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方法的多项式时间复杂度。此外，与线性规划一样，原始-对偶方法的子类及其高阶变体对于求解SDP问题也是非常有效的。然而，与LP不同的是，可以通过多种方式使用SDP的原对偶算法来计算牛顿搜索方向。由于这个原因，SDP的原-对偶方法的理论和实现比LP的原-对偶方法更困难。一阶NLP算法已经被开发作为二阶IP方法（基于精确线性求解器）的替代方案，用于求解在某些应用中出现的大规模SDP，例如，这些方法将SDP问题转化为NLP问题，可以使用标准的NLP技术解决-特别是一阶技术，它不需要像二阶技术那样多的计算。然而，排除二阶信息使得（也许不可能）建立这种算法的多项式复杂性。基于迭代线性求解器的二阶IP方法的多项式收敛性分析仍然是一个没有很好理解的话题。由于这些方法在解决大规模SDP问题时有可能优于一阶方法，研究这些方法的理论和实践行为是至关重要的。本文首先从LP问题出发，然后从二次规划、二阶锥规划和SDP等锥规划问题出发，对SDP的理论发展和算法实现进行了深入的研究，并对SDP的应用进行了探讨。本研究计划的目标包括：1）推进LP、SDP和其他锥规划问题的二阶原始-对偶方法的理论和实现的知识;2）开发和实现LP和更一般的锥规划的基于迭代线性解的二阶IP算法;3）开发新的和/或改进现有的SDP的一阶光滑和非光滑算法和实现; 4）增强了SDP一阶NLP方法的多样性、适用性、实用性和鲁棒性：5）发展了基于低秩约束SDP问题的组合问题SDP算法;和6）发展新的见解的几何中心路径和itsconsequences的多项式可解性的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.