Polynomial speedups with algorithms based on semidefinite programming

Question

This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time.

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 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). 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, 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, 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)?

Answer 1

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.