Collaborative Research: Theory and Implementation of Semidefinite Programming and its Applications to Combinatorial Optimization

在半定规划（SDP）问题中，对称矩阵变量X的线性函数在X的线性等式约束和X是半正定的本质约束下被最小化。许多数学优化问题都可以转化为SDP问题，包括线性规划、带凸二次不等式约束的凸二次问题、矩阵范数最小化问题以及各种极大极小特征值问题。此外，SDP在组合优化、工程、统计和鲁棒优化等领域也有广泛的应用。目前，有许多可用于求解sdp的算法和代码，这些方法可以大致分为两类：二阶内点（IP）方法和一阶非线性规划（NLP）方法。对于特定应用程序使用哪种类的选择主要取决于问题的大小——二阶IP方法在中小型问题上更有效，而一阶NLP方法在大规模问题上更好。

ABSTRACT0203113Monteiro, Renato GA Tech Res Corp -GITIn 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. Many mathematical optimization problems can be cast as SDP problems including linear programs, convex quadratic problems with convex quadratic inequality constraints, matrix norm minimization problems, and a variety of maximum and minimum eigenvalue problems. In addition, SDP has many applications in combinatorial optimization, engineering, statistics, and robust optimization.Today, there are numerous algorithms and codes available for solving SDPs, and these methods can be loosely grouped into two classes: second-order interior-point (IP) methods and first-order nonlinear programming (NLP) methods. The choice of which class to use for a particular application is determined primarily byproblem size --- second-order IP methods are more efficient on small- to medium-scale problems while first-order NLP methods are better for large-scale problems.