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