Second-order cone programming

A second-order cone program (SOCP) is a convex optimization problem of the form

:minimize $$f^T x subject to

:$$lVert A_i x + b_i Vert_2 leq c_i^T x + d_i,quad i = 1,dots,m

:$$Fx = g

where the problem parameters are $$f in mathbb{R}^n, A_i in mathbb{R}^n_i} imes n}, b_i in mathbb{R}^{n_I}, c_i in mathbb{R}^n, d_i in mathbb{R}, F in mathbb{R}^{p imes n}, and $$g in mathbb{R}^p. Here $$xinmathbb{R}^n is the optimization variable. When $$A_i = 0 for $$i = 1,dots,m, the SOCP reduces to a linear program. When $$c_i = 0 for $$i = 1,dots,m, the SOCP is equivalent to a convex Quadratically constrained quadratic program. SOCPs can be solved with great efficiency by interior point methods.

Example: Stochastic Programming

Consider a stochastic linear program in inequality form

:minimize $$c^T x subject to

: $$P(a_i^T(x) geq b_i) geq p, quad i = 1,dots,m

where the parameters $$a_i are independent Gaussian random vectors with mean $$ar{a}_i and covariance $$Sigma_i and $$pgeq0.5. This problem can be expressed as the SOCP

:minimize $$c^T x subject to

: $$ar{a}_i^T (x) + Phi^{-1}(1-p) lVert Sigma_i^{1/2} x Vert_2 geq b_i , quad i = 1,dots,m

where $$Phi^{-1} is the inverse error function.

External links

* Stephen Boyd and Lieven Vandenberghe, [http://www.stanford.edu/~boyd/cvxbook/ Convex Optimization] (book in pdf).

;Software
* [http://www.mosek.com/ MOSEK] — The first commercially available software package for solution SOCP.
* [http://www.ilog.com/products/cplex/product/algorithms.cfm CPLEX] — Full-featured solver for large scale linear, quadratic, and integer programming problems, including SOCP.