Second-order cone programming
![]() | This article may be too technical for most readers to understand.(October 2011) |
A second-order cone program (SOCP) is a convex optimization problem of the form
- minimize
- subject to
where the problem parameters are , and . is the optimization variable. is the Euclidean norm and indicates transpose.[1] The "second-order cone" in SOCP arises from the constraints, which are equivalent to requiring the affine function to lie in the second-order cone in .[1]
SOCPs can be solved by interior point methods[2] and in general, can be solved more efficiently than semidefinite programming (SDP) problems.[3] Some engineering applications of SOCP include filter design, antenna array weight design, truss design, and grasping force optimization in robotics.[4] Applications in quantitative finance include portfolio optimization; some market impact constraints, because they are not linear, cannot be solved by quadratic programming but can be formulated as SOCP problems.[5][6][7]
Second-order cone
[edit]The standard or unit second-order cone of dimension is defined as
.
The second-order cone is also known by quadratic cone or ice-cream cone or Lorentz cone. The standard second-order cone in is .
The set of points satisfying a second-order cone constraint is the inverse image of the unit second-order cone under an affine mapping:
and hence is convex.
The second-order cone can be embedded in the cone of the positive semidefinite matrices since
i.e., a second-order cone constraint is equivalent to a linear matrix inequality (Here means is semidefinite matrix). Similarly, we also have,
.
Relation with other optimization problems
[edit]![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Hierarchy_compact_convex.png/220px-Hierarchy_compact_convex.png)
When for , the SOCP reduces to a linear program. When for , the SOCP is equivalent to a convex quadratically constrained linear program.
Convex quadratically constrained quadratic programs can also be formulated as SOCPs by reformulating the objective function as a constraint.[4] Semidefinite programming subsumes SOCPs as the SOCP constraints can be written as linear matrix inequalities (LMI) and can be reformulated as an instance of semidefinite program.[4] The converse, however, is not valid: there are positive semidefinite cones that do not admit any second-order cone representation.[3] In fact, while any closed convex semialgebraic set in the plane can be written as a feasible region of a SOCP,[8] it is known that there exist convex semialgebraic sets that are not representable by SDPs, that is, there exist convex semialgebraic sets that can not be written as a feasible region of a SDP.[9]
Examples
[edit]Quadratic constraint
[edit]Consider a convex quadratic constraint of the form
This is equivalent to the SOCP constraint
Stochastic linear programming
[edit]Consider a stochastic linear program in inequality form
- minimize
- subject to
where the parameters are independent Gaussian random vectors with mean and covariance and . This problem can be expressed as the SOCP
- minimize
- subject to
where is the inverse normal cumulative distribution function.[1]
Stochastic second-order cone programming
[edit]We refer to second-order cone programs as deterministic second-order cone programs since data defining them are deterministic. Stochastic second-order cone programs are a class of optimization problems that are defined to handle uncertainty in data defining deterministic second-order cone programs.[10]
Other examples
[edit]Other modeling examples are available at the MOSEK modeling cookbook.[11]
Solvers and scripting (programming) languages
[edit]Name | License | Brief info |
---|---|---|
AMPL | commercial | An algebraic modeling language with SOCP support |
Artelys Knitro | commercial | |
Clarabel | open source | Native Julia and Rust SOCP solver. Can solve convex problems with arbitrary precision types. |
CPLEX | commercial | |
CVXPY | open source | Python modeling language with support for SOCP. Supports open source and commercial solvers. |
CVXOPT | open source | Convex solver with support for SOCP |
ECOS | open source | SOCP solver optimized for embedded applications |
FICO Xpress | commercial | |
Gurobi Optimizer | commercial | |
MATLAB | commercial | The coneprog function solves SOCP problems[12] using an interior-point algorithm[13]
|
MOSEK | commercial | parallel interior-point algorithm |
NAG Numerical Library | commercial | General purpose numerical library with SOCP solver |
SCS | open source | SCS (Splitting Conic Solver) is a numerical optimization package for solving large-scale convex quadratic cone problems. |
See also
[edit]- Power cones are generalizations of quadratic cones to powers other than 2.[14]
References
[edit]- ^ a b c Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved July 15, 2019.
- ^ Potra, lorian A.; Wright, Stephen J. (1 December 2000). "Interior-point methods". Journal of Computational and Applied Mathematics. 124 (1–2): 281–302. Bibcode:2000JCoAM.124..281P. doi:10.1016/S0377-0427(00)00433-7.
- ^ a b Fawzi, Hamza (2019). "On representing the positive semidefinite cone using the second-order cone". Mathematical Programming. 175 (1–2): 109–118. arXiv:1610.04901. doi:10.1007/s10107-018-1233-0. ISSN 0025-5610. S2CID 119324071.
- ^ a b c Lobo, Miguel Sousa; Vandenberghe, Lieven; Boyd, Stephen; Lebret, Hervé (1998). "Applications of second-order cone programming". Linear Algebra and Its Applications. 284 (1–3): 193–228. doi:10.1016/S0024-3795(98)10032-0.
- ^ "Solving SOCP" (PDF).
- ^ "portfolio optimization" (PDF).
- ^ Li, Haksun (16 January 2022). Numerical Methods Using Java: For Data Science, Analysis, and Engineering. APress. pp. Chapter 10. ISBN 978-1484267967.
- ^ Scheiderer, Claus (2020-04-08). "Second-order cone representation for convex subsets of the plane". arXiv:2004.04196 [math.OC].
- ^ Scheiderer, Claus (2018). "Spectrahedral Shadows". SIAM Journal on Applied Algebra and Geometry. 2 (1): 26–44. doi:10.1137/17M1118981. ISSN 2470-6566.
- ^ Alzalg, Baha M. (2012-10-01). "Stochastic second-order cone programming: Applications models". Applied Mathematical Modelling. 36 (10): 5122–5134. doi:10.1016/j.apm.2011.12.053. ISSN 0307-904X.
- ^ "MOSEK Modeling Cookbook - Conic Quadratic Optimization".
- ^ "Second-order cone programming solver - MATLAB coneprog". MathWorks. 2021-03-01. Retrieved 2021-07-15.
- ^ "Second-Order Cone Programming Algorithm - MATLAB & Simulink". MathWorks. 2021-03-01. Retrieved 2021-07-15.
- ^ "MOSEK Modeling Cookbook - the Power Cones".