Cone programming: Theory, Implementation and Applications

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

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.