  The cubic regularization (CR) algorithm has attracted a lot of attentions in
the literature in recent years. We propose a new reformulation of the cubic
regularization subproblem. The reformulation is an unconstrained convex problem
that requires computing the minimum eigenvalue of the Hessian. Then based on
this reformulation, we derive a variant of the (non-adaptive) CR provided a
known Lipschitz constant for the Hessian and a variant of adaptive
regularization with cubics (ARC). We show that the iteration complexity of our
variants matches the best known bounds for unconstrained minimization
algorithms using first- and second-order information. Moreover, we show that
the operation complexity of both of our variants also matches the
state-of-the-art bounds in the literature. Numerical experiments on test
problems from CUTEst collection show that the ARC based on our new subproblem
reformulation is comparable to existing algorithms.
