Second-order cone programming

This article may be too technical for most readers to understand. Please to make it understandable to non-experts, without removing the technical details. (October 2011) (Learn how and when to remove this template 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 "second-order cone" in SOCP arises from the constraints, which are equivalent to requiring the affine function ${\displaystyle (Ax+b,c^{T}x+d)}$ to lie in the second-order cone in ${\displaystyle \mathbb {R} ^{n_{i}+1}}$.^[1]

SOCPs can be solved by interior point methods^[2] and in general, can be solved more efficiently than semidefinite programming (SDP) problems.^[3] Some engineering applications of SOCP include filter design, antenna array weight design, truss design, and grasping force optimization in robotics.^[4] 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.^[5][6][7]

Second-order cone[]

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 quadratic cone, ice-cream cone, or Lorentz cone. The 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 (Here ${\displaystyle M\succcurlyeq 0}$ means ${\displaystyle M}$ is semidefinite matrix). 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}$.

Relation with other optimization problems[]

A hierarchy of convex optimization problems. (LP: linear program, QP: quadratic program, SOCP second-order cone program, SDP: semidefinite program, CP: cone program.)

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.^[4] 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.^[4] The converse, however, is not valid: there are positive semidefinite cones that do not admit any second-order cone representation.^[3] In fact, while any closed convex semialgebraic set in the plane can be written as a feasible region of a SOCP,^[8] it is known that there exist convex semialgebraic sets that are not representable by SDPs, that is, there exist convex semialgebraic sets that can not be written as a feasible region of a SDP.^[9]

Examples[]

Quadratic constraint[]

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}}}$

Stochastic linear programming[]

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]

Stochastic second-order cone programming[]

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.

Solvers and scripting (programming) languages[]

References[]