Conic optimization

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Conic optimization is a subfield of convex optimization that studies a class of structured convex optimization problems called conic optimization problems. A conic optimization problem consists of minimizing a convex function over the intersection of an affine subspace and a convex cone.

The class of conic optimization problems is a subclass of convex optimization problems and it includes some of the most well known classes of convex optimization problems, namely linear and semidefinite programming.

Definition[edit]

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

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

Conic LP[edit]

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 A^T y + s= c, s \in C^* \

where C^* denotes the dual cone of C \ .

Semidefinite Program[edit]

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{tr}\ (GZ)\ subject to

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

External links[edit]