<p>I am interested in exact scaling of the ellipsoid method and interior point methods for solving SDPs.</p>

<p>(I am not interested in algorithms like multiplicative weights updates method.)</p>

CC BY-SA 3.0
2013-11-18T18:05:20.310Z
See some related questions:  http://cstheory.stackexchange.com/q/14770/1542 and http://cstheory.stackexchange.com/q/14548/1542
Alessandro Cosentino
CC BY-SA 3.0
2013-11-18T18:36:51.527Z
actually the ellipsoid method and combinatorial primal-dual algorithms are the *only* ways I know how to solve *some* exponential size mathematical programs.
Sasho Nikolov
CC BY-SA 3.0
2013-11-18T18:52:48.150Z
combinatorial primal-dual is a large class :). do you count mult-weight-update in that class as well ?
Suresh Venkat
CC BY-SA 3.0
2013-11-18T22:29:58.593Z
@Suresh, true :). I had multiplicative weights (or Plotkin-Shmoys-Tardos) and Edmonds' blossom algorithm in mind as examples.
Sasho Nikolov
<ds.algorithms><convex-optimization><semidefinite-programming>
Time complexity of standard semidefinite programming solvers
postasaguest
# Time complexity of standard semidefinite programming solvers

(Asked by: username_0 on 2013-11-18)

I am interested in exact scaling of the ellipsoid method and interior point methods for solving SDPs.

(I am not interested in algorithms like multiplicative weights updates method.)

**Tags:** ds.algorithms, convex-optimization, semidefinite-programming

> **Comments:**
> **username_1**: See some related questions:  http://cstheory.stackexchange.com/q/14770/1542 and http://cstheory.stackexchange.com/q/14548/1542  
> **username_2**: actually the ellipsoid method and combinatorial primal-dual algorithms are the *only* ways I know how to solve *some* exponential size mathematical programs.  
> **username_3**: combinatorial primal-dual is a large class :). do you count mult-weight-update in that class as well ?  
> **username_2**: @Suresh, true :). I had multiplicative weights (or Plotkin-Shmoys-Tardos) and Edmonds' blossom algorithm in mind as examples.  

---

## 0 answers

