Editing Quadratic programming (section)

=== Non-convex quadratic programming ===
If {{mvar|Q}} is indefinite, (so the problem is non-convex) then the problem is [[NP-hard]].<ref>{{cite journal | last = Sahni | first = S. | title = Computationally related problems | journal = SIAM Journal on Computing | volume = 3 | issue = 4 | pages = 262–279 | year = 1974 | doi=10.1137/0203021| url = http://www.cise.ufl.edu/~sahni/papers/comp.pdf | citeseerx = 10.1.1.145.8685 }}</ref> A simple way to see this is to consider the non-convex quadratic constraint ''x<sub>i</sub>''<sup>2</sup> = ''x<sub>i</sub>''. This constraint is equivalent to requiring that ''x<sub>i</sub>'' is in {0,1}, that is, ''x<sub>i</sub>'' is a binary integer variable. Therefore, such constraints can be used to model any [[Integer programming|integer program]] with binary variables, which is known to be NP-hard.

Moreover, these non-convex problems might have several stationary points and local minima. In fact, even if {{mvar|Q}} has only one negative [[eigenvalue]], the problem is (strongly) [[NP-hard]].<ref>{{cite journal | title = Quadratic programming with one negative eigenvalue is (strongly) NP-hard | first1 = Panos M. | last1 = Pardalos | first2 = Stephen A. | last2 = Vavasis | journal = Journal of Global Optimization | volume = 1 | issue = 1 | year = 1991 | pages = 15–22 | doi=10.1007/bf00120662| s2cid = 12602885 }}</ref>

Moreover, finding a KKT point of a non-convex quadratic program is CLS-hard.<ref>{{Cite arXiv |eprint=2311.13738 |last1=Fearnley |first1=John |last2=Goldberg |first2=Paul W. |last3=Hollender |first3=Alexandros |last4=Savani |first4=Rahul |title=The Complexity of Computing KKT Solutions of Quadratic Programs |date=2023 |class=cs.CC }}</ref>