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 is an optimization problem of the form:

Minimize [math]\displaystyle{ 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.The objective function is the linear function [math]\displaystyle{ C.X }[/math] 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 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]

• 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.

---