Conic programming

Conic optimization is a subfield of convex optimization that studies problems consisting of minimizing a convex function over the intersection of an affine subspace and a convex cone.

The class of conic optimization problems 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$ 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$ for which the number $f(x)$ is smallest.

Examples of $C$ include the positive orthant $\mathbb_+^n = \left\$, positive semidefinite matrices $\mathbb^n_$, and the second-order cone $\left \$. Often $f \$ is a linear function, in which case the conic optimization problem reduces to a linear program, a semidefinite 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 \$

is

:maximize $b^T y \$
:subject to $A^T y + s= c, s \in C^* \$

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

Whilst weak duality holds in conic linear programming, strong duality does not necessarily hold.

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\ (GZ)\$
: subject to $\mathrm\ (F_i Z) +c_i =0,\quad i=1,\dots,n$
: $Z \geq0$

References

External links

* {{cite book, title=Convex Optimization, first1=Stephen P., last1=Boyd, first2=Lieven, last2=Vandenberghe, year=2004, publisher=Cambridge University Press, isbn=978-0-521-83378-3, url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf , accessdate=October 15, 2011

MOSEK
Software capable of solving conic optimization problems.

Convex optimization