# time complexity of a convex quadratically constrained quadratic program (QCQP) problem

Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP) problem? And any references?

Thank you very much.

-
In general, it is good to expand out the abbreviations (QCQP - Quadratically constrained quadratic program, which is what I assume, in this case) at least once. –  user17762 Mar 14 '11 at 5:29
yes. it stands for Quadratically constrained quadratic program. thank you for pointing it out –  Giantron Mar 14 '11 at 5:39
I believe Nesterov, Nemirovskii, and Yi give complexity results in their book, Interior-point polynomial algorithms in convex programming (epubs.siam.org/doi/pdf/10.1137/1.9781611970791.fm) –  Erik Miehling Dec 2 '14 at 20:10

I just read the wikipedia article on QCQPs, and my impression is that a QCQP can only be NP-hard in the non-convex case. Since you specify that you have a convex QCQP, I believe the problem can be solved in polynomial time with interior point methods.

I could be mistaken though.

-
It doesn't say so explicitly. It says general case is NP hard. It says that the problem can be "readily" solved if it is convex. Can we assume that means it is in P? Probably, I guess, but a different reference is necessary. –  Tim Seguine Sep 26 '11 at 11:36

This problem is NP-Hard in the general case. This can be shown by reduction from the boolean satisfiability problem.

Edit: After doing some more digging, it seems anon is right.Here is a link to a solver that claims to do so.

-