Semidefinite programming: Difference between revisions

Content deleted Content added
Equivalent formulations: Make notation lighter
Line 24:
An <math>n \times n</math> matrix <math>M</math> is said to be [[Positive-definite matrix#Positive-semidefinite|positive semidefinite]] if it is the [[Gram matrix]] of some vectors (i.e. if there exist vectors <math>x^1, \ldots, x^n</math> such that <math>m_{i,j}=x^i \cdot x^j</math> for all <math>i,j</math>). If this is the case, we denote this as <math>M \succeq 0</math>. Note that there are several other equivalent definitions of being positive semidefinite, for example, positive semidefinite matrices are [[self-adjoint]] matrices that have only non-negative [[Eigenvalues and eigenvectors|eigenvalues]].
 
Denote by <math>\mathbb{S}^n</math> the space of all <math>n \times n</math> real symmetric matrices. The space is equipped with the [[Inner product space|inner product]] (where <math>{\rm trtrace}</math> denotes the [[Trace (linear algebra)|trace]]):<blockquote><math>
\langle A,B\rangle_{\mathbb{S}^n}rangle = {\rm trtrace}(A^T B) = \sum_{i=1,j=1}^n
<math>
\langle A,B\rangle_{\mathbb{S}^n} = {\rm tr}(A^T B) = \sum_{i=1,j=1}^n
A_{ij}B_{ij}.
</math></blockquote>We can rewrite the mathematical program given in the previous section equivalently as
</math>
 
We can rewrite the mathematical program given in the previous section equivalently as
 
:<math>
\begin{array}{rl}
{\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n}rangle \\
\text{subject to} & \langle A_k, X \rangle_{\mathbb{S}^n}rangle \leq b_k, \quad k = 1,\ldots,m \\
& X \succeq 0.
\end{array}
Line 42 ⟶ 39:
where entry <math>i,j</math> in <math>C</math> is given by <math>\frac{c_{i,j} + c_{j,i}}{2}</math> from the previous section and <math>A_k</math> is a symmetric <math>n \times n</math> matrix having <math>i,j</math>th entry <math>\frac{a_{i,j,k}+a_{j,i,k}}{2}</math> from the previous section. Thus, the matrices <math>C</math> and <math>A_k</math> are symmetric and the above inner products are well-defined.
 
Note that if we add [[slack variable]]s appropriately, this SDP can be converted to onean of the''equational form'':
 
:<math>
\begin{array}{rl}
{\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n}rangle \\
\text{subject to} & \langle A_k, X \rangle_{\mathbb{S}^n}rangle = b_k, \quad k = 1,\ldots,m \\
& X \succeq 0.
\end{array}
Line 62 ⟶ 59:
:<math>
\begin{array}{rl}
{\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n}rangle \\
\text{subject to} & \langle A_i, X \rangle_{\mathbb{S}^n}rangle = b_i, \quad i = 1,\ldots,m \\
& X \succeq 0
\end{array}
Line 71 ⟶ 68:
:<math>
\begin{array}{rl}
{\displaystyle\max_{y \in \mathbb{R}^m}} & \langle b,^T y \rangle_{\mathbb{R}^m} \\
\text{subject to} & {\displaystyle\sum_{i=1}^m} y_i A_i \preceq C
\end{array}
Line 82 ⟶ 79:
The [[weak duality]] theorem states that the value of the primal SDP is at least the value of the dual SDP. Therefore, any feasible solution to the dual SDP lower-bounds the primal SDP value, and conversely, any feasible solution to the primal SDP upper-bounds the dual SDP value. This is because
:<math>
\langle C, X \rangle - \langle b,^T y \rangle
= \langle C, X \rangle - \sum_{i=1}^m y_i b_i
= \langle C, X \rangle - \sum_{i=1}^m y_i \langle A_i, X \rangle
Line 96 ⟶ 93:
feasible (i.e., there exists
<math>X_0\in\mathbb{S}^n, X_0\succ 0</math> such that <math>\langle
A_i,X_0\rangle_{\mathbb{S}^n}rangle = b_i</math>, <math>i=1,\ldots,m</math>). Then there is an optimal solution <math>y^*</math> to (D-SDP) and
:<math>\langle C,X^*\rangle_{\mathbb{S}^n}rangle = \langleb^T b,y^*\rangle_{\R^m}.</math>
Then there is an optimal solution <math>y^*</math> to (D-SDP) and
:<math>\langle C,X^*\rangle_{\mathbb{S}^n} = \langle b,y^*\rangle_{\R^m}.</math>
 
(ii) Suppose the dual problem (D-SDP) is bounded above and strictly