What is the time complexity of solving an SOCP problem when using SeDuMi or SDPT3 solvers through cvx? There are many papers about SeDuMi or SDPT3 solvers in literature, but they only discuss the numerical results of the algorithms. Is there any theoratical results about the time complexity of SeDuMi or SDPT3 solvers when sloving SOCP problems which includes worst-case iteration bound and complexity per iteration.
In practice interior-point optimizer like MOSEK, SeDuMi and SDPT3 solves problems in say
10 to 100 iterations. If they need more than 200 iterations numerical problems typically prevent them from solving the problem.
Each iteration requires polynomial complexity typically some like O(n^3) where n is the number variables. In practice if the problem is sparse then the complexity is much better.
Therefore, in practice the methods either solves problem in polynomial time or does not solve the problem at all due to numerical problems. Moreover, the complexity is much better than the theoretical worst case complexity.
Strictly speaking no formal complexity for the optimizers is available because it is typically very hard to prove good results for the actual implementations when taking finite precision into account and the various tricks the implementations employs. In any case such proofs would be overly pessimistic.
The above is true independent of CVX. If we assume that CVX behaves reasonable i.e. do not introduce exponentially many constraints and variables in it is reformulations then my reply also apply to CVX.
Now I also have blog post about this issue.