Semidefinite Programming Task
A Semidefinite Programming Task is a convex optimization task that accepts a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space.
- AKA: SDP.
- Context:
- It can be expressed as [math]\displaystyle{ \operatorname{min} C.X }[/math] such that [math]\displaystyle{ A_i X=b_i,i=1,\dots,m \\ X \geq 0 }[/math], where [math]\displaystyle{ C }[/math] is a symmetric matrix, [math]\displaystyle{ C.X }[/math] is a linear objective function, and there are [math]\displaystyle{ m }[/math] linear equations that [math]\displaystyle{ X }[/math] must satisfy, namely [math]\displaystyle{ A_i X = b_i,i =1,...,m. }[/math].
- It can be solved by a Semidefinite Programming Solving System (that implements a [[semidefinite programming solving algorithm, such as a primal-dual algorithm).
- Example(s):
- For [math]\displaystyle{ C=\begin{bmatrix}1 & 2 & 3 \\ 2 & 9 & 0 \\ 3 & 0 & 7\end{bmatrix},A_1=\begin{bmatrix} 1 & 0 & 1 \\ 0 & 3 & 7 \\ 1 & 7 & 5 \end{bmatrix}, A_2=\begin{bmatrix} 0 & 2 & 8 \\ 2 & 6 & 0 \\ 8 & 0 & 4 \end{bmatrix} }[/math] and [math]\displaystyle{ b_1=11, b_2=19 }[/math]. Then the variable [math]\displaystyle{ X }[/math] will be a symmetric matrix: [math]\displaystyle{ X=\begin{bmatrix}x_{11}&x_{12}&x_{13}\\x_{21}&x_{22}&x_{23}\\x_{31}&x_{32}&x_{33}\end{bmatrix},C.X=x_{11}+2x_{12}+3x_{13}+2x_{21}+9x_{22}+0x_{23}+3x_{31}+0x_{32}+7x_{33}=x_{11}+4x_{12}+6x_{13}+9x_{22}+0x_{23}+7x_{33} }[/math]
The SDP can be written as: Minimize [math]\displaystyle{ x_{11}+4x_{12}+6x_{13}+9x_{22}+0x_{23}+7x_{33}\\ s.t. x_{11}+0x_{12}+2x_{13}+3x_{22}+14x_{23}+5x_{33}=11 \\ 0x_{11}+4x_{12}+16x_{13}+6x_{22}+0x_{23}+4x_{33}=19 \\ X=\begin{bmatrix}x_{11}&x_{12}&x_{13}\\x_{21}&x_{22}&x_{23}\\x_{31}&x_{32}&x_{33}\end{bmatrix} \geq 0 }[/math]
- For [math]\displaystyle{ C=\begin{bmatrix}1 & 2 & 3 \\ 2 & 9 & 0 \\ 3 & 0 & 7\end{bmatrix},A_1=\begin{bmatrix} 1 & 0 & 1 \\ 0 & 3 & 7 \\ 1 & 7 & 5 \end{bmatrix}, A_2=\begin{bmatrix} 0 & 2 & 8 \\ 2 & 6 & 0 \\ 8 & 0 & 4 \end{bmatrix} }[/math] and [math]\displaystyle{ b_1=11, b_2=19 }[/math]. Then the variable [math]\displaystyle{ X }[/math] will be a symmetric matrix: [math]\displaystyle{ X=\begin{bmatrix}x_{11}&x_{12}&x_{13}\\x_{21}&x_{22}&x_{23}\\x_{31}&x_{32}&x_{33}\end{bmatrix},C.X=x_{11}+2x_{12}+3x_{13}+2x_{21}+9x_{22}+0x_{23}+3x_{31}+0x_{32}+7x_{33}=x_{11}+4x_{12}+6x_{13}+9x_{22}+0x_{23}+7x_{33} }[/math]
- See: Negative-Definite Matrix, Affine Space, Spectrahedron, Combinatorial Optimization, Linear Matrix Inequality, Conic Optimization.
References
2016
- (Wikipedia, 2016) ⇒ http://en.wikipedia.org/wiki/semidefinite_programming Retrieved:2016-1-11.
- Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a [[linear
objective function]] (an objective function is a user-specified function that the user wants to minimize or maximize)
over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.
Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled or approximated as semidefinite programming problems. In automatic control theory, SDPs are used in the context of linear matrix inequalities. SDPs are in fact a special case of cone programming and can be efficiently solved by interior point methods.
All linear programs can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Semidefinite programming has been used in the optimization of complex systems. In recent years, some quantum query complexity problems have been formulated in term of semidefinite programs.