arXiv:2604.02285 · v2
The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
摘要
The complexity of finding second-order stationary points (SOSPs) in constrained settings has remained unclear and has been highlighted as an open question by the works of Hollender and Zampetakis [2023] and Kontogiannis et al. [2024]. In particular, under one established definition (SOSP1) where nonnegative curvature is required only along the null space of the active constraints [Bertsekas, 1997], the problem lies in TFNP, and algorithms with $O(poly(1/ε))$ running times have been proposed. Under another established notion of stationarity (SOSP2) checking is coNP-hard in high dimensions. We investigate the computational landscape of finding SOSPs under polytope constraints. We prove that, even if promised that all KKT points lie a constant distance away from the domain's boundary--where SOSP1 and SOSP2 reduce to the standard unconstrained conditions--finding an approximate SOSP under either definition is PLS-hard, and the hardness continues to hold even in $[0,1]^2$. As a direct consequence, our result establishes a fundamental barrier on the continuity of SOSP-computing algorithms: unless PLS=CLS, no deterministic, iterative algorithm with a computationally efficient, continuous update rule can guarantee that every $ε$-approximate fixed point is an $(ε,\sqrtε)$-SOSP, even under the above interior promise. We establish PLS-completeness by proving that the problem of finding approximate SOSP1 belongs to PLS in high dimensions. In addition, we prove that, for every fixed $d\ge 2$, finding an approximate SOSP2 is also PLS-complete, escaping the coNP-hardness which appears in high dimensions. We also establish PLS-hardness and a polynomial-time search reduction to LOCALOPT for finding $(r^{2+γ},r)$-local pure Nash equilibria, for every fixed rational $γ\in(0,1]$, in two-player nonconvex common-interest games with actions in $[0,1]$.
作者备注：This version simplifies the group analysis and extends the results to the SOSP2 definition and nonconvex games. The abstract was shortened to meet the arXiv requirements