Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP) problem? And any references?
Thank you very much.
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.
This problem is NP-Hard in the general case. This can be shown by reduction from the boolean satisfiability problem.
Here is a link to a paper about it.
Edit: After doing some more digging, it seems anon is right.Here is a link to a solver that claims to do so.