The Complexity of Computing KKT Solutions of Quadratic Programs

John Fearnley; Paul W. Goldberg; Alexandros Hollender; Rahul Savani

doi:10.1145/3618260.3649647

STOC2024顶会

The Complexity of Computing KKT Solutions of Quadratic Programs

John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani

arXiv DOI 出版方

2024年份

1被引次数

4顶会引用

摘要

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.