Conic optimization

Short description: Subfield of convex 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]\displaystyle{ f:C \to \mathbb R }[/math]

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

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

subject to [math]\displaystyle{ Ax = b, x \in C \ }[/math]

is

maximize [math]\displaystyle{ b^T y \ }[/math]

subject to [math]\displaystyle{ A^T y + s= c, s \in C^* \ }[/math]

where [math]\displaystyle{ C^* }[/math] denotes the dual cone of [math]\displaystyle{ C \ }[/math].

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 [math]\displaystyle{ c^T x \ }[/math]

subject to [math]\displaystyle{ x_1 F_1 + \cdots + x_n F_n + G \leq 0 }[/math]

is given by

maximize [math]\displaystyle{ \mathrm{tr}\ (GZ)\ }[/math]

subject to [math]\displaystyle{ \mathrm{tr}\ (F_i Z) +c_i =0,\quad i=1,\dots,n }[/math]

[math]\displaystyle{ Z \geq0 }[/math]

External links

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3. https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf. Retrieved October 15, 2011. 
• MOSEK Software capable of solving conic optimization problems.