On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems
On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems
复制标题
DOI：
10.1137/090774100
复制
发表时间：
2010-08
期刊：
影响因子：
--
通讯作者：
C. Cartis;N. Gould;P. Toint
中科院分区：
文献类型：
--
作者：
C. Cartis;N. Gould;P. Toint
它表明，最速下降和牛顿的方法无约束非凸优化在标准假设下可能都需要一个数量的迭代和函数评估任意接近$O（\displaystyle\mathrm ^{-2}）$驱动的梯度低于$\displaystyle\mathrm $的范数。这表明，已知的最速下降的上界是紧的，牛顿法在最坏的情况下可能和最速下降法一样慢。改进的评估复杂性界的$O（\displaystyle\mathr ^{-3/2}）$评估已知的立方正则化牛顿的方法也被证明是紧的。
It is shown that the steepest-descent and Newton's methods for unconstrained nonconvex optimization under standard assumptions may both require a number of iterations and function evaluations arbitrarily close to $O(\epsilon^{-2})$ to drive the norm of the gradient below $\epsilon$. This shows that the upper bound of $O(\epsilon^{-2})$ evaluations known for the steepest descent is tight and that Newton's method may be as slow as the steepest-descent method in the worst case. The improved evaluation complexity bound of $O(\epsilon^{-3/2})$ evaluations known for cubically regularized Newton's methods is also shown to be tight.