Second-order Cone Programming : Algorithms and Applications

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.