Cubic-quartic regularization models for solving polynomial subproblems in third-order tensor methods
针对三阶张量方法中的子问题，提出CQR算法框架，通过最小化带四次正则化的三次多项式，利用最优性条件转化为可高效求解的方程，并证明其最优评价复杂度为O(ε^{-3/2})，数值实验显示在病态子问题上表现优越。
Abstract High-order tensor methods for solving both convex and nonconvex optimization problems have recently generated significant research interest, due in part to the natural way in which higher derivatives can be incorporated into adaptive regularization frameworks, leading to algorithms with optimal global rates of convergence and local rates that are faster than Newton’s method. On each iteration, to find the next solution approximation, 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 the change in the iterates. Developing efficient techniques for the solution of such subproblems is a current topic of research, and this paper addresses this question for the case of the third-order tensor subproblem. In particular, we propose the CQR algorithmic framework, for minimizing a nonconvex Cubic multivariate polynomial with Quartic Regularisation, by sequentially minimizing a sequence of local quadratic models that also incorporate both simple cubic and quartic terms. The role of the cubic term is to crudely approximate local tensor information, while the quartic one provides model regularization and controls 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 efficiently using root-finding procedures. We show, using our optimality characterisations, that a CQR algorithmic variant has the optimal-order evaluation complexity of $$\mathcal {O}(\epsilon ^{-3/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> when applied to minimizing our quartically-regularised cubic subproblem, which can be further improved in special cases. We propose practical CQR variants that judiciously use local tensor information to construct the local cubic-quartic models. We test these variants numerically and observe them to be competitive with cubic regularization and other subproblem solvers on typical instances and even show superior performance on ill-conditioned subproblems with special structure.