Technical Report ERGO 12-009

On the complexity of the steepest-descent with exact linesearches
Coralia Cartis, Nicholas I. M. Gould and Philippe L. Toint


The worst-case complexity of the steepest-descent algorithm with exact linesearches for unconstrained optimization is analyzed, and it is shown that the number of iterations of this algorithm which may be necessary to find an iterate at which the norm of the objective function's gradient is less that a prescribed ε is, essentially a multiple of 1/ε2, as is the case for variants of the same algorithms using inexact linesearches.




Written: 9 September 2012


Submitted for publication