The Complexity of Computing KKT Solutions of Quadratic Programs

Fearnley, John, Goldberg, Paul W, Hollender, Alexandros and Savani, Rahul ORCID: 0000-0003-1262-7831 (2024) The Complexity of Computing KKT Solutions of Quadratic Programs PROCEEDINGS OF THE 56TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2024, abs/23. pp. 892-903. ISSN 0737-8017

Access the full-text of this item by clicking on the Open Access link.

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∩PLS.

Item Type:	Article
Uncontrolled Keywords:	Quadratic Programming, KKT, Continuous Local Search
Depositing User:	Symplectic Admin
Date Deposited:	15 Jul 2024 13:42
Last Modified:	23 May 2026 08:18
DOI:	10.1145/3618260.3649647
Open Access URL:	https://doi.org/10.1145/3618260.3649647
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3182878
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.