Conic optimization

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

defined on a convex cone $C\subset X$, and an affine subspace $\mathscr{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 \mathscr{H}$ for which the number $f(x)$ is smallest.

Examples of $C$ include the positive orthant ${ℝ}_{+}^n=\{x\in {ℝ}^n:x\ge \mathrm{𝟎}\}$, positive semidefinite matrices ${𝕊}_{+}^n$, and the second-order cone $\{(x,t)\in {ℝ}^n\times ℝ:\Vert x\Vert \le t\}$. 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\le 0$

is given by

maximize $\mathrm{t}\mathrm{r}(GZ)$

subject to $\mathrm{t}\mathrm{r}(F_{i}Z)+c_i=0,i=1,\dots ,n$

$Z\ge 0$

External links

• MOSEK Software capable of solving conic optimization problems.