Misplaced Pages

Conic optimization

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Conic programming) Subfield of convex optimization
This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (October 2011) (Learn how and when to remove this message)

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 → R {\displaystyle f:C\to \mathbb {R} }

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

Examples of C {\displaystyle C} include the positive orthant R + n = { x ∈ R n : x ≥ 0 } {\displaystyle \mathbb {R} _{+}^{n}=\left\{x\in \mathbb {R} ^{n}:\,x\geq \mathbf {0} \right\}} , positive semidefinite matrices S + n {\displaystyle \mathbb {S} _{+}^{n}} , and the second-order cone { ( x , t ) ∈ R n × R : ‖ x ‖ ≤ t } {\displaystyle \left\{(x,t)\in \mathbb {R} ^{n}\times \mathbb {R} :\lVert x\rVert \leq t\right\}} . Often f   {\displaystyle 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   {\displaystyle c^{T}x\ }
subject to A x = b , x ∈ C   {\displaystyle Ax=b,x\in C\ }

is

maximize b T y   {\displaystyle b^{T}y\ }
subject to A T y + s = c , s ∈ C ∗   {\displaystyle A^{T}y+s=c,s\in C^{*}\ }

where C ∗ {\displaystyle C^{*}} denotes the dual cone of C   {\displaystyle 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   {\displaystyle c^{T}x\ }
subject to x 1 F 1 + ⋯ + x n F n + G ≤ 0 {\displaystyle x_{1}F_{1}+\cdots +x_{n}F_{n}+G\leq 0}

is given by

maximize t r   ( G Z )   {\displaystyle \mathrm {tr} \ (GZ)\ }
subject to t r   ( F i Z ) + c i = 0 , i = 1 , … , n {\displaystyle \mathrm {tr} \ (F_{i}Z)+c_{i}=0,\quad i=1,\dots ,n}
Z ≥ 0 {\displaystyle Z\geq 0}

References

  1. "Duality in Conic Programming" (PDF).

External links

Category: