Conic optimization

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 \

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 + \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

References

1. "Duality in Conic Programming".