Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
复制标题
DOI：
10.1137/22m1492428
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Frank E. Curtis;Qi Wang
中科院分区：
文献类型：
--
作者：
Frank E. Curtis;Qi Wang
提出、分析并测试了一种用于解决非凸光滑优化问题的算法。该算法是具有收缩和扩张的信赖域算法（TRACE）[《数学规划》162(1):132, 2017]的扩展。特别地，这种扩展使得该算法能够使用所产生的子问题的不精确解，这对于解决大规模问题是一个重要特性。以一种这样的方式允许不精确性：在保持获得一个$\epsilon$-近似一阶驻点的${\cal O}(\epsilon^{-3/2})$的最优迭代复杂度的同时，与原始的TRACE相比，在海森矩阵 - 向量乘积方面的最坏情况复杂度可能会显著提高。数值实验表明了允许不精确子问题解的益处，并且该算法与一种最先进的技术相比具有优势。
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) [Math. Prog. 162(1):132, 2017]. 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 a state-of-the-art technique.