Sotiris Kanellopoulos

The Computational Complexity of Finding Second-Order Stationary Points

Non-convex minimization problems are universally considered hard, and even guaranteeing that a computed solution is locally minimizing is known to be NP-hard. In this general context, our paper focuses on the problem of finding stationary points that satisfy an approximate second-order optimality co…