Second order cone programming

Poll without page-refresh

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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.

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

minimize $\ c^T x \$ subject to

$\bar{a}_i^T (x) + \Phi^{-1}(1-p) \lVert \Sigma_i^{1/2} x \rVert_2 \geq b_i , \quad i = 1,\dots,m$

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

External links

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

Software

MOSEK — The first commercially available software package for solution SOCP.
CPLEX — Full-featured solver for large scale linear, quadratic, and integer programming problems, including SOCP.

This mathematics-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "http://en.wikipedia.org/wiki/Second-order_cone_programming"

Categories: Mathematical optimization | Mathematics stubs

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car

This site monitored by SitePinger.net