Conic optimization

From Wikipedia, the free encyclopedia

Conic optimization is a subfield of convex optimization that studies a class of structured convex optimization problems called conic optimization problems. A conic optimization problem consists of minimizing a convex function over the intersection of an affine subspace and a convex cone.

The class of conic optimization problems is a subclass of convex optimization problems and it includes some of the most well known classes of convex optimization problems, namely linear and semidefinite programming.

Definition

Given a real vector space X, a convex, real-valued function

$f:C\to {\mathbb R}$

defined on a convex cone $C\subset X$ , and an affine subspace ${\mathcal {H}}$ defined by a set of affine constraints $h_{i}(x)=0\$ , a conic optimization problem is to find the point $x$ in $C\cap {\mathcal {H}}$ for which the number $f(x)$ is smallest. Examples of $C$ include the positive semidefinite matrices ${\mathbb {S}}_{{+}}^{n}$ , the positive orthant $x\geq {\mathbf {0}}$ for $x\in {\mathbb {R}}^{n}$ , and the second-order cone $\left\{(x,t)\in {\mathbb {R}}^{{n+1}}:\lVert x\rVert \leq t\right\}$ . Often $f\$ is a linear function, in which case the conic optimization problem reduces to a semidefinite program, a linear program, and a second order cone program, respectively.

Duality

Certain special cases of conic optimization problems have notable closed-form expressions of their dual problems.

Conic LP

The dual of the conic linear program

minimize $c^{T}x\$

subject to $Ax=b,x\in C\$

maximize $b^{T}y\$

subject to $A^{T}y+s=c,s\in C^{*}\$

where $C^{*}$ denotes the dual cone of $C\$ .

Semidefinite Program

The dual of a semidefinite program in inequality form,

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

$x_{1}F_{1}+\cdots +x_{n}F_{n}+G\leq 0$

is given by

maximize ${\mathrm {tr}}\ (GZ)\$ subject to

${\mathrm {tr}}\ (F_{i}Z)+c_{i}=0,\quad i=1,\dots ,n$

$Z\geq 0$

External links

Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 15, 2011.
MOSEK Software capable of solving conic optimization problems.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.