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 and covariance $Sigma\_i$ and $pgeq0.5$. This problem can be expressed as the SOCP

:minimize $c^T\; x$ subject to

:

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.