Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 220:
</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>. Suppose all coefficients in the SDP are rational numbers. Let ''R'' be an explicitly given upper bound on the maximum [[Frobenius norm]] of a feasible solution, and ''ε>''0 a constant. 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>. Denote <math>
v_{deep} := \sup \{\langle C,X\rangle: X \text{ is } \epsilon\text{-deep} \}
</math>. The ellipsoid returns one of the following outputs:
* A matrix X* in L (that is, satisfying all linear equality constraints exactly), such that the Frobenius distance between X* and some feasible solution is at most ''ε'' (that is, approximately satisfying the inequality constraint <math>
X\succeq 0
</math>), and <math>
\langle C,X^*\rangle \geq v_{deep} -\epsilon
</math> (that is, approximately optimal objective value).
* A certificate that the problem has no ''ε-deep'' solutions (that is, the problem is approximately infeasible).
The run-time is polynomial in the binary encodings of the inputs and in log(R/''ε''), in the [[Turing machine]] model.
=== Interior point methods ===
| |||