Quadratic programming with one negative eigenvalue is NP-hard

• DOI: 10.1007/bf00120662
• Publication Date: 2004-11-04T04:07:32Z
• Authors: Panos M. Pardalos; Stephen A. Vavasis

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Hacijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.