Paperlane

no. 10 · Friday 6 November 2026

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization

Andreas Kontogiannis, Ioannis Panageas and Vasilis Pollatos

math.OC · via cs.CC · v2

Abstract

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]$.

comments
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
fields
Optimization and Control
pdf ↗ page arXiv:2604.02285 ↗