User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Accelerating the cubic regularization of Newton's method on convex problems

Primary tabs

Nesterov, Yurii [UCL]

In this paper we propose an accelerated version of the cubic regularization of Newton’s method (Nesterov and Polyak, in Math Program 108(1): 177–205, 2006). The original version, used for minimizing a convex function with Lipschitz-continuous Hessian, guarantees a global rate of convergence of order O1k2 , where k is the iteration counter. Our modified version converges for the same problem class with order O1k3 , keeping the complexity of each iteration unchanged. We study the complexity of both schemes on different classes of convex problems. In particular, we argue that for the second-order schemes, the class of non-degenerate problems is different from the standard class.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2008
Language Anglais
Journal information "Mathematical Programming" - Vol. 112, no. 1, p. 159-181 (2008)
Peer reviewed yes
issn 0025-5610
e-issn 1436-4646
Publication status Publié
Affiliation UCL - FSA/INMA - Département d'ingénierie mathématique
Links
  1. Bennet A.A. (1916). Newton’s method in general analysis. Proc. Nat. Ac. Sci. USA. 2(10): 592–598
  2. Conn Andrew R., Gould Nicholas I. M., Toint Philippe L., Trust Region Methods, ISBN:9780898714609, 10.1137/1.9780898719857
  3. Dennis J. E., Schnabel Robert B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations, ISBN:9780898713640, 10.1137/1.9781611971200
  4. Kantorovich, L.V.: Functional analysis and applied mathematics. Uspehi Matem. Nauk. 3(1), 89–185 (1948), (in Russian). Translated as N.B.S. Report 1509, Washington (1952)
  5. Nesterov Yurii, Introductory Lectures on Convex Optimization, ISBN:9781461346913, 10.1007/978-1-4419-8853-9
  6. Nesterov Yu. and Polyak B. (2006). Cubic regularization of Newton method and its global performance. Math. Program. 108(1): 177–205
  7. Ortega J.M. and Rheinboldt W.C. (1970). Iterative Solution of Nonlinear Equations in Several Variables. Academic, NY
  8. Vladimirov, A., Nesterov, Yu., Chekanov, Yu.: Uniformly convex functionals. Vestnik Moskovskogo universiteta, ser. Vychislit. Matem. i Kibern., 4, 18–27 (1978), (In Russian)
Bibliographic reference Nesterov, Yurii. Accelerating the cubic regularization of Newton's method on convex problems. In: Mathematical Programming, Vol. 112, no. 1, p. 159-181 (2008)
Permanent URL http://hdl.handle.net/2078.1/94948