Second-order cone programming

From Wikipedia, the free encyclopedia

This article or section is in need of attention from an expert on the subject.

WikiProject Mathematics or the Mathematics Portal may be able to help recruit one.

If a more appropriate WikiProject or portal exists, please adjust this template accordingly.

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: 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 $\bar{a}_i$ and covariance $\Sigma_i \$ and $p\geq0.5$ . This problem can be expressed as the SOCP