Cone programming: Theory, Implementation and Applications

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Abstract: -------- 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. Many mathematical optimization problems can 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 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 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-order nonlinear programming (NLP) methods. The choice of which type to use for a particular application is determined primarily by problem size --- second-order IP methods based on exact linear solvers are more efficient on small- to medium-scale problems while first-order NLP methods and second-order IP methods based on iterative linear solvers are better for large-scale problems. Second-order IP algorithms for SDP are derived from similar algorithms for LP and, in particular, inherit the polynomial-time complexity of IP methods for LP. In addition, as in LP, the subclass of primal-dual methods and their higher-order variants are very effective for solving SDP problems practically. In contrast to LP, however, there are many ways one can compute the Newton search directions used in primal-dual algorithms for SDP. For this reason, the theory and implementation of primal-dual methods for SDP is substantially more difficult than that for LP. First-order NLP algorithms have been developed as an alternative to second-order IP methods (based on exact linear solvers) for solving large-scale SDPs that arise in certain applications, e.g., in combinatorial optimization. These methods reformulate the SDP problem into a NLP problem that can be solved using standard NLP techniques --- in particular, first-order techniques that do not require as much computation as second-order techniques. The exclusion of second-order information, however, makes it difficult (perhaps impossible) to establish the polynomial complexity of such algorithms. Polynomial convergence analysis of second-order IP methods based on iterative linear solvers is still a topic which is not well-understood. Since these methods have the potential to outperform first-order methods in the solution of large-scale SDP problems, it is of paramount importance to study the theoretical and practical behavior of these methods. This proposal will address this topic in depth first in the context of the basic LP problem and then in the context of other cone programming problems such as quadratic programming (QP), second-order cone programming and SDP. This proposal addresses the development of the theory and implementation of algorithms for SDP and also investigates the applications of SDP. The objectives of this research project consist of: 1) advancing the knowledge of the theory and implementation of second-order primal-dual methods for LP, SDP and other cone programming problems; 2) developing and implementing second-order IP algorithms based on iterative linear solvers for LP and more general cone programs; 3) developing new and/or improving existing algorithms and implementations for first-order smooth and non-smooth methods for SDP; 4) enhancing the variety, applicability, usefulness, and robustness of first-order NLP methods for SDP; 5) developing SDP heuristics for combinatorial problems based on low-rank restricted SDP problems; and 6) develop new insights of the geometry of the central path and its consequences into the polynomial solvability of IP methods. This research will lead to new and improved algorithms and codes to find exact or approximate solutions to optimization problems arising in diverse applications in industry, finance, science, and engineering.