Computational complexity of "optimize" for QCQP

[Shaik]

Dear Johan,

I have implemented the following piece of code for QCQP in using yalmip. Here the unknown zk is 2by1 vecor, Pz is a known 2by2 positive definite matrix and P is a known 3by3 positive definite matrix. For this simple problem, could you tell me the computational complexity? It is not very clear to me, I tried to look for literature where there is no unique answer for in this context.

constraint=[1 zk'; zk Pz];

M = [constraint >= 0];

obj = ([zk;1])'*P*([zk;1]);

sol = optimize(M,obj,sdpsettings('verbose',0));

Thank you,

Shaik.

[Johan Löfberg]

To begin with, why are you writing a simple quadratic constraint as an SDP?

Secondly, since the dimension is fixed, complexity is O(1)!

[Shaik]

1. Well, the actual constraint is $z_k P_z^{-1} z_k<=1$, to avoid the matrix inversion I have considered such constraint above.

2. As per your second remark, I see some literature where it is mentioned that QP is solved polynomial time (just for linear constraint case though). It may be a stupid question, but please clarify me briefly.

[Johan Löfberg]

1. An SDP is more complex to solve than an SOCP, so for real problems, you should stay in the SOCP world, i.e. norm(chol(Pz)\zk)<=1

2. Complexity analysis only makes sense when you have varying dimensions. If the length of z is n, then complexity will at least be cubic, as you will have n variables and thus a linear system of size nxn to solve for search directions in every iteration. Theory says you need roughly n^.5 iterations, thus ending up in n^3.5 complexity, but in practice the number of iterations is typically 10-20, menaing practical cubic complexity. Another computational part is compilation of the hessian in every iteration. Not sure what that would be here, but I suspcet it also can be done in cubic time. Compelxity analysis for specific problems is very hard though, as it depends on particular sparsity patterns etc, so all numbers above could be completely off in practice.

Having said that, the particular problem you've posed can be solved analytically.

[Johan Löfberg]

scratch that note on analytic solutions, might not be trivial

[Shaik]

Dear Johan,

Thank you for your wonderful explanation. Yes, I do note about the analytical solutions, because what I provide is a very simplistic piece of code.

Thank you,

Shaik.

[Erling D. Andersen]

From theoretical point of view you get the best complexity converting the problem to a SOCP. Well other approaches may have the same complexity but not better . Now at

   http://erlingdandersen.blogspot.dk/2013/11/complexity-of-solving-conic-quadratic.html

I discuss the practical complexity of solving an SOCP.

You may find that interesting. See also

   http://docs.mosek.com/whitepapers/qmodel.pdf

for info about the conversion.

[Shaik]

Dear Erling,

Thanks a ton for the information.

-Shaik.