Cone programming: Theory, Implementation and Applications

圆锥规划：理论、实现和应用

• 批准号: 0430644
• 负责人: Renato D. C. Monteiro
• 金额: $ 20万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430644&HistoricalAwards=false
• 关键词: Cone; programming; Theory; Implementation; Applications

Abstract:--------In a semidefinite programming (SDP) problem, a linear function ofa symmetric matrix variable $X$ is minimized subject to linearequality constraints on $X$ and the essential constraint that $X$be positive semidefinite. Many mathematical optimization problemscan be cast as SDP problems including linear programming (LP) problems,convex quadratic problems with convex quadratic inequality constraints,matrix norm minimization problems, and a variety of maximum andminimum eigenvalue problems. In addition, SDP has manyapplications in combinatorial optimization, engineering,statistics, and robust optimization.Today, there are numerous algorithms and codes available forsolving LPs, SDPs, and other cone programs,and these methods can be loosely grouped into three types:second-order interior-point (IP) methods based on exact linear solvers,second-order IP methods based on iterative linear solvers, and first-ordernonlinear programming (NLP) methods. The choice of which type touse for a particular application is determined primarily byproblem size --- second-order IP methods based on exact linear solversare more efficient on small- to medium-scale problems whilefirst-order NLP methods and second-order IP methods based on iterativelinear solvers are better for large-scale problems.Second-order IP algorithms for SDP are derived from similaralgorithms for LP and, inparticular, inherit the polynomial-time complexity of IP methodsfor LP. In addition, as in LP, the subclass of primal-dual methodsand their higher-order variants are very effective for solving SDPproblems practically. In contrast to LP, however, there are manyways one can compute the Newton search directions used inprimal-dual algorithms for SDP. For this reason, the theory andimplementation of primal-dual methods for SDP is substantiallymore difficult than that for LP.First-order NLP algorithms have been developed as an alternativeto second-order IP methods (based on exact linear solvers)for solving large-scale SDPs that arisein certain applications, e.g., in combinatorial optimization.These methods reformulate the SDP problem into a NLP problem thatcan be solved using standard NLP techniques --- in particular,first-order techniques that do not require as much computation assecond-order techniques. The exclusion of second-orderinformation, however, makes it difficult (perhaps impossible) toestablish the polynomial complexity of such algorithms.Polynomial convergence analysis of second-order IP methods based oniterative linear solvers is still a topic which is not well-understood.Since these methods have the potential to outperform first-ordermethods in the solution of large-scale SDP problems, it is ofparamount importance to study the theoretical and practical behavior of thesemethods. This proposal will address this topic in depth first inthe context of the basic LP problem and then in the context ofother cone programming problems such as quadratic programming (QP),second-order cone programming and SDP.This proposal addresses the development of the theory andimplementation of algorithms for SDP and also investigates the applicationsof SDP. The objectives of this research project consist of:1) advancing the knowledge of the theory and implementation ofsecond-order primal-dual methods for LP, SDP and other coneprogramming problems;2) developing and implementing second-order IP algorithms based on iterativelinear solvers for LP and more general cone programs;3) developing new and/or improving existing algorithms and implementations forfirst-order smooth and non-smooth methods for SDP;4) enhancing the variety, applicability, usefulness, and robustnessof first-order NLP methods for SDP;5) developing SDP heuristics for combinatorial problems based on low-rankrestricted SDP problems; and6) develop new insights of the geometry of the central path and itsconsequences into the polynomial solvability of IP methods.This research will lead to new and improved algorithms and codesto find exact or approximate solutions to optimization problemsarising in diverse applications in industry, finance, science, andengineering.

文摘：-在半定规划问题中，对称矩阵变量$X$的线性函数在$X$上线性重复性约束和$X$为半正定的本质约束下被最小化。许多数学优化问题可以归结为SDP问题，包括线性规划(LP)问题、具有凸二次不等式约束的凸二次问题、矩阵范数最小化问题以及各种最大和最小特征值问题。此外，SDP在组合优化、工程、统计学和稳健优化等领域有着广泛的应用。目前，求解LP、SDP等锥规划的算法和代码很多，这些方法大致可分为三类：基于精确线性求解器的二阶内点方法、基于迭代线性求解器的二阶内点方法和一阶非线性规划方法。对于特定的应用，选择哪种类型的方法主要取决于问题的大小-基于精确线性解的二阶IP方法对于中小型问题是更有效的，而基于迭代线性求解器的一阶NLP方法和二阶IP方法对于大规模问题是更好的。SDP的二阶IP算法是从类似的LP算法得到的，特别是继承了LP IP方法的多项式时间复杂度。此外，与线性规划中一样，原对偶方法的子类及其高阶变种对于实际求解SDP问题是非常有效的。然而，与线性规划不同的是，对于SDP，有许多方法可以用来计算牛顿搜索方向。正因为如此，SDP的原-对偶方法的理论和实现都比LP困难得多。一阶NLP算法已经被发展为二阶IP方法(基于精确线性求解器)的替代，用于求解某些应用中出现的大规模SDP问题，例如在组合优化中。这些方法将SDP问题重新描述为一个NLP问题，可以用标准的NLP技术--特别是不需要像二阶技术那样大量计算的一阶技术--来求解。基于迭代线性求解器的二阶激电方法的多项式收敛分析仍然是一个尚未被很好理解的课题。由于这些方法在求解大规模SDP问题时具有优于一阶方法的潜力，因此研究这些方法的理论和实际行为是至关重要的。这项建议将首先在基本线性规划问题的背景下，然后在其他锥规划问题，如二次规划(QP)、二阶锥规划和SDP的背景下，深入讨论这一主题。该建议涉及SDP的理论和算法实现的发展，并研究SDP的应用。本研究的目标包括：1)增进对二阶原-对偶方法的理论和实现的认识；2)开发和实现基于迭代线性求解器的二阶IP算法，用于线性规划和更一般的锥规划；3)开发和/或改进现有的一阶光滑和非光滑方法的算法和实现；4)增强求解SDP的一阶NLP方法的多样性、适用性、有用性和健壮性；5)开发基于低阶约束SDP问题的组合问题的SDP启发式算法；以及6)将中心路径的几何及其结果发展到IP方法的多项式可解性的新见解。这项研究将导致新的和改进的算法和代码，以找到在工业、金融、科学和工程中的各种应用中的优化问题的精确或近似解。