Conic optimization

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

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

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

c^T x \

subject to

Ax = b, x \in C \

maximize

b^T y \

subject to

A^T y + s= c, s \in C^* \

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

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

Semidefinite Program

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

References

↑ "Duality in Conic Programming" (PDF).

External links

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.

This article is issued from Wikipedia - version of the 4/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.