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

协作研究：半定规划的理论与实现及其在组合优化中的应用

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

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.

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