Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
提出并测试了一种扩展的TRACE算法，允许子问题不精确求解，在保持最优迭代复杂度的同时，显著改善Hessian-向量积的最坏情况复杂度，适合大规模非凸光滑优化问题。
.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 \({\cal O}(\epsilon^{-3/2})\) for attaining an \(\epsilon\) -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.Keywordsnonlinear optimizationnonconvex optimizationworst-case iteration complexityworst-case evaluation complexitytrust-region methodsMSC codes49M3765K0565K1065Y2068Q2590C3090C60