Second-order cone programming
Encyclopedia
A second-order cone program (SOCP) is a convex optimization problem of the form
where the problem parameters are
, and 
. Here 
is the optimization variable. When 
for 
, the SOCP reduces to a linear program. When 
for 
, the SOCP is equivalent to a convex Quadratically constrained quadratic program
. Semidefinite programs
subsumes SOCPs as the SOCP constraints can be written as Linear Matrix Inequalities(LMI) and can be reformulated as an instance of semi definite program. SOCPs can be solved with great efficiency by interior point methods.
This is equivalent to the SOC constraint
where the parameters
are independent Gaussian random vectors with mean 
and covariance 
and 
. This problem can be expressed as the SOCP
where
is the inverse error function
.
1. Free and opensource, with OSI-Approved licenses
2. Commercial
Note that the most of the solvers in the above list are more general solvers (i.e they solve Semidefinite Programs
or more general Convex optimization problems). There have been a few benchmarking studies comparing the various solvers
- minimize
subject to
where the problem parameters are
, and . Here is the optimization variable. When for , the SOCP reduces to a linear program. When for , the SOCP is equivalent to a convex Quadratically constrained quadratic programQuadratically constrained quadratic program
In mathematics, a quadratically constrained quadratic program is an optimization problem in which both the objective function and the constraints are quadratic functions...
. Semidefinite programs
Semidefinite programming
Semidefinite programming is a subfield of convex optimization concerned with the optimization of a linear objective functionover the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron....
subsumes SOCPs as the SOCP constraints can be written as Linear Matrix Inequalities(LMI) and can be reformulated as an instance of semi definite program. SOCPs can be solved with great efficiency by interior point methods.
Example: Quadratic Constraint
Consider a quadratic constraint of the formThis is equivalent to the SOC constraint
Example: Stochastic Programming
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 error functionError function
In mathematics, the error function is a special function of sigmoid shape which occurs in probability, statistics and partial differential equations...
.
Solvers
There are various solvers available for solving SOCP. Some of the popular ones are listed below1. Free and opensource, with OSI-Approved licenses
| Name | License | Brief info |
|---|---|---|
| CSDP | CPL Common Public License In computing, the CPL is a free software / open-source software license published by IBM. The Free Software Foundation and Open Source Initiative have approved the license terms of the CPL.... |
a library of routines that implements a predictor corrector variant of the semidefinite programming algorithm of Helmberg, Rendl, Vanderbei, and Wolkowicz |
| DSDP | GPL | is present in Linux software channels |
| OpenOpt OpenOpt OpenOpt is an open-source framework for numerical optimization, nonlinear equations and systems of them. It is licensed under the BSD license, making it available to be used in both open- and closed-code software. The package already has some essential .... |
BSD BSD licenses BSD licenses are a family of permissive free software licenses. The original license was used for the Berkeley Software Distribution , a Unix-like operating system after which it is named.... |
universal cross-platform numerical optimization framework; see its SOCP page and full list of problems |
| SBmethod | GPL | no longer supported |
| SDPT3 | GPL2 | API: MATLAB MATLAB MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,... (commercial); last update - December 2002 |
| SDPA | GPL | primal-dual interior-point method |
| SDPLR | GPL? | language: C, API: MATLAB |
| SeDuMi | GPL? | package for commercial MATLAB MATLAB MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,... |
| CVXOPT | GPL | a comprehensive Python Python (programming language) Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive... library for convex optimization |
2. Commercial
- MOSEK — The first commercially available software package for solution SOCP. with Free Academic Licence.
- CPLEX — Full-featured solver for large scale linear, quadratic, and integer programming problems, including SOCP
- PENSDP
- LOQO
Note that the most of the solvers in the above list are more general solvers (i.e they solve Semidefinite Programs
Semidefinite programming
Semidefinite programming is a subfield of convex optimization concerned with the optimization of a linear objective functionover the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron....
or more general Convex optimization problems). There have been a few benchmarking studies comparing the various solvers