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

In this paper we derive 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( k13 ), where k is the iteration counter. We derive also the efficiency estimate of a second-order scheme for smooth variational inequalities. Its 1 global rate of convergence is established on the level O( k ).