Tell me more ×
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.
up vote 2 down vote favorite
1

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

2 Answers

up vote 2 down vote

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 Sep 26 '11 at 11:36
up vote 1 down vote

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

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.