The Complexity of Computing KKT Solutions of Quadratic Programs.
CoRR(2023)
摘要
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$\cap$PLS.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要