Metraipolis › archive › dc_0cb54fb41ba0
The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization — arXiv:2604.02285
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2604.02285
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-06T14:52:05.722Z
- SHA-256 of the archived text
15c0c6beeb5789d44d359cab97723f01158af43f79b5ec4df1ea9481433aa468- Stable URL of this page
https://metraipolis.com/documento/dc_0cb54fb41ba0
How to cite
The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization — arXiv:2604.02285 — arXiv (en), https://arxiv.org/abs/2604.02285 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0cb54fb41ba0 (Metraipolis archive dc_0cb54fb41ba0, sha256 15c0c6beeb5789d44d359cab97723f01158af43f79b5ec4df1ea9481433aa468)
BibTeX
@misc{dc0cb54fb41ba0,
title = {The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization — arXiv:2604.02285},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2604.02285},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0cb54fb41ba0; sha256 15c0c6beeb5789d44d359cab97723f01158af43f79b5ec4df1ea9481433aa468},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2604.02285. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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/\epsilon))$ 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 $\epsilon$-approximate fixed point is an $(\epsilon,\sqrt{\epsilon})$-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+\gamma},r)$-local pure Nash equilibria, for every fixed rational $\gamma\in(0,1]$, in two-player nonconvex common-interest games with actions in $[0,1]$.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2604.02285 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:23:27.654Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).