Projects per year
Abstract
It is shown that the steepestdescent 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(ε^{2}) to drive the norm of the gradient below ε. This shows that the upper bound of O(ε^{2}) evaluations known for the steepest descent is tight and that Newton's method may be as slow as the steepestdescent method in the worst case. The improved evaluation complexity bound of O(ε^{3/2} ) evaluations known for cubically regularized Newton's methods is also shown to be tight. © 2010 Society for Industrial and Applied Mathematics.
Original language  English 

Pages (fromto)  28332852 
Number of pages  20 
Journal  SIAM Journal on Optimization 
Volume  20 
Issue number  6 
DOIs  
Publication status  Published  1 Jan 2010 
Fingerprint
Dive into the research topics of 'On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems'. Together they form a unique fingerprint.Projects
 2 Active

Complexity in nonlinear optimization
TOINT, P., Gould, N. I. M. & Cartis, C.
1/11/08 → …
Project: Research


How much patience do you have? Issues in complexity for nonlinear optimization
Philippe Toint (Invited speaker)
5 Feb 2016Activity: Talk or presentation types › Oral presentation

How much patience do you have? Issues in complexity for nonlinear optimization
Philippe Toint (Speaker)
31 Jan 2016Activity: Talk or presentation types › Oral presentation

How much patience do you have? Issues in complexity for nonlinear optimization
Philippe Toint (Invited speaker)
10 Dec 2015Activity: Talk or presentation types › Oral presentation