Technical Report ERGO 13-008

An example of slow convergence for Newton's method on a function with globally Lipschitz continuous Hessian
Coralia Cartis, Nicholas I. M. Gould and Philippe L. Toint


An example is presented where Newton’s method for unconstrained minimization is applied to find an ε-approximate first-order critical point of a smooth function and takes a multiple of ε−2 iterations and function evaluations to terminate, which is as many as the steepest-descent method in its worst-case. The novel feature of the proposed example is that the objective function has a globally Lipschitz-continuous Hessian, while a previous example published by the same authors only ensured this critical property along the path of iterates, which is impossible to verify a priori.




Written: 3 May 2013


Submitted for publication