Solving Large-Scale Cubic Regularization by a Generalized Eigenvalue Problem
Felix Lieder
Abstract
Cubic regularization methods have several favorable properties. In particular under mild assumptions, they are globally convergent towards critical points with second-order necessary conditions satisfied. Their adoption among practitioners, however, does not yet match the strong theoretical results. One of the reasons for this discrepancy may be the additional implementation complexity needed to solve the cubic regularization subproblems. In this paper we show that this complexity can be decreased significantly by reducing the subproblem to a generalized eigenvalue problem. The resulting algorithm is not only robust, due to existing highly advanced eigenvalue solvers, but also provides a new way of employing second-order methods in the large-scale case.