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

:<math>f:C \to \mathbb R</math>

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

Examples of <math> C </math> include the positive orthant <math>\mathbb{R}_+^n = \left\{ x \in \mathbb{R}^n : \, x \geq \mathbf{0}\right\} </math>, positive semidefinite matrices <math>\mathbb{S}^n_{+}</math>, and the '''second-order cone''' <math>\left \{ (x,t) \in \mathbb{R}^{n}\times \mathbb{R} : \lVert x \rVert \leq t \right \} </math>. Often <math>f \ </math> 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 <math>c^T x \ </math> :subject to <math>Ax = b, x \in C \ </math>

:maximize <math>b^T y \ </math> :subject to <math>A^T y + s= c, s \in C^* \ </math>

where <math>C^*</math> denotes the dual cone of <math>C \ </math>.

Whilst weak duality holds in conic linear programming, strong duality does not necessarily hold.<ref name="ConicDuality" />

===Semidefinite Program=== The dual of a semidefinite program in inequality form

: minimize <math>c^T x \ </math> : subject to <math>x_1 F_1 + \cdots + x_n F_n + G \leq 0</math>

is given by

: maximize <math>\mathrm{tr}\ (GZ)\ </math> : subject to <math>\mathrm{tr}\ (F_i Z) +c_i =0,\quad i=1,\dots,n</math> : <math>Z \geq0</math>

==References== {{Reflist|refs= <ref name="ConicDuality">{{cite web|title=Duality in Conic Programming|url=https://people.smp.uq.edu.au/YoniNazarathy/teaching_projects/studentWork/Duality.pdf}}</ref> }}

==External links== * {{cite book|title=Convex Optimization|first1=Stephen P.|last1=Boyd|first2=Lieven|last2=Vandenberghe|year=2004|publisher=Cambridge University Press|isbn=978-0-521-83378-3|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf |accessdate=October 15, 2011}} * [http://www.mosek.com MOSEK] Software capable of solving conic optimization problems.

Category:Convex optimization