Worst-case complexity of SOCP

[Jiaxin Yang]

Hi Johan,

I recent found a thread on the old YALMIP forum on the complexity of SDP and SOCP "http://sedumi.ie.lehigh.edu/index.php?option=com_kunena&Itemid=78&func=view&catid=16&id=3711";

However, on that thread, you only talked about how to approximate the complexity of SDP. So what about SOCP? Can we use the same approach to approximate its complexity?

Thank you.

[Erling D. Andersen]

I am the author of MOSEK which is a widely used SOCP solver.

A primal-dual interior-point algorithm as implemented in MOSEK and SeDuMi needs about O(n^3) work per iterations. The number of iterations is about O(sqrt(n)*log(1/eps))  where eps is the required precision. In practice virtually all  SOCPs solves in less than 100 iterations and the per iteration complexity is much better because sparsity can be exploited.

n is roughly speaking the number cones in the problem.

[Erling D. Andersen]

I should add to my previous post that I assumed the problem had the form

   min c'x

   st.  Ax=b

         x \in K

which is the one employed by SeDuMi and MOSEK, You could also have given a complexity results for the dual. This number will of course in the end be the same.