IE417 Lecture 24
For convex QP problems, there exists polynomial time algorithms (barrier methods, for instance).
If the Hessian has even a single negative eigenvalue, these problems are NP-hard in general.
However, we can attempt to nd KKT points.
Consider QP: min c>x + x>Hx)/2 s t Ax ≤ b x≥0