Second-order cone programming

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}}$. Here ${\displaystyle x\in \mathbb {R} ^{n}}$ is the optimization variable. 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 quadratic program. SOCPs can be solved with great efficiency by interior point methods.

Example: Robust Linear Programming

Consider a stochastic linear program in inequality form

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

${\displaystyle P(a_{i}^{T}(x)\leq b_{i})\leq \eta ,\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 \eta \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}(\eta )\lVert \Sigma _{i}^{1/2}x\rVert _{2}\leq b_{i},\quad i=1,\dots ,m}$ 

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

External links

• Stephen Boyd and Lieven Vandenberghe, Convex Optimization (book in pdf)