Second order cone programming

From Wikipedia, the free encyclopedia

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 \rVert_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}\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 $g \in \mathbb{R}^p$ . Here $x\in\mathbb{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.

[edit] Example: Robust Linear Programming

Consider a stochastic linear program in inequality form

minimize $\ c^T x \$ subject to

$P(a_i^T(x) \leq b_i) \leq \eta, \quad i = 1,\dots,m$

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