Evaluation complexity of adaptive cubic regularization methods
                   for convex unconstrained optimization

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

                  Report NAXYS-05-2010 November 2010

The  adaptive cubic  regularization algorithms  described in  Cartis,  Gould &
Toint  (2009, 2010) for  unconstrained (nonconvex)  optimization are  shown to
have   improved  worst-case  efficiency   in  terms   of  the   function-  and
gradient-evaluation  count   when  applied  to  convex   and  strongly  convex
objectives. In  particular, our complexity upper  bounds match in  order (as a
function of the accuracy of  approximation), and sometimes even improve, those
obtained by Nesterov (2004, 2008) and  Nesterov & Polyak (2006) for these same
problem classes, without employing the Hessian's Lipschitz constant explicitly
in the algorithms or requiring exact or global solution of the subproblem.  An
additional outcome of our approximate  approach is that our complexity results
can naturally capture the advantages of both first- and second-order methods.