Improved second-order evaluation complexity for unconstrained
     nonlinear optimization using high-order regularized models

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

       naXys techreport, naXys, University of Namur, Namur (B), 2017
         
The unconstrained minimization of a sufficiently smooth objective function
f(x) is considered, for which derivatives up to order p, p >= 2, are assumed
to be available. An adaptive regularization algorithm is proposed that uses
Taylor models of the objective of order p and that is guaranteed to find a
first- and second-order critical point in at most
O(max(\epsilon_1^{-(p+1)/p},\epsilon_2^{-(p+1)/(p-1)})) function and
derivatives evaluations, where\epsilon_1 and \epsilon_2 >0 are prescribed
first- and second-order optimality tolerances.  Our approach extends the
method in Birgin et al. (2016) to finding second-order critical points, and
establishes the novel complexity bound for second-order criticality under
identical problem assumptions as for first-order, namely, that the p-th
derivative tensor is Lipschitz continuous and that f(x) is bounded from
below.  The evaluation-complexity bound for second-order criticality improves
on all such known existing results.