User menu

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

Cubic regularization of Newton method and its global performance

Primary tabs

Nesterov, Yurii [UCL] Polyak, Boris []

In this paper, we provide theoretical analysis for a cubic regularization of Newton method as applied to unconstrained minimization problem. For this scheme, we prove general local convergence results. However, the main contribution of the paper is related to global worst-case complexity bounds for different problem classes including some nonconvex cases. It is shown that the search direction can be computed by standard linear algebra technique.

Document type Article de périodique (Journal article)
Publication date 2006
Language Anglais
Journal information "Mathematical Programming, Série A" - Vol. 108, no. 1, p. 177-205 (Août 2006)
Peer reviewed yes
Publisher Springer (Heidelberg, Germany)
issn 0025-5610
e-issn 1436-4646
Publication status Publié
Affiliations UCL - EUEN/CORE - Center for operations research and econometrics
Institute of Control Science
Keywords General nonlinear optimization ; Unconstrained optimization ; Newton method ; Trust-region methods ; Global complexity bounds ; Global rate of convergence
Links
  1. Bennet, A.A.: Newton's method in general analysis. Proc. Nat. Ac. Sci. USA. 2 (10), 592–598 (1916)
  2. Conn, A.B., Gould, N.I.M., Toint, Ph.L.: Trust Region Methods. SIAM, Philadelphia, 2000
  3. Dennis, J.E., Jr., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM, Philadelphia, 1996
  4. Fletcher, R.: Practical Methods of Optimization, Vol. 1, Unconstrained Minimization. John Wiley, NY, 1980
  5. Goldfeld, S., Quandt, R., Trotter, H.: Maximization by quadratic hill climbing. Econometrica. 34, 541–551 (1966)
  6. 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 D.C. (1952)
  7. Levenberg, K.: A method for the solution of certain problems in least squares. Quart. Appl. Math. 2, 164–168 (1944)
  8. Marquardt, D.: An algorithm for least-squares estimation of nonlinear parameters. SIAM J. Appl. Math. 11, 431–441 (1963)
  9. Nemirovsky, A., Yudin, D.: Informational complexity and efficient methods for solution of convex extremal problems. Wiley, New York, 1983
  10. Nesterov, Yu.: Introductory lectures on convex programming: a basic course. Kluwer, Boston, 2004
  11. Nesterov, Yu., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, 1994
  12. Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, NY, 1970
  13. Polyak, B.T.: Gradient methods for minimization of functionals. USSR Comp. Math. Math. Phys. 3 (3), 643–653 (1963)
  14. Polyak, B.T.: Convexity of quadratic transformations and its use in control and optimization. J. Optim. Theory and Appl. 99 (3), 553–583 (1998)
Bibliographic reference Nesterov, Yurii ; Polyak, Boris. Cubic regularization of Newton method and its global performance. In: Mathematical Programming, Série A, Vol. 108, no. 1, p. 177-205 (Août 2006)
Permanent URL http://hdl.handle.net/2078.1/23376