17
$\begingroup$

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)?
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Dec 19 '12 at 23:41
  • $\begingroup$ @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. $\endgroup$ – Alessandro Cosentino Dec 20 '12 at 0:09
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$, ...). $\endgroup$ – Alessandro Cosentino Dec 21 '12 at 1:48
  • $\begingroup$ One more thing: shouldn't the number of constraints also appear somewhere in the analysis? Also, is this specific to linear programs? $\endgroup$ – Alessandro Cosentino Dec 21 '12 at 1:50
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeffε Dec 21 '12 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.