Semidefinite Programing (SDP)

Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space.

• 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 m linear equations that X must satisfy, namely [math]\displaystyle{ A_i X = b_i,i =1,...,m. }[/math]

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]