Transcription of Second-order cone programming - University of Chicago
1 Math. Program., Ser. B 95: 3 51 (2003)Digital Object Identifier (DOI) Alizadeh D. Goldfarb Second-order cone programmingReceived: August 18, 2001 / Accepted: February 27, 2002 Published online: December 9, 2002 c Springer-Verlag 20021. IntroductionSecond-order cone programming (SOCP) problems are convex optimization problemsin which a linear function is minimized over the intersection of an affine linear manifoldwith the Cartesian product of Second-order (Lorentz) cones. Linear programs, convexquadratic programs and quadratically constrained convex quadratic programs can allbe formulated as SOCP problems, as can many other problems that do not fall intothese three categories.
2 These latter problems model applications from a broad range offields from engineering, control and finance to robust optimization and the other hand semidefinite programming (SDP) that is the optimization problemover the intersection of an affine set and the cone of positive semidefinite matrices in-cludes SOCP as a special case. Therefore, SOCP falls between linear (LP) and quadratic(QP) programming and SDP. Like LP, QP and SDP problems, SOCP problems can besolved in polynomial time by interior point methods.
3 The computational effort per iter-ation required by these methods to solve SOCP problems is greater than that required tosolve LP and QP problems but less than that required to solve SDP s of similar size andstructure. Because the set of feasible solutions for an SOCP problem is not polyhedralas it is for LP and QP problems, it is not readily apparent how to develop a simplex orsimplex-like method for SOCP problems can be solved as SDP problems, doing so is not advisableboth on numerical grounds and computational complexity concerns.
4 For instance, manyof the problems presented in the survey paper of Vandenberghe and Boyd [VB96] asexamples of SDPs can in fact be formulated as SOCPs and should be solved as 2, 3 below we give SOCP formulations for four of these examples: the convexquadratically constrained quadratic programming (QCQP) problem, problems involvingfractional quadratic functions such as those that arise in structural optimization, logarith-mic Tchebychev approximation and the problem of finding the smallest ball containing aF.
5 Alizadeh: RUTCOR and School of Business, Rutgers, State University of New Goldfarb: IEOR, Columbia University , Research supported in part by the National Science Foundation grant CCR-9901991 Research supported in part by the Department of Energy grant DE-FG02-92ER25126, National ScienceFoundation grants DMS-94-14438, CDA-97-26385 and Alizadeh, D. Goldfarbgiven set of ellipsoids. Thus, because of its broad applicability and its computationaltractability, SOCP deserves to be studied in its own examples of SOCP problems have been studied for a long time.
6 The clas-sical Fermat-Weber problem (described in below) goes back several centuries; see[Wit64] and more recently [XY97] for further references and background. The paper ofLobo et al [LVBL98] contains many applications of SOCP in engineering. Nesterov andNemirovski [NN94], Nemirovski [Nem99] and Lobo et al [LVBL98] show that manykinds of problems can be formulated as SOCPs. Our presentation in 2 is based in parton these references. Convex quadratically constrained programming (QCQP), which isa special case of SOCP, has also been widely studied in the last decade.
7 Extension ofKarmarkar s interior point method [Kar84] to QCQPs began with Goldfarb, Liu andWang [GLW91], Jarre [Jar91] and Mehrotra and Sun [MS91].Nesterov and Nemirovski [NN94] showed that their general results on self-concor-dant barriers apply to SOCP problems, yielding interior point algorithms for SOCP with an iteration complexity of rfor problems withrsecond-order cone inequalities(see below for definitions). Nemirovski and Scheinberg [NS96] showed that primal ordual interior point methods developed for linear programming can be extended in aword-for-word fashion to SOCP; specifically they showed this for Karmarkar s came the study of primal-dual interior point methods for SOCP.
8 As in linear andsemidefinite programming , primal-dual methods seem to be numerically more robustfor solving SOCPs. Furthermore, exploration of these methods leads to a large class ofalgorithms, the study of which is both challenging and potentially significant in prac-tice. Study of primal-dual interior point methods for SOCP started with Nesterov andTodd [NT97, NT98]. These authors presented their results in the context of optimizationover self-scaled cones, which includes the class of Second-order cones as special work culminated in the development of a particular primal-dual method called theNT method.
9 Adler and Alizadeh [AA95] studied the relationship between semidefiniteand Second-order cone programs and specialized the so-calledXZ+ZXmethod of[AHO98] to SOCP. Then Alizadeh and Schmieta [AS97] gave nondegeneracy condi-tions for SOCP and developed a numerically stable implementation of theXZ+ZXmethod; this implementation is used in theSDPpacksoftware package, [AHN+97]. ( 5and 6 below are partly based on [AS97].) Subsequently, Monteiro and Tsuchiya in[MT00] proved that this method, and hence all members of the Monteiro-Zhang familyof methods, have a polynomial iteration is a unifying theory based on Euclidean Jordan algebras that connects LP, SDPand SOCP.
10 The text of Faraut and Kor any [FK94] covers the foundations of this review this theory for the particular Jordan algebra relevant to SOCP problems in [Fay97b, Fay97a, Fay98] studied nondegeneracy conditions and presentedthe NT,XZandZXmethods in Jordan algebraic terms. Schmieta [Sch99] and Schmi-eta and Alizadeh [SA01, SA99] extended the analysis of the Monteiro-Zhang familyof interior point algorithms from SDP to all symmetric cones using Jordan algebraictechniques. They also showed that word-for-word generalizations of primal based anddual based interior point methods carry over to all symmetric cones [AS00].
