Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 236:
Note that, in general, ''R'' may be doubly-exponential in ''n.'' In that case, the run-time guarantee of the ellipsoid method is exponential in ''n''. But in most applications, ''R'' is not so huge. In these cases, the ellipsoid method is the only known method that guarantees polynomial runtime in the Turing machine model.''<ref name=":0" />''{{Rp|___location=|page=23}} But in practice, its performance is not so good.
=== Hazan's algorithm ===
[[Elad Hazan]]<ref>{{Cite journal |last=Hazan |first=Elad |date=2008 |editor-last=Laber |editor-first=Eduardo Sany |editor2-last=Bornstein |editor2-first=Claudson |editor3-last=Nogueira |editor3-first=Loana Tito |editor4-last=Faria |editor4-first=Luerbio |title=Sparse Approximate Solutions to Semidefinite Programs |url=https://link.springer.com/chapter/10.1007/978-3-540-78773-0_27 |journal=LATIN 2008: Theoretical Informatics |series=Lecture Notes in Computer Science |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=306–316 |doi=10.1007/978-3-540-78773-0_27 |isbn=978-3-540-78773-0}}</ref> has developed a simple algorithm for solving SDPs with the additional constraint that the [[Trace (linear algebra)|trace]] of the variables matrix must be 1. Specifically, his algorithm solves problems of the form:
<math>
\begin{array}{rl}
{\displaystyle\max_{X \in \mathbb{S}^n}} & \langle C, X \rangle \\
\text{subject to} & \langle A_k, X \rangle \leq b_k, \quad k = 1,\ldots,m \\
& \operatorname{trace}(X) = 1,
\\
& X \succeq 0.
\end{array}
</math>
This can be seen as a maximizing a linear objective over the [[spectraplex]].
Let OPT be the optimal value of this problem, and ''ε>''0 a constant. Hazan's algorithm returns one of the following:''<ref name=":0" />''{{Rp|___location=Thm.5.1.1|page=}}
* A matrix in the spectraplex such that <math>
OPT - \langle C,X\rangle \leq 2\epsilon \cdot \|C\| \text{ and } \langle A_i , X\rangle - bi \leq \epsilon\cdot \|A_i\|
</math> (that is, the solution is approximately optimal and satisfies the linear inequalities approximately);
* A certificate that there is no feasible solution.
The run-time in the [[Real RAM]] model is, [[With high probability|with high probability,]] in <math>
O\left (\frac{N \cdot \log{n}\cdot \log{m} \cdot log(1/\epsilon)}{\epsilon^3}\right)
</math>, where ''N'' is input size (number of nonzero entries in the matrices), ''n'' is the number of variables, and ''m'' is the number of inequality constraints. Note that the runtime is polynomial in 1/''ε'' rather than log(1/''ε''). However, in practice it runs quite fast.
Hazan's algorithm uses a sub-routine for solving the '''feasibility problem''' - deciding whether a given SDP is feasible:<blockquote><math>
\begin{array}{rl}
{\displaystyle \text{find } {X \in \mathbb{S}^n}} & \\
\text{subject to} & \langle A_k, X \rangle \leq b_k, \quad k = 1,\ldots,m \\
& \operatorname{trace}(X) = 1,
\\
& X \succeq 0.
\end{array}
</math></blockquote>There is an algorithm that, for any given ''ε>''0, returns one of the following:''<ref name=":0" />''{{Rp|___location=Thm.5.3.2|page=}}
* An ''ε''-approximately-feasible solution: a solution ''X'' in the spectraplex, for which <math>
\langle A_i , X\rangle - bi \leq \epsilon
</math> for all ''i'' in 1,...,''m''.
* A certificate that no feasible solution exists.
The run-time in the [[Real RAM]] model is, [[With high probability|with high probability,]] in <math>
O\left (\frac{N \cdot \log{n}\cdot \log{m} \cdot }{\epsilon^3}\right)
</math>. The algorithm is applied in a [[binary search]] style to find an approximately-optimal solution.
=== Interior point methods ===
| |||