Adaptive cubic overestimation methods for unconstrained optimization.
           Part II: worst-case iteration complexity

         C. Cartis, N. I. M. Gould and Ph. L. Toint

                      Report TR07/05b 


An Adaptive Cubic Overestimation (ACO) framework for unconstrained
optimization was proposed 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 ACO 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 ACO
algorithm requires at most O(eps^{-3/2}) iterations to drive the objectiveâs
gradient below the desired accuracy eps, and O(eps^{-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 ACO allows the cubic model to be solved only
approximately and may employ approximate Hessians.