The Complexity of Computing KKT Solutions of Quadratic Programs
Open Access
- 9 October 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (5) , 1-48
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] n is complete for the class CLS = PPAD ∩ PLS .Keywords
All Related Versions
Funding Information
- EPSRC (EP/W014750/1, EP/X040461/1)
- Swiss State Secretariat for Education, Research and Innovation (MB22.00026)
This publication has 37 references indexed in Scilit:
- Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy2022
- Adaptive Global Algorithm for Solving Box-Constrained Non-convex Quadratic Minimization ProblemsJournal of Optimization Theory and Applications, 2022
- On the complexity of finding a local minimizer of a quadratic function over a polytopeMathematical Programming, 2022
- Approximating quadratic programming with bound and quadratic constraintsMathematical Programming, 1999
- On the complexity of approximating a KKT point of quadratic programmingMathematical Programming, 1998
- The complexity of approximating a nonlinear programMathematical Programming, 1995
- On affine scaling algorithms for nonconvex quadratic programmingMathematical Programming, 1992
- Open questions in complexity theory for numerical optimizationMathematical Programming, 1992
- Quadratic programming with one negative eigenvalue is NP-hardJournal of Global Optimization, 1991
- Some NP-complete problems in quadratic and nonlinear programmingMathematical Programming, 1987