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.1
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}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.
References
"Duality in Conic Programming" (PDF). https://people.smp.uq.edu.au/YoniNazarathy/teaching_projects/studentWork/Duality.pdf ↩