Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) |
||
Line 214:
== Algorithms for solving SDPs ==
There are several types of algorithms for solving SDPs. These algorithms output the value of the SDP up to an additive error <math>\epsilon</math> in time that is polynomial in the program description size and <math>\log (1/\epsilon)</math>.
=== 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 standard form:<blockquote>Maximize </blockquote>
=== Interior point methods ===
| |||