### Technical Report MS 07-008

#### Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity

*Coralia Cartis, Nicholas I. M. Gould and Philippe L. Toint*

##### Abstract:

An Adaptive Regularisation algorithm using Cubics (ARC) was proposed for
unconstrained optimization and analysed in Cartis, Gould & Toint (Part I,
2007). In this companion paper, we further the analysis by providing worst-case
global iteration complexity bounds for ARC and a second-order variant to
achieve approximate first-order, and for the latter even second-order,
criticality of the iterates. In particular, the second-order ARC algorithm
requires at most O(ε^{-3/2}) iterations to drive the
objective's gradient below the desired accuracy ε, and
O(ε^{-3}), to reach approximate nonnegative curvature in a
subspace. The orders of these bounds match those proved by Nesterov & Polyak
(Math. Programming 108 (1), 2006, pp 177-205) for their Algorithm 3.3 which
minimizes the cubic model globally on each iteration. Our approach is more
general, and relevant to practical (large-scale) calculations, as ARC allows
the cubic model to be solved only approximately and may employ approximate
Hessians.

##### Keywords:

Unconstrained optimization, Newton's method, globalization, cubic models, complexity

##### Download:

MS-07-008.pdf

##### History:

Written: 29 September 2007

Revised: 25 September 2008, 9 March 2009

##### Status:

It is part of the previous 'Adaptive cubic overestimation methods for unconstrained optimization', 2007, which has been split into two parts, with Part I available as ERGO Technical Report MS 07-006, 2007.

Published in *Mathematical Programming*.