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

Yurii Nesterov (nesterovcore.ucl.ac.be)

Abstract: 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})$.

Keywords: Convex optimiation with constraints, Newton method, global complexity bounds, cubic regularization

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: CORE Discussion Paper 2006/39, April 2006

Download: [PDF]

Entry Submitted: 04/13/2006
Entry Accepted: 04/13/2006
Entry Last Modified: 04/13/2006

Modify/Update this entry