  The unconstrained minimization of a sufficiently smooth objective function
$f(x)$ is considered, for which derivatives up to order $p$, $p\geq 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 \left(\max\left(
\epsilon_1^{-\frac{p+1}{p}}, \epsilon_2^{-\frac{p+1}{p-1}} \right) \right)$
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.
