Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thank you very much.

share|improve this question
2  
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 at 20:10

2 Answers 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.

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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