Content deleted Content added
Erel Segal (talk | contribs) →Equivalent formulations: Make notation lighter |
Erel Segal (talk | contribs) |
||
Line 25:
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 trace}</math> denotes the [[Trace (linear algebra)|trace]]):<blockquote><math>
\langle A,B\rangle := {\rm trace}(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
Line 212:
=== Ellipsoid method ===
The [[ellipsoid method]] is a general method for convex programming, and can be used in particular to solve SDPs. In the context of SDPs, the ellipsoid method provides the following guarantee.<ref name=":0" />{{Rp|___location=Thm.2.6.1}}Consider an SDP in the following
\begin{array}{rl}
{\displaystyle\max_{X \in \mathbb{S}^n}} & \langle C, X \rangle \\
\text{subject to} & \langle A_k, X \rangle = b_k, \quad k = 1,\ldots,m \\
& X \succeq 0.
\end{array}
</math></blockquote>Let ''L'' be the affine subspace of matrices in S<sup>n</sup> satisfying the ''m'' equational constraints; so the SDP can be written as: <math>
\max_{X\in L} \langle C,X\rangle \text{ subject to } X\succeq 0
</math>. A matrix ''X'' in S<sup>n</sup> is called ''ε-deep'' if every matrix ''Y'' in ''L'' with [[Frobenius distance]] at most ''ε'' from ''X'' satisfies the feasibility condition <math>
Y\succeq 0
</math>.
=== Interior point methods ===
| |||