<p>I'm not familiar with details of the ellipsoid method specifically for semi-definite programs, but even for <em>linear</em> programs, analysis of the ellipsoid method is pretty subtle.</p>

<ul>
<li><p>First, one needs to bound the number of iterations of the <em>ideal</em> ellipsoid algorithm.  Let $E_i$ be the ellispoid used in the $i$th iteration of the ellipsoid algorithm, and let $c_i$ be its centroid.  In the ideal algorithm, a separation/membership oracle gives you a halfspace $h_i$ that contains the optimum point $x^*$ but not the centroid $c_i$.  The next ellipsoid $E_{i+1}$ is the smallest ellipsoid containing $E_i\cap h_i$.  For each $i$, we have $vol(E_{i+1}) &lt; (1-\frac{1}{n})\cdot vol(E_i)$, where $n$ is the dimension.  Thus, given a reasonable starting ellipsoid, the number of iterations is polynomial in $n$ and $\log(1/\varepsilon)$.  Computing $E_{i+1}$ from $E_i$ and $h_i$ requires (crudely) $O(n^2)$ arithmetic operations.  So the number of arithmetic operations is also polynomial in $n$ and $\log(1/\varepsilon)$.</p></li>
<li><p>However, some of those arithmetic operations are square roots!  It follows that the coefficients of the ideal ellipsoid $E_i$ are irrational numbers of degree $2^i$, and so there's no hope of actually computing $E_{i+1}$ <em>exactly</em> in any reasonable time.  So instead, one computes a close outer approximation $\tilde{E}_i \supset E_i$ at each iteration using finite precision arithmetic.  Grötschel, Lovasz, and Schrijver prove that if one uses (say) $10i$ bits of precision in the $i$th iteration, we still have $vol(\tilde E_{i+1}) &lt; O(1-\frac{1}{n})\cdot vol(\tilde E_i)$, so the number of iterations increases by at most a constant factor.  But now each arithmetic operation during the $i$th iteration (including the operations performed by the separation oracle) requires $O(i~\text{polylog}~i)$ time.</p></li>
</ul>

<p>Altogether, the total running time of the ellipsoid method is <em>very</em> roughly the <em>square</em> of the number of arithmetic operations.  Since the number of arithmetic operations is polynomial in $n$ and $\log(1/\varepsilon)$, so is the running time.</p>

CC BY-SA 3.0
2012-12-21T01:48:03.550Z
Thanks for the answer. If I am tallying correctly, this is what I have (very roughly): $\sum_{i = 1}^{\text{n. of iterations}} O(n^2)$ (n. of arithmetic operations) $\times O(i \operatorname{polylog}i)$ (time for each arithmetic operation). I still don't have a bound on the number of iterations, except that is polynomial in $n$ and $\log(1/\epsilon)$. Perhaps I wasn't very clear in my question, but I am interested in a more precise bound also for the number of iterations (something like: $n$, $n^2$, ...).
Alessandro Cosentino
CC BY-SA 3.0
2012-12-21T01:50:15.313Z
One more thing: shouldn't the number of constraints also appear somewhere in the analysis? Also, is this specific to linear programs?
Alessandro Cosentino
CC BY-SA 3.0
2012-12-21T14:03:55.340Z
You also have to take the running time of the separation oracle into account; that's where the number of constraints shows up.  For explicit LPs, the separation oracle just tries the constraints one at a time.  For implicitly represented LPs, it's more complicated.
Jeffε
CC BY-SA 3.0
2012-12-20T03:21:31.390Z
2012-12-20T03:21:31.390Z
Jeffε
<p>This is a followup of a recent question asked by A. Pal: <a href="https://cstheory.stackexchange.com/q/14548/1542">Solving semidefinite programs in polynomial time</a>.</p>

<p>I am still puzzling over the actual running time of algorithms that compute the solution of  a semidefinite program (SDP). As Robin pointed out in <a href="https://cstheory.stackexchange.com/questions/14548/solving-semidefinite-programs-in-polynomial-time#comment39404_14548">his comment</a> to the above question, SDPs cannot be solved in polynomial time in general.</p>

<p>It turns out that, if we define our SDP carefully and we impose a condition on how well-bounded the primal feasible region is, we can use the ellipsoid method to give a polynomial bound on the time needed to solve the SDP (see Section 3.2 in L. Lovász, <a href="http://www.cs.elte.hu/~lovasz/semidef.ps" rel="nofollow noreferrer">Semidefinite programs and combinatorial optimization</a>).
The bound given there is a generic "<em>polynomial time</em>" and here I am interested in a less coarse bound.</p>

<p>The motivation comes from the comparison of two algorithms used for the quantum separability problem (the actual problem is not relevant here, so don't stop reading classical readers!).
The algorithms are based on a hierarchy of tests that can be cast into SDPs, and each test in the hierarchy is on a larger space, that is, the size of the corresponding SDP is larger. 
The two algorithms I want to compare differ in the following tradeoff: in the first one, to find the solution you need to climb more steps of the hierarchy and in the second one the steps of the hierarchy are higher, but you need to climb less of them. It is clear that in the analysis of this tradeoff, a precise running time of the algorithm used to solve the SDP is important. The analysis of these algorithms is done by Navascués et al. in <a href="http://arxiv.org/abs/0906.2731" rel="nofollow noreferrer">arxiv:0906.2731</a>, where they write:</p>

<blockquote>
  <p>... the time complexity of an SDP with $m$ variables and of matrix size $n$ is $O(m^2 n^2)$ (with a small extra cost coming from an iteration of algorithms).</p>
</blockquote>

<p>In <a href="http://arxiv.org/abs/quant-ph/0308032" rel="nofollow noreferrer">another paper</a>, where this approach to the problem was first proposed, the authors give the same bound, but they use the more cautious term "<em>number of arithmetic operations</em>" instead of "<em>time complexity</em>".  </p>

<p>My question is two-fold:</p>

<ul>
<li>Which algorithm/bound are Navascués et al. referring to?</li>
<li>Can I replace the expression "polynomial time" in Lovász with something less coarse (keeping the same assumptions)?</li>
</ul>

CC BY-SA 3.0
2012-12-19T23:41:41.443Z
My understanding is that the ellipsoid method gave answers that were within additive error $\epsilon$ in time polynomial in $\log(1/\epsilon)$. For most problems, one might suspect that $\epsilon = \Omega(1/2^n)$ might suffice.
Suresh Venkat
CC BY-SA 3.0
2012-12-20T00:09:05.880Z
@SureshVenkat: That is right, the ellipsoid method works in time polynomial in the size of the input matrices, the size of the constraints and $\log(1/\epsilon)$. The problem is that, for the application I mentioned in the question, saying just "polynomial" is not enough, I need a more precise bound.
Alessandro Cosentino
<quantum-information><semidefinite-programming><analysis-of-algorithms>
Polynomial speedups with algorithms based on semidefinite programming
Alessandro Cosentino
# Polynomial speedups with algorithms based on semidefinite programming

(Asked by: username_0 on 2012-12-19)

This is a followup of a recent question asked by A. Pal: [Solving semidefinite programs in polynomial time](https://cstheory.stackexchange.com/q/14548/1542).

I am still puzzling over the actual running time of algorithms that compute the solution of a semidefinite program (SDP). As Robin pointed out in [his comment](https://cstheory.stackexchange.com/questions/14548/solving-semidefinite-programs-in-polynomial-time#comment39404_14548) to the above question, SDPs cannot be solved in polynomial time in general.

It turns out that, if we define our SDP carefully and we impose a condition on how well-bounded the primal feasible region is, we can use the ellipsoid method to give a polynomial bound on the time needed to solve the SDP (see Section 3.2 in L. Lovász, [Semidefinite programs and combinatorial optimization](http://www.cs.elte.hu/~lovasz/semidef.ps)).
The bound given there is a generic "*polynomial time*" and here I am interested in a less coarse bound.

The motivation comes from the comparison of two algorithms used for the quantum separability problem (the actual problem is not relevant here, so don't stop reading classical readers!).
The algorithms are based on a hierarchy of tests that can be cast into SDPs, and each test in the hierarchy is on a larger space, that is, the size of the corresponding SDP is larger.
The two algorithms I want to compare differ in the following tradeoff: in the first one, to find the solution you need to climb more steps of the hierarchy and in the second one the steps of the hierarchy are higher, but you need to climb less of them. It is clear that in the analysis of this tradeoff, a precise running time of the algorithm used to solve the SDP is important. The analysis of these algorithms is done by Navascués et al. in [arxiv:0906.2731](http://arxiv.org/abs/0906.2731), where they write:

> ... the time complexity of an SDP with $m$ variables and of matrix size $n$ is $O(m^2 n^2)$ (with a small extra cost coming from an iteration of algorithms).

In [another paper](http://arxiv.org/abs/quant-ph/0308032), where this approach to the problem was first proposed, the authors give the same bound, but they use the more cautious term "*number of arithmetic operations*" instead of "*time complexity*".

My question is two-fold:

* Which algorithm/bound are Navascués et al. referring to?
* Can I replace the expression "polynomial time" in Lovász with something less coarse (keeping the same assumptions)?

**Tags:** quantum-information, semidefinite-programming, analysis-of-algorithms
> **Comments:**
> **username_1**: My understanding is that the ellipsoid method gave answers that were within additive error $\epsilon$ in time polynomial in $\log(1/\epsilon)$. For most problems, one might suspect that $\epsilon = \Omega(1/2^n)$ might suffice.  
> **username_0**: @SureshVenkat: That is right, the ellipsoid method works in time polynomial in the size of the input matrices, the size of the constraints and $\log(1/\epsilon)$. The problem is that, for the application I mentioned in the question, saying just "polynomial" is not enough, I need a more precise bound.  

---

## 1 answers

### Answer by username_2 on 2012-12-20. Score: 12

I'm not familiar with details of the ellipsoid method specifically for semi-definite programs, but even for *linear* programs, analysis of the ellipsoid method is pretty subtle.

* First, one needs to bound the number of iterations of the *ideal* ellipsoid algorithm. Let $E\_i$ be the ellispoid used in the $i$th iteration of the ellipsoid algorithm, and let $c\_i$ be its centroid. In the ideal algorithm, a separation/membership oracle gives you a halfspace $h\_i$ that contains the optimum point $x^\*$ but not the centroid $c\_i$. The next ellipsoid $E\_{i+1}$ is the smallest ellipsoid containing $E\_i\cap h\_i$. For each $i$, we have $vol(E\_{i+1}) < (1-\frac{1}{n})\cdot vol(E\_i)$, where $n$ is the dimension. Thus, given a reasonable starting ellipsoid, the number of iterations is polynomial in $n$ and $\log(1/\varepsilon)$. Computing $E\_{i+1}$ from $E\_i$ and $h\_i$ requires (crudely) $O(n^2)$ arithmetic operations. So the number of arithmetic operations is also polynomial in $n$ and $\log(1/\varepsilon)$.
* However, some of those arithmetic operations are square roots! It follows that the coefficients of the ideal ellipsoid $E\_i$ are irrational numbers of degree $2^i$, and so there's no hope of actually computing $E\_{i+1}$ *exactly* in any reasonable time. So instead, one computes a close outer approximation $\tilde{E}\_i \supset E\_i$ at each iteration using finite precision arithmetic. Grötschel, Lovasz, and Schrijver prove that if one uses (say) $10i$ bits of precision in the $i$th iteration, we still have $vol(\tilde E\_{i+1}) < O(1-\frac{1}{n})\cdot vol(\tilde E\_i)$, so the number of iterations increases by at most a constant factor. But now each arithmetic operation during the $i$th iteration (including the operations performed by the separation oracle) requires $O(i~\text{polylog}~i)$ time.

Altogether, the total running time of the ellipsoid method is *very* roughly the *square* of the number of arithmetic operations. Since the number of arithmetic operations is polynomial in $n$ and $\log(1/\varepsilon)$, so is the running time.

> **Comments:**
> **username_0**: Thanks for the answer. If I am tallying correctly, this is what I have (very roughly): $\sum_{i = 1}^{\text{n. of iterations}} O(n^2)$ (n. of arithmetic operations) $\times O(i \operatorname{polylog}i)$ (time for each arithmetic operation). I still don't have a bound on the number of iterations, except that is polynomial in $n$ and $\log(1/\epsilon)$. Perhaps I wasn't very clear in my question, but I am interested in a more precise bound also for the number of iterations (something like: $n$, $n^2$, ...).  
> **username_0**: One more thing: shouldn't the number of constraints also appear somewhere in the analysis? Also, is this specific to linear programs?  
> **username_2**: You also have to take the running time of the separation oracle into account; that's where the number of constraints shows up.  For explicit LPs, the separation oracle just tries the constraints one at a time.  For implicitly represented LPs, it's more complicated.  

---

