3
$\begingroup$

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

Thank you very much.

  • 0
    I believe Nesterov, Nemirovskii, and Yi give complexity results in their book, Interior-point polynomial algorithms in convex programming (http://epubs.siam.org/doi/pdf/10.1137/1.9781611970791.fm)2014-12-02

2 Answers 2

2

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.

2

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.

  • 0
    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.2011-09-26