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

and a strictly convex function

\phi:H\to {\mathbb{R}} ϕ : H → R

of class

{\mathcal C}^2 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)$} x n + 1 = x n − λ n   ∇ ϕ ( x n ) ,  with  λ n = ∣ ∇ ϕ ( x n ) ∣ 2 ⟨ ∇ 2 ϕ ( x n ) . ∇ ϕ ( x n ) , ∇ ϕ ( x n ) ⟩ . ( ⋆ )

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 λ 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.