|
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]], 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]], 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 ===
=== Approximate methods ===
Algorithms that solve SDPs approximately have been proposed as well. The main goal of such methods is to achieve lower complexity in applications where approximate solutions are sufficient and complexity must be minimal. A prominent method that has been used for data detection in multiple-input multiple-output (MIMO) wireless systems is Triangular Approximate SEmidefinite Relaxation (TASER),<ref>{{Cite journal|last1=Castañeda|first1=O.|last2=Goldstein|first2=T.|last3=Studer|first3=C.|date=December 2016|title=Data Detection in Large Multi-Antenna Wireless Systems via Approximate Semidefinite Relaxation|journal=IEEE Transactions on Circuits and Systems I: Regular Papers|volume=63|issue=12|pages=2334–2346|doi=10.1109/TCSI.2016.2607198|arxiv=1609.01797|hdl=20.500.11850/448631|issn=1558-0806|doi-access=free}}</ref> which operates on the Cholesky decomposition factors of the semidefinite matrix instead of the semidefinite matrix. This method calculates approximate solutions for a max-cut-like problem that are often comparable to solutions from exact solvers but in only 10-20 algorithm iterations. [[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 an approximate algorithm for solving SDPs with the additional constraint that the [[Trace (linear algebra)|trace]] of the variables matrix must be 1.
== Preprocessing algorithms ==
| 