Conic optimization

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 \$

is

maximize $b^T y \$

subject to $y^T A + 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 \geq0$

External links

• Boyd, Stephen P.; Vandenberghe, Lieven (2004) (pdf). Convex Optimization. Cambridge University Press. ISBN 9780521833783. http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf. Retrieved October 15, 2011. 
• MOSEK Software capable of solving conic optimization problems.