Conference item
The complexity of computing KKT solutions of quadratic programs
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 302.4KB, Terms of use)
-
- Publisher copy:
- 10.1145/3618260.3649647
Authors
- Publisher:
- Association for Computing Machinery
- Host title:
- Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024)
- Journal:
- Proceedings of the 56th Annual ACM Symposium on Theory of Computing More from this journal
- Pages:
- 892 - 903
- Publication date:
- 2024-02-09
- Acceptance date:
- 2024-02-09
- Event title:
- 56th Annual ACM Symposium on Theory of Computing (STOC 2024)
- Event location:
- Vancouver, Canada
- Event website:
- http://acm-stoc.org/stoc2024/
- Event start date:
- 2024-06-24
- Event end date:
- 2024-06-28
- DOI:
- ISBN:
- 979-8-4007-0383-6
- Language:
-
English
- Pubs id:
-
1615534
- Local pid:
-
pubs:1615534
- Deposit date:
-
2024-02-09
- ARK identifier:
Terms of use
- Copyright holder:
- Fearnley et al.
- Copyright date:
- 2024
- Rights statement:
- © 2024 Copyright held by the owner/author(s).
- Notes:
- This paper was presented at the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), 24th-28th June 2024, Vancouver, Canada. This is the accepted manuscript version of the article. The final version will be available online from a forthcoming edition of the conference proceedings.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record