The Complexity of Computing KKT Solutions of Quadratic Programs
It is well known that solving a (non-convex) quadratic program is NP -hard. We show that the problem remains hard even if we are only looking for a Karush–Kuhn–Tucker (KKT) point, instead of a global optimum. Namely, we prove that computing a KKT point of a quadratic polynomial over the domain [0,1] n is complete for the class CLS = PPAD ∩ PLS .
Authors
- John Fearnley (ORCID: https://orcid.org/0000-0003-0791-4342)
- Alexandros Hollender (ORCID: https://orcid.org/0000-0001-5255-9349)
- Paul W. Goldberg (ORCID: https://orcid.org/0000-0002-5436-7890)
- Rahul Savani (ORCID: https://orcid.org/0000-0003-1262-7831)
Institutions
- Turing Institute (GB)
- University of Liverpool (GB)
- University of Oxford (GB)
- The Alan Turing Institute (GB)
- Science Oxford (GB)
Publication Details
- Journal
- Journal of the ACM
- Published
- 2025-06-19
- DOI
- https://doi.org/10.1145/3745017
- Primary Topic
- Advanced Optimization Algorithms Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00