Cone programming: Theory, Implementation and 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.