  A class of second-order algorithms is proposed for minimizing smooth
nonconvex functions that alternates between regularized Newton and negative
curvature steps in an iteration-dependent subspace. In most cases, the Hessian
matrix is regularized with the square root of the current gradient and an
additional term taking moderate negative curvature into account, a negative
curvature step being taken only exceptionally. Practical variants have been
detailed where the subspaces are chosen to be the full space, or Krylov
subspaces. In the first case, the proposed method only requires the solution of
a single linear system at nearly all iterations. We establish that at most
$\mathcal{O}\left(|\log\epsilon|\,\epsilon^{-3/2}\right)$ evaluations of the
problem's objective function and derivatives are needed for algorithms in the
new class to obtain an $\epsilon$-approximate first-order minimizer, and at
most $\mathcal{O}\left(|\log\epsilon|\,\epsilon^{-3}\right)$ to obtain a
second-order one. Encouraging initial numerical experiments with two full-space
and two Krylov-subspaces variants are finally presented.
