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
- 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 linear program. Quadratically constrained quadratic programs can also be formulated as SOCPs by reformulating the objective function as a constraint. Semidefinite programming 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 form
This is equivalent to the SOC constraint
Example: Stochastic linear programming
Consider a stochastic linear program in inequality form
- subject to
where the parameters are independent Gaussian random vectors with mean and covariance and . This problem can be expressed as the SOCP
- subject to
Example: Stochastic second-order cone programming
We refer to second-order cone programs as deterministic second-order cone programs since data deﬁning them are deterministic. Stochastic second-order cone programs is a class of optimization problems that deﬁned to handle uncertainty in data deﬁning deterministic second-order cone programs.
Solvers and scripting (programming) languages
|AMPL||commercial||An algebraic modeling language with SOCP support|
|ECOS||GPL v3||SOCP solver for embedded applications|
|Gurobi||commercial||parallel SOCP barrier algorithm|
|JOptimizer||Apache License||Java library for convex optimization (open source)|
|OpenOpt||BSD||universal cross-platform numerical optimization framework, see its SOCP page and other problems involved. Uses NumPy arrays and SciPy sparse matrices.|
|SDPT3||GPL v2||Matlab package with primal–dual interior point methods|
|Xpress||commercial||from 7.6 release|
- Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 3, 2011.
- Alzalg, Baha (2012). Stochastic second-order cone programming: Application models. 36(10). pp. 5122–5134.
- Toh, K.C.; M.J. Todd, and R.H. Tutuncu (1999). "SDPT3 - a Matlab software package for semidefinite programming". Optimization Methods andSoftware 11: 545–581. doi:10.1080/10556789908805762.
- Alzalg, Baha (2012). "Stochastic second-order cone programming: Application models". Applied Mathematical Modeling. 36(10): 5122–5134.
- Tutuncu, R.H.; K.C. Toh, and M.J. Todd (2003). "Solving semidefinite-quadratic-linear programs using SDPT3". Mathematical Programming. Ser. B, 95: 189–217.
- |SeDuMi||GPL v3||Matlab package with primal–dual interior point methods
- Sturm, Jos F. (1999). "Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones". Optimization Methods and Software. 11-12: 625–653.