Conic optimization explained

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

f:C \to R C \subset X , and an affine subspace l{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 l{H} for which the number f(x) is smallest.

Examples of

C include the positive orthant R ^{n} _{+} = \left\{ x \in R ^{n} : x \geq 0 \right\} , positive semidefinite matrices S ^{n} _{+} , and the second-order cone \left \{ (x,t) \in R ^{n} x 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

is

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.

Semidefinite Program

The dual of a semidefinite program in inequality form

minimize

c ^{T} x

subject to

x _{1} F _{1} + … + x _{n} F _{n} + G \leq 0

is given by

maximize

tr (GZ)

subject to

tr (F _{i} Z) + c _{i} =0 , i =1 , ... ,n Z \geq 0

External links

• Book: Convex Optimization. Stephen P.. Boyd. Lieven. Vandenberghe. 2004. Cambridge University Press. 978-0-521-83378-3. October 15, 2011.
• MOSEK Software capable of solving conic optimization problems.