Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) →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
▲ \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▼
▲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 \
\text{subject to} & \langle A_k, X \
& 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
:<math>
\begin{array}{rl}
{\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \
\text{subject to} & \langle A_k, X \
& X \succeq 0.
\end{array}
Line 62 ⟶ 59:
:<math>
\begin{array}{rl}
{\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \
\text{subject to} & \langle A_i, X \
& X \succeq 0
\end{array}
Line 71 ⟶ 68:
:<math>
\begin{array}{rl}
{\displaystyle\max_{y \in \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 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\
▲:<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
|