Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization
Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization
复制标题
DOI：
10.1137/19m130563x
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Frank E. Curtis;Daniel P. Robinson;C. Royer;Stephen J. Wright
中科院分区：
文献类型：
--
作者：
Frank E. Curtis;Daniel P. Robinson;C. Royer;Stephen J. Wright
非凸优化算法的最坏情况复杂性保证一直是人们越来越感兴趣的话题。已经提出了多个框架，它们在一大类一阶和二阶策略中实现了最已知的复杂性界限。这些方法通常在设计时主要考虑到复杂性保证，因此，它们与实践中被证明是最有效的算法背道而驰。在这篇文章中，我们考虑了信赖域牛顿方法，它是求解非凸优化问题的最流行的算法之一。通过对原格式稍加修改，我们得到了两种方法--一种基于精确子问题的解，另一种利用了流行的“信赖域牛顿-共轭梯度”(信赖域牛顿-CG)方法中的不精确子问题解--其迭代和运算复杂性界与上述一类和二阶方法的最佳已知界相匹配。所得到的信赖域牛顿-CG方法也保留了经典信赖域牛顿-CG方法吸引人的实用行为，我们在标准基准测试集上进行了数值比较。
Worst-case complexity guarantees for nonconvex optimization algorithms have been a topic of growing interest. Multiple frameworks that achieve the best known complexity bounds among a broad class of first- and second-order strategies have been proposed. These methods have often been designed primarily with complexity guarantees in mind and, as a result, represent a departure from the algorithms that have proved to be the most effective in practice. In this paper, we consider trust-region Newton methods, one of the most popular classes of algorithms for solving nonconvex optimization problems. By introducing slight modifications to the original scheme, we obtain two methods -- one based on exact subproblem solves and one exploiting inexact subproblem solves as in the popular "trust-region Newton-Conjugate-Gradient" (trust-region Newton-CG) method -- with iteration and operation complexity bounds that match the best known bounds for the aforementioned class of first- and second-order methods. The resulting trust-region Newton-CG method also retains the attractive practical behavior of classical trust-region Newton-CG, which we demonstrate with numerical comparisons on a standard benchmark test set.