Conic optimization

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (October 2011) (Learn how and when to remove this message)

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.

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

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

defined on a convex cone ${\displaystyle C\subset X}$, and an affine subspace ${\displaystyle {\mathcal {H}}}$ defined by a set of affine constraints ${\displaystyle h_{i}(x)=0\ }$, a conic optimization problem is to find the point ${\displaystyle x}$ in ${\displaystyle C\cap {\mathcal {H}}}$ for which the number ${\displaystyle f(x)}$ is smallest.

Examples of ${\displaystyle C}$ include the positive orthant ${\displaystyle \mathbb {R} _{+}^{n}=\left\{x\in \mathbb {R} ^{n}:\,x\geq \mathbf {0} \right\}}$, positive semidefinite matrices ${\displaystyle \mathbb {S} _{+}^{n}}$, and the second-order cone ${\displaystyle \left\{(x,t)\in \mathbb {R} ^{n}\times \mathbb {R} :\lVert x\rVert \leq t\right\}}$. Often ${\displaystyle 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.

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

The dual of the conic linear program

minimize ${\displaystyle c^{T}x\ }$

subject to ${\displaystyle Ax=b,x\in C\ }$

is

maximize ${\displaystyle b^{T}y\ }$

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

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

Whilst weak duality holds in conic linear programming, strong duality does not necessarily hold.^[1]

The dual of a semidefinite program in inequality form

minimize ${\displaystyle c^{T}x\ }$

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

is given by

maximize ${\displaystyle \mathrm {tr} \ (GZ)\ }$

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

${\displaystyle Z\geq 0}$

• 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.