Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
Frank E. Curtis, Qi Wang · SIAM Journal on Optimization · 2023
Abstract. An algorithm for solving nonconvex smooth optimization problems is proposed, analyzed, and tested. The algorithm is an extension of the trust-region algorithm with contractions and expansions (TRACE) [F. E. Curtis, D. P. Robinson, and M. Samadi, Math. Program., 162 (2017), pp. 1–32]. In particular, the extension allows the algorithm to use inexact solutions of the arising subproblems, which is an important feature for solving large-scale problems. Inexactness is allowed in a manner such that the optimal iteration complexity of [Formula: see text] for attaining an [Formula: see text]-approximate first-order stationary point is maintained, while the worst-case complexity in terms of Hessian-vector products may be significantly improved as compared to the original TRACE. Numerical experiments show the benefits of allowing inexact subproblem solutions and that the algorithm compares favorably to state-of-the-art techniques.