Second-order Cone Programming : Algorithms and Applications

Columbia University, New York NY

Investigators

Abstract

Large Second-order Cone Programming: Algorithms and Applications. PI. Donald Goldfarb and Garud Iyengar. Abstract. Second-order cone programs (SOCPs) are convex optimization problems in which a linear function is optimized over the intersection of an affine linear manifold with the Cartesian product of second-order (Lorentz) cones. Linear programs (LPs), convex quadratic programs (QPs), and quadratically constrained convex quadratic programs can all be formulated as SOCPs, as can many other problems that do not fall into these three problem classes. On the other hand, since a second-order cone constraint is equivalent to a linear matrix inequality, semidefinite programs (SDPs) include SOCPs as a special case. Computationally speaking, an SOCP falls between an LP or a QP and an SDP. Interior point methods solve all of these problems in polynomial time. Although, the computational effort required to solve an SOCP is greater than that required to solve an LP or a QP, it is substantially less than that required to solve an SDP of similar size and structure. However, in many ways, an SOCP is closer to an SDP than an LP or QP since its feasible set is non-polyhedral. The proposed research focuses on several aspects of SOCPs, including the development of numerically stable algorithms for SOCPs that take advantage of sparsity in the data, the study of SOCP-based approximation algorithms for hard combinatorial optimization problems, the study of computational aspects of cut generation methods for mixed 0-1 SOCPs and the applications of SOCPs in robust financial optimization. SOCPs are excellent models for applications that arise in a broad range of fields from engineering, control, and finance, to robust and combinatorial optimization. The wide applicability of SOCPs and the need for efficient, numerically stable algorithms to solve them makes their study worthwhile.