Second-order cone programming

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (October 2011) (Learn how and when to remove this message)

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

minimize ${\displaystyle \ f^{T}x\ }$

subject to

${\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i},\quad i=1,\dots ,m}$

${\displaystyle Fx=g\ }$

where the problem parameters are ${\displaystyle f\in \mathbb {R} ^{n},\ A_{i}\in \mathbb {R} ^{{n_{i}}\times n},\ b_{i}\in \mathbb {R} ^{n_{i}},\ c_{i}\in \mathbb {R} ^{n},\ d_{i}\in \mathbb {R} ,\ F\in \mathbb {R} ^{p\times n}}$, and ${\displaystyle g\in \mathbb {R} ^{p}}$. ${\displaystyle x\in \mathbb {R} ^{n}}$ is the optimization variable. ${\displaystyle \lVert x\rVert _{2}}$ is the Euclidean norm and ${\displaystyle ^{T}}$ indicates transpose.^[1]

The name "second-order cone programming" comes from the nature of the individual constraints, which are each of the form:

${\displaystyle \lVert Ax+b\rVert _{2}\leq c^{T}x+d}$

These each define a subspace that is bounded by an inequality based on a second-order polynomial function defined on the optimization variable ${\displaystyle x}$; this can be shown to define a convex cone, hence the name "second-order cone".^[2] By the definition of convex cones, their intersection can also be shown to be a convex cone, although not necessarily one that can be defined by a single second-order inequality. See below for a more detailed treatment.

SOCPs can be solved by interior point methods^[3] and in general, can be solved more efficiently than semidefinite programming (SDP) problems.^[4] Some engineering applications of SOCP include filter design, antenna array weight design, truss design, and grasping force optimization in robotics.^[5] Applications in quantitative finance include portfolio optimization; some market impact constraints, because they are not linear, cannot be solved by quadratic programming but can be formulated as SOCP problems.^[6][7][8]

The standard or unit second-order cone of dimension ${\displaystyle n+1}$ is defined as

${\displaystyle {\mathcal {C}}_{n+1}=\left\{{\begin{bmatrix}x\\t\end{bmatrix}}{\Bigg |}x\in \mathbb {R} ^{n},t\in \mathbb {R} ,\|x\|_{2}\leq t\right\}}$.

The second-order cone is also known by the names quadratic cone or ice-cream cone or Lorentz cone. For example, the standard second-order cone in ${\displaystyle \mathbb {R} ^{3}}$ is

${\displaystyle \left\{(x,y,z){\Big |}{\sqrt {x^{2}+y^{2}}}\leq z\right\}}$.

The set of points satisfying a second-order cone constraint is the inverse image of the unit second-order cone under an affine mapping:

${\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}A_{i}\\c_{i}^{T}\end{bmatrix}}x+{\begin{bmatrix}b_{i}\\d_{i}\end{bmatrix}}\in {\mathcal {C}}_{n_{i}+1}}$

and hence is convex.

The second-order cone can be embedded in the cone of the positive semidefinite matrices since

${\displaystyle ||x||\leq t\Leftrightarrow {\begin{bmatrix}tI&x\\x^{T}&t\end{bmatrix}}\succcurlyeq 0,}$

i.e., a second-order cone constraint is equivalent to a linear matrix inequality. The nomenclature here can be confusing; here ${\displaystyle M\succcurlyeq 0}$ means ${\displaystyle M}$ is a semidefinite matrix: that is to say

${\displaystyle x^{T}Mx\geq 0{\text{ for all }}x\in \mathbb {R} ^{n}}$

which is not a linear inequality in the conventional sense.

Similarly, we also have,

${\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}(c_{i}^{T}x+d_{i})I&A_{i}x+b_{i}\\(A_{i}x+b_{i})^{T}&c_{i}^{T}x+d_{i}\end{bmatrix}}\succcurlyeq 0}$.

When ${\displaystyle A_{i}=0}$ for ${\displaystyle i=1,\dots ,m}$, the SOCP reduces to a linear program. When ${\displaystyle c_{i}=0}$ for ${\displaystyle i=1,\dots ,m}$, the SOCP is equivalent to a convex quadratically constrained linear program.

Convex quadratically constrained quadratic programs can also be formulated as SOCPs by reformulating the objective function as a constraint.^[5] 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.^[5] The converse, however, is not valid: there are positive semidefinite cones that do not admit any second-order cone representation.^[4]

Any closed convex semialgebraic set in the plane can be written as a feasible region of a SOCP,.^[9] However, it is known that there exist convex semialgebraic sets of higher dimension that are not representable by SDPs; that is, there exist convex semialgebraic sets that can not be written as the feasible region of a SDP (nor, a fortiori, as the feasible region of a SOCP).^[10]

Consider a convex quadratic constraint of the form

${\displaystyle x^{T}Ax+b^{T}x+c\leq 0.}$

This is equivalent to the SOCP constraint

${\displaystyle \lVert A^{1/2}x+{\frac {1}{2}}A^{-1/2}b\rVert \leq \left({\frac {1}{4}}b^{T}A^{-1}b-c\right)^{\frac {1}{2}}}$

Consider a stochastic linear program in inequality form

minimize ${\displaystyle \ c^{T}x\ }$

subject to

${\displaystyle \mathbb {P} (a_{i}^{T}x\leq b_{i})\geq p,\quad i=1,\dots ,m}$

where the parameters ${\displaystyle a_{i}\ }$ are independent Gaussian random vectors with mean ${\displaystyle {\bar {a}}_{i}}$ and covariance ${\displaystyle \Sigma _{i}\ }$ and ${\displaystyle p\geq 0.5}$. This problem can be expressed as the SOCP

minimize ${\displaystyle \ c^{T}x\ }$

subject to

${\displaystyle {\bar {a}}_{i}^{T}x+\Phi ^{-1}(p)\lVert \Sigma _{i}^{1/2}x\rVert _{2}\leq b_{i},\quad i=1,\dots ,m}$

where ${\displaystyle \Phi ^{-1}(\cdot )\ }$ is the inverse normal cumulative distribution function.^[1]

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.^[11]

Other modeling examples are available at the MOSEK modeling cookbook.^[12]

• Power cones are generalizations of quadratic cones to powers other than 2.^[15]