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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – user17762
    Mar 14, 2011 at 5:29
  • $\begingroup$ yes. it stands for Quadratically constrained quadratic program. thank you for pointing it out $\endgroup$
    – Giantron
    Mar 14, 2011 at 5:39
  • $\begingroup$ 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) $\endgroup$
    – Erik M
    Dec 2, 2014 at 20:10

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Tim Seguine
    Sep 26, 2011 at 11:36
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.