On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems

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 ... to drive the norm of the gradient below ... This shows that the upper bound of...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on optimization 2010-01, Vol.20 (6), p.2833-2852
Main Authors: Cartis, C, Gould, N I M, Toint, Ph L
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Complexity theory
Descent
Mathematical analysis
Methods
Newton methods
Norms
Optimization
Studies
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ... to drive the norm of the gradient below ... This shows that the upper bound of ... 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 ... evaluations known for cubically regularized Newton's methods is also shown to be tight. [PUBLICATION ABSTRACT]
ISSN:1052-6234
1095-7189
DOI:10.1137/090774100