Definitions
Nearby Words

Conic optimization

Conic optimization is a subfield of convex optimization. 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\left\{H\right\}$ defined by a set of affine constraints $h_i\left(x\right) = 0$, the problem is to find the point $x$ in $C cap mathcal\left\{H\right\}$ for which the number $f\left(x\right)$ is smallest. Examples of $C$ include the positive semidefinite matrices $mathbb\left\{S\right\}^n_\left\{++\right\}$, the positive orthant $x geq mathbf\left\{0\right\}$ for $x in mathbb\left\{R\right\}^n$, and the second-order cone $left \left\{ \left(x,t\right) in mathbb\left\{R\right\}^\left\{n+1\right\} : lVert x rVert leq t right \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\left\{tr\right\} \left(GZ\right)$ subject to

$mathrm\left\{tr\right\} \left(F_i Z\right) +c_i =0,quad i=1,dots,n$

$Z geq0$