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
SOCPs can be solved by
Second-order cone
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
When for , the SOCP reduces to a
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
Quadratic constraint
Consider a convex quadratic constraint of the form
This is equivalent to the SOCP constraint
Stochastic linear programming
Consider a
- 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
Stochastic second-order cone programming
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
Other modeling examples are available at the MOSEK modeling cookbook.[11]
Solvers and scripting (programming) languages
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
- Power cones are generalizations of quadratic cones to powers other than 2.[14]
References
- ^ ISBN 978-0-521-83378-3. Retrieved July 15, 2019.
- .
- ^ S2CID 119324071.
- ^ .
- ^ "Solving SOCP" (PDF).
- ^ "portfolio optimization" (PDF).
- ISBN 978-1484267967.
- arXiv:2004.04196 [math.OC].
- ISSN 2470-6566.
- 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".