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.

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

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

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

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

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

is

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

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

where ${\displaystyle C^{*}}${\displaystyle C^{*}} denotes the dual cone of ${\displaystyle C\ }${\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\ }${\displaystyle c^{T}x\ }

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

is given by

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

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

${\displaystyle Z\geq 0}${\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.

• Convex optimization

• Articles with short description
• Short description matches Wikidata
• Articles lacking in-text citations from October 2011
• All articles lacking in-text citations