A Deeper Understanding of the Geometry of Interior-Point Methods

点击翻译按钮获取中文摘要

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.