The Complexity of Computing KKT Solutions of Quadratic Programs

Fearnley, John, Goldberg, Paul, Hollender, Alexandros and Savani, Rahul ORCID: 0000-0003-1262-7831 (2025) The Complexity of Computing KKT Solutions of Quadratic Programs In: ACM Symposium on Theory of Computing, 2024-6-24 - 2024-6-28.

PDF stoc24-paper170.pdf - Author Accepted Manuscript Download (685kB) | Preview

Abstract

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]ⁿ is complete for the class CLS = PPAD g PLS.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	Quadratic programming, KKT, continuous local search
Divisions:	Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	25 Mar 2024 10:34
Last Modified:	23 May 2026 08:37
DOI:	10.1145/3745017
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3179845
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.