A Deeper Understanding of the Geometry of Interior-Point Methods

更深入地理解内点方法的几何形状

• 批准号: 9901941
• 负责人: James Renegar
• 金额: $ 19.84万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-06-15 至 2003-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9901941&HistoricalAwards=false
• 关键词: Deeper; Understanding; Geometry; Interior; Point

The project is aimed at providing a better understanding of the geometry of the central paths for linear programming problems, the paths that are followed by interior-point methods. The motivation for better understanding the geometry is the hope that it might be useful in resolving a major open problem in optimization, namely, whether or not a genuinely polynomial algorithm exists. It might be possible to design such an algorithm by extending interior-point ideas, the extensions requiring a deeper understanding of the geometry than presently exists.Another aim is to develop an efficient symbolic method for making queries regarding the exact optimal solutions of semi-definite programming problems. Interior-point methods only approximate the optimal solutions, so in general do not suffice to answer such queries.The research is expected to make the most mathematical interior-point method theory (for general convex optimization) more cohesive, as well as more accessible to researchers in related areas. It is hoped that by focusing on the geometry underlying interior-point methods --- in particular, focusing on the inner products induced by the barrier functions --- the advanced theory can be made more transparent and better motivated to Ph.D. students and outside researchers.

该项目旨在更好地理解线性规划问题的中心路径的几何形状，这些路径遵循内点方法。更好地理解几何的动机是希望它可能有助于解决优化中的一个主要开放问题，即，是否存在真正的多项式算法。通过扩展内点思想来设计这样一个算法是可能的，这种扩展需要比目前存在的更深入的几何理解。另一个目标是开发一种有效的符号方法，用于查询半确定规划问题的精确最优解。内点方法只能近似最优解，因此通常不足以回答此类查询。该研究有望使最具数学性的内点法理论（用于一般凸优化）更具凝聚力，并使相关领域的研究人员更容易使用。希望通过关注内点方法的几何基础-特别是关注由势垒函数引起的内积-可以使先进的理论更加透明，更好地激励博士生和外部研究人员。