Interior Point Methods: Semidefinite and Nonlinear Programming

在半定规划（SDP）问题中，对称矩阵变量X的线性函数在X上的线性等式约束和X是半正定的基本约束下被最小化. 一些问题可以被转换为SDP问题，包括线性规划，凸二次不等式约束的凸二次问题，矩阵范数最小化以及各种最大和最小特征值问题。此外，SDP在工程、组合优化和统计学中也有许多应用。 已知线性规划的几种内点算法可以推广到SDP问题。在线性规划中，这些方法中的许多是多项式收敛的，并且在实践中非常有效。特别地，原始-对偶内点方法类及其高阶变体是最有效的内点方法。 与线性规划相比，有许多方法可以计算SDP的原始-对偶算法中使用的牛顿搜索方向。由于这个原因，SDP的原始-对偶方法的理论实质上比LP更困难。 本计画致力于发展求解SDP问题的原始-对偶内点演算法的理论与实作。 本研究计划的目标包括：1）发展一种新的求解SDP的原始-对偶内点算法; 2）提高求解SDP的多项式理论和原始-对偶方法的超线性收敛性分析的知识; 3）研究SDP的连续轨迹的存在性和渐近性; 4）发展新的高阶原始-对偶方法; 5）实现新算法并与已有的原-对偶内点算法进行比较; 6）将原-对偶内点算法推广到非线性SDP和互补问题。

In a semidefinite programming (SDP) problem, a linear function of a symmetric matrix variable X is minimized subject to linear equality constraints on X and the essential constraint that X be positive semidefinite. Several problems can be cast as SDP problems including linear programs, convex quadratic problems with convex quadratic inequality constraints, matrix norm minimization and a variety of maximum and minimum eigenvalue problems. In addition, SDP has many applications in enginnering, combinatorial optimization and statistics. It is known that several interior point algorithms for linear programs can be extended to SDP problems. As in linear programming, many of these methods are polynomially convergent and perform very efficiently in practice. In particular, the class of primal-dual interior point methods and their higher- order variants are the most effective interior point methods. In contrast to linear programming, there are many ways one can compute the Newton search directions used in primal-dual algorithms for SDP. For this reason, the theory of primal-dual methods for SDP is substantially more difficult than that for LP. This project addresses the development of the theory and implementation of primal-dual interior point algorithms for SDP problems. The objectives of this research project include: 1) developing a new primal-dual interior point algorithm for SDP; 2) advancing the knowledge of the theory of polynomial and superlinear convergence analysis of primal-dual methods for SDP; 3) studying the existence and asymptotic behavior of continuous trajectories for SDP; 4) developing new higher-order primal-dual methods for SDP; 5) implementing the new proposed algorithm and comparing it against existing primal-dual interior point methods; and 6) extending primal-dual interior point algorithms to the context of nonlinear SDP and complementarity problems.