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

Abstract:

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.

Download:

ERGO-13-008.pdf

History:

Written: 3 May 2013

Status:

Submitted for publication