Complexity bounds for second-order optimality
                    in unconstrained optimization

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

                Report NAXYS-11-2010     18 December 2010

Abstract.
This paper examines worst-case evaluation bounds for finding weak minimizers
in unconstrained optimization. For the cubic regularization algorithm,
Nesterov and Polyak (2006) and Cartis, Gould and Toint (2010) show that at most
O(epsilon^{-3}) iterations may have to be performed for finding an iterate
which is within epsilon of satisfying second-order optimality conditions.
We first show that this bound can be derived for a version of the algorithm
which only uses one-dimensional global optimization of the cubic model and
that it is sharp.  We next consider the standard trust-region method and show
that a bound of the same type may also be derived for this method, and that it
is also sharp in some cases. We conclude by showing that a comparison of the
worst-case behaviour of the ARC and trust-region algorithms favours
the first of these methods.