Investigations in Interior Point Methods and Convex Programming

摘要本项目的目标是开发内点法的算法和工具。研究人员将继续他正在进行的内点方法的研究，目的是推进半定规划(SDP)和相关问题的几个突出主题。在SDP中以及通常在对称锥体上进行编程时，需要更好地了解邻域和路径。为了开发出更快的渐近收敛和数值稳定性方面更有效的算法，这是必要的。研究人员打算开发有效的数学工具来处理这些问题。齐次圆锥和双曲圆锥上的程序设计很可能成为内点方法的下一个新兴领域，因此有必要为这类问题开发高效、长步长的内点算法。最终，内点法将需要处理更复杂的工业应用，这些应用必须得到有效的解决。该项目将涉及内点方法的所有这些领域；将在所有情况下设计有效的算法，并将开发所需的数学工具。该项目还有另外两个目标。第一个是对偶理论在其传统凸性之外的扩展，第二个是凸规划的更快的近似点算法的发展。内点方法已经成功地解决了工业中的许多大型工业问题：在土木工程和电气工程、管理、通信网络、金融等领域。这些方法的进一步适用性取决于对其行为的更好理解和适当软件的持续开发。这个项目的目的是寻找有效的算法和改进的数学工具，以便有效地解决来自不同行业学科的大规模优化问题。

AbstractThe goal of this project is to develop algorithms and tools for interior point methods. The investigator will continue his ongoing research into interior point methods with the aim of advancing several outstanding topics in semidefinite programming (SDP) and related problems. A better understanding of neighborhoods and paths is needed in SDP, and in programming over a symmetric cone in general. This is necessary in order to develop more efficient algorithms in terms of faster asymptotic convergence and numerical stability. The investigator intends to develop effective mathematical tools to deal with these issues. Programming over homogeneous cones and hyperbolic cones are likely to become the next emerging fields in interior point methods, and there is a need to develop efficient, long-step interior algorithms for such problems. Eventually, interior point methods will need to deal with even more complicated industrial applications which must be solved efficiently. The project will involve all of these areas of interior point methods; efficient algorithms will be devised in all cases, and the needed mathematical tools will be developed. The project also has two other goals. The first is an extension of duality theory beyond its traditional convexity, and the second one is the development of faster proximal point algorithms for convex programming. Interior point methods have been successful in solving many large scale industrial problems in industry: in civil and electrical engineering, management, communication networks, finance, and others. Further applicability of these methods depends on a better understanding of their behavior and continuous development of appropriate software. This project aims to search for efficient algorithms and improved mathematical tools so that large scale optimization problems arising from diverse industrial disciplines can be efficiently solved.