Samiksha Jaiswal (Editor)

Conic optimization

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

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 → R

defined on a convex cone C ⊂ X , and an affine subspace H defined by a set of affine constraints h i ( x ) = 0   , a conic optimization problem is to find the point x in C ∩ H for which the number f ( x ) is smallest.

Examples of C include the positive orthant R + n = { x ∈ R n : x ≥ 0 } , positive semidefinite matrices S + n , and the second-order cone { ( x , t ) ∈ R n × R : ∥ x ∥ ≤ t } . 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 A x = b , x ∈ C  

is

maximize b T y   subject to A T y + s = c , s ∈ 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 ≤ 0

is given by

maximize t r   ( G Z )   subject to t r   ( F i Z ) + c i = 0 , i = 1 , … , n Z ≥ 0

References

Conic optimization Wikipedia
(Text) CC BY-SA