Semidefinite Programing (SDP): Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
Line 2: | Line 2: | ||
* <B>Context:</B> | * <B>Context:</B> | ||
** <p>It is an optimization problem of the form: | ** <p>It is an optimization problem of the form: | ||
Minimize <math>C.X | Minimize <math>C.X</math> | ||
such that <math>A_i X=b_i,i=1,\dots,m \\ X \geq 0</math></p> | such that <math>A_i X=b_i,i=1,\dots,m \\ X \geq 0</math></p> | ||
<p>where <math>C</math> is a symmetric matrix.The objective function is the linear function <math>C.X</math> | <p>where <math>C</math> is a symmetric matrix.The objective function is the linear function <math>C.X</math> | ||
and there are m linear equations that X must satisfy, namely <math>A_i X = b_i,i =1,...,m.</math></p> | and there are m linear equations that X must satisfy, namely <math>A_i X = b_i,i =1,...,m.</math></p> | ||
<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}</math> |
Revision as of 13:33, 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} }[/math]