Abstract

The aim of this paper is to show the interest of taking into account the notion of curvature in gradient methods. More precisely, given a Hilbert space HH and a strictly convex function ϕ:H→R\phi:H\to {\mathbb{R}} of class C2{\mathcal C}^2, we consider the following algorithm xn+1=xn−λn ∇ϕ(xn), with λn=∣∇ϕ(xn)∣2⟨∇2ϕ(xn).∇ϕ(xn),∇ϕ(xn)⟩.(⋆)x_{n+1}=x_n-\lambda_n\, \nabla \phi(x_n),\quad \text{ with } \lambda_n = \frac{|\nabla \phi(x_n)|^2}{\langle\nabla^2\phi(x_n).\nabla\phi(x_n), \nabla\phi(x_n)\rangle}.\tag*{$(\star)$} We obtain results of linear convergence for the above algorithm, even without strong convexity. Some variants of (⋆)(\star) are also considered, with different expressions of the curvature-dependent steplength λn\lambda_n. A large part of the paper is devoted to the study of an implicit version of (⋆)(\star), falling into the field of the proximal point iteration. All these algorithms are clearly related to the Barzilai-Borwein method and numerical illustrations at the end of the paper allow to compare these different schemes.

Author information

Contact details are reproduced from the original publication and may be historical.

Bruno Baji

Dép. de Mathématiques, Université Montpellier, Place Eugène Bataillon, 34095 Montpellier 05, France

baji19@free.fr

Alexandre Cabot

Dép. de Mathématiques, Université Montpellier, Place Eugène Bataillon, 34095 Montpellier 05, France

acabot@math.univ-montp2.fr

Keywords

  • Unconstrained convex optimization
  • steepest descent
  • gradient method
  • proximal point algorithm
  • Barzilai-Borwein stepsize

Mathematics Subject Classification

65K10, 90C25, 49M25

References

  1. F. Alvarez, A. Cabot: Steepest descent with curvature dynamical system, J. Optimization Theory Appl. 120 (2004) 247–273.https://doi.org/10.1023/B:JOTA.0000015684.50827.49Google Scholar
  2. A. Auslender: Numerical methods for nondifferentiable convex optimization, Math. Program. Study 30 (1987) 102–126.https://doi.org/10.1007/BFb0121157Google Scholar
  3. J. Barzilai, J. M. Borwein: Two point step size gradient methods, IMA J. Numer. Anal. 8 (1988) 141–148.https://doi.org/10.1093/imanum/8.1.141Google Scholar
  4. H. Brézis, P. L. Lions: Produits infinis de résolvantes, Isr. J. Math. 29 (1978) 329–345.https://doi.org/10.1007/BF02761171Google Scholar
  5. A. Cauchy: Méthodes générales pour la résolution des systèmes d’équations simultanées, C. R. Acad. Sci., Paris 25 (1847) 536–538.Google Scholar
  6. J. Céa: Optimisation. Théorie et Algorithmes, Dunod, Paris (1971).Google Scholar
  7. P. G. Ciarlet: Introduction à l’Analyse Numérique Matricielle et à l’Optimisation, Masson, Paris (1990).Google Scholar
  8. R. Cominetti: Coupling the proximal point algorithm with approximation methods, J. Optimization Theory Appl. 95 (1997) 581–600.https://doi.org/10.1023/A:1022621905645Google Scholar
  9. Y. H. Dai, L. Z. Liao: R-linear convergence of the Barzilai and Borwein gradient method, IMA J. Numer. Anal. 22 (2002) 1–10.https://doi.org/10.1093/imanum/22.1.1Google Scholar
  10. O. Güler: On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optimization 29 (1991) 403–419.https://doi.org/10.1137/0329022Google Scholar
  11. B. Lemaire: About the convergence of the proximal method, in: Advances in Optimization (Lambrecht, 1991), W. Oettli, D. Pallaschke (eds.), Lect. Notes Econ. Math. Syst. 382, Springer, Berlin (1992) 39–51.https://doi.org/10.1007/978-3-642-51682-5_4Google Scholar
  12. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Franç. Inform. Rech. Opér. 4 (1970) 154–159.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  13. B. Martinet: Détermination approchée d’un point fixe d’une application pseudocontractante, C. R. Acad. Sci., Paris, Sér. A 274 (1972) 163–165.Google Scholar
  14. B. T. Polyak: Introduction to Optimization, Optimization Software, New York (1987).Google Scholar
  15. M. Raydan: On the Barzilai and Borwein choice of steplength for the gradient method, IMA J. Numer. Anal. 13 (1993) 321–326.https://doi.org/10.1093/imanum/13.3.321Google Scholar
  16. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optimization 14 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  17. M. Teboulle: Convergence of proximal-like algorithms, SIAM J. Optim. 7 (1997) 1069–1083.https://doi.org/10.1137/S1052623495292130Google Scholar

Suggested citation

B. Baji, A. Cabot. “On some Curvature-Dependent Steplength for the Gradient Method.” Journal of Convex Analysis 17 (2010), No. 3&4, 765–780. https://doi.org/10.68381/jca17050

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2010. Rights now held by Banach Press LLC.