A MINRES-based Linesearch Algorithm for Nonconvex Optimization with Non-positive Curvature Detection

We propose a MINRES-based Newton-type algorithm for unconstrained nonconvex problems that leverages second-order and non-positive curvature (NPC) information. The derivation of comprehensive asymptotic convergence properties regarding the Kurdyka-Łojasiewicz inequality are primarily achieved by the integration of proper regularization techniques.

Basically, this thing is really good at dodging strict saddle points! We prove that the algorithm converges to second-order critical points and achieves fast local superlinear convergence under the Polyak-Łojasiewicz condition. Experiments on CUTEst and deep auto-encoders show it works like a charm.