On some Curvature-Dependent Steplength for the Gradient Method

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 $H$ and a strictly convex function $\phi:H\to {\mathbb{R}}$ of class ${\mathcal C}^2$, we consider the following algorithm $$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 $\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.