  High-order tensor methods for solving both convex and nonconvex optimization
problems have generated significant research interest, leading to algorithms
with optimal global rates of convergence and local rates that are faster than
Newton's method. On each iteration, these methods require the unconstrained
local minimization of a (potentially nonconvex) multivariate polynomial of
degree higher than two, constructed using third-order (or higher) derivative
information, and regularized by an appropriate power of regularization.
Developing efficient techniques for solving such subproblems is an ongoing
topic of research, and this paper addresses the case of the third-order tensor
subproblem. We propose the CQR algorithmic framework, for minimizing a
nonconvex Cubic multivariate polynomial with Quartic Regularisation, by
minimizing a sequence of local quadratic models that incorporate simple cubic
and quartic terms. The role of the cubic term is to crudely approximate local
tensor information, while the quartic one controls model regularization and
progress. We provide necessary and sufficient optimality conditions that fully
characterise the global minimizers of these cubic-quartic models. We then turn
these conditions into secular equations that can be solved using nonlinear
eigenvalue techniques. We show, using our optimality characterisations, that a
CQR algorithmic variant has the optimal-order evaluation complexity of
$\mathcal{O}(\epsilon^{-3/2})$ when applied to minimizing our
quartically-regularised cubic subproblem, which can be further improved in
special cases. We propose practical CQR variants that use local tensor
information to construct the local cubic-quartic models. We test these variants
numerically and observe them to be competitive with ARC and other subproblem
solvers on typical instances and even superior on ill-conditioned subproblems
with special structure.
