Theory and Implementation of Algorithms for Semi-Definite and Cone Programming

半定锥规划算法的理论与实现

• 批准号: 9902010
• 负责人: Renato D. C. Monteiro
• 金额: $ 23.1万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-07-01 至 2003-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9902010&HistoricalAwards=false
• 关键词: Theory; Implementation; Algorithms; Semi; Definite

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 SCP 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 engineering, combinatorial optimization and statistics.Today, 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 very effective methods for solving SDP problems. 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 algorithms for SDP problems. The objectives of this research consist of: 1) advancing the knowledge of the theory of polynomial and superlinear convergence analysis of primal-dual methods for SDP; 2) studying the existence and asymptotic behavior of continuous trajectories for SDP; 3) developing superlinearly convergent higher-order primal-dual methods for SDP problems which do not have strictly complementary solutions; 4) developing interior-point primal-dual algorithms to solve more general classes of cone programming problems; 5) developing new methods for solving specially structured SDP problems based on nonlinear programming techniques; 6) implementing these new approaches and comparing them against existing SDP methods; 7) extending primal-dual interior point algorithms to the context of nonlinear SDP and complementary problems.This research will lead to new or improved algorithms to find exact or approximate solutions to large-scale optimization problems arising in diverse applications in industry, finance, science, and engineering.

在半定规划（SDP）问题中，对称矩阵变量X的线性函数在X的线性等式约束和X是半正定的基本约束下被最小化。线性规划问题、带凸二次不等式约束的凸二次问题、矩阵范数最小化问题和各种极大极小特征值问题都可以被描述为SCP问题。此外，SDP在工程、组合优化和统计等方面也有广泛的应用。目前，已知一些线性规划的内点算法可以推广到SDP问题。与线性规划一样，这些方法中的许多都是多项式收敛的，在实践中表现得非常有效。其中，一类原对偶内点法及其高阶变异体是求解SDP问题的有效方法。与线性规划相反，有许多方法可以计算SDP的原始对偶算法中使用的牛顿搜索方向。因此，SDP的原始对偶方法的理论要比LP的理论困难得多。该项目解决了SDP问题的理论和算法的发展。本研究的目标包括：1)提高了SDP的多项式理论和原始-对偶方法的超线性收敛分析的知识；2)研究了SDP连续轨迹的存在性和渐近性；3)发展了不具有严格互补解的SDP问题的超线性收敛的高阶原对偶方法；4)发展内点原对偶算法来解决更一般的锥规划问题；5)基于非线性规划技术，开发求解特殊结构SDP问题的新方法；6)实施这些新方法，并将其与现有的SDP方法进行比较；7)将原始-对偶内点算法推广到非线性SDP和互补问题。这项研究将导致新的或改进的算法，以找到精确或近似的解决方案，大规模优化问题出现在工业，金融，科学和工程的各种应用。