Cubic regularization of Newton’s method for convex problems with constraints

In this paper we derive the efficiency estimates of the regularized Newton's method as applied to constrained convex minimization problems and to variational inequalities. We study a one-step Newton's method and its multistep accelerated version, which converges on smooth convex problems as $O({1 \over k^3})$, where $k$ is the iteration counter. We derive also the efficiency estimate of a second-order scheme for smooth variational inequalities. Its global rate of convergence is established on the level $O({1 \over k})$.


CORE Discussion Paper 2006/39, April 2006



View Cubic regularization of Newton's method for convex problems with constraints