The computational complexity of finding stationary points in non-convex optimization

DOI10.1007/S10107-024-02139-3MaRDI QIDQ6932189zbMATH OpenFDO

Authors Alexandros Hollender, Manolis Zampetakis

Publication date 9 September 2025

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10107-024-02139-3

Mathematics Subject Classification ID

Searching and sorting (68P10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Nonconvex programming, global optimization (90C26)

Cites work

• Black-Box Complexity of Local Minimization
• How easy is local search?
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• Lower bounds for finding stationary points I
• On the complexity of finding stationary points of smooth functions in one dimension
• Polynomial interpolation schemes for internal derivative distributions on structured grids
• Propositional proofs and reductions between NP search problems
• Separations in proof complexity and TFNP
• Settling the complexity of Nash equilibrium in congestion games
• The complexity of constrained min-max optimization
• The complexity of gradient descent: CLS = PPAD pls
• The relative complexity of NP search problems

This page was built for publication: The computational complexity of finding stationary points in non-convex optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6932189)