Semidefinite Programing (SDP): Difference between revisions
No edit summary |
No edit summary |
||
Line 8: | Line 8: | ||
<B>Example(s):</B> | <B>Example(s):</B> | ||
** For <math>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>b_1=11, b_2=19</math>. Then the variable <math>X</math> will be a symmetric matrix: <math>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> | ** For <math>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>b_1=11, b_2=19</math>. Then the variable <math>X</math> will be a symmetric matrix: <math>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>x_{11}+4x_{12}+6x_{13}+9x_{22}+0x_{23}+7x_{33}\\ s.t. | The SDP can be written as: Minimize <math>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> |
Revision as of 13:49, 11 January 2016
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]
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]