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.
Unconstrained optimization, Newton's method, globalization, cubic models, complexity
Written: 29 September 2007
Revised: 25 September 2008, 9 March 2009
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.
