Algorithme du gradient

Soient ${\displaystyle \mathbb {E} }$ un espace hilbertien (produit scalaire noté ${\displaystyle \langle \cdot ,\cdot \rangle }$ et norme associée notée ${\displaystyle \|\cdot \|}$) et ${\displaystyle x\in \mathbb {E} \mapsto f(x)\in \mathbb {R} }$ une fonction différentiable. On note ${\displaystyle \mathrm {d} f(x)}$ la différentielle de ${\displaystyle f}$ en ${\displaystyle x}$ et ${\displaystyle \nabla f(x)}$ le gradient de ${\displaystyle f}$ en ${\displaystyle x}$, si bien que pour tout direction ${\displaystyle d\in \mathbb {E} }$, ${\displaystyle \mathrm {d} f(x)(d)=\langle \nabla f(x),d\rangle }$[2].

En pratique, il faudra prendre ${\displaystyle \varepsilon >0}$ ; la valeur nulle de cette tolérance a été admise uniquement pour simplifier l'expression des résultats de convergence ci-dessous.

Cet algorithme structurellement très simple repose sur le fait que, dans le voisinage d'un point ${\displaystyle x}$, la fonction ${\displaystyle f}$ décroît le plus fortement dans la direction opposée à celle du gradient de ${\displaystyle f}$ en ${\displaystyle x}$, à savoir dans la direction ${\displaystyle -\nabla f(x)}$. De manière plus précise, cette affirmation exprime en termes suggestifs le fait que, si ${\displaystyle \mathrm {d} f(x)\neq 0}$, la solution du problème d'optimisation

est la direction ${\displaystyle d=-\nabla f(x)/\|\nabla f(x)\|}$, orientée donc vers l'opposé du gradient[3].

La notion de direction de plus forte pente est en fait mal définie car elle dépend fortement du produit scalaire que l'on se donne sur l'espace hilbertien ${\displaystyle \mathbb {E} }$. En effet, si ${\displaystyle \sigma$ :(u,v)\mapsto \sigma (u,v)} est un autre produit scalaire sur ${\displaystyle \mathbb {E} }$, il existe un opérateur linéaire continu ${\displaystyle S:\mathbb {E} \to \mathbb {E} }$ auto-adjoint et défini positif tel que ${\displaystyle \sigma (u,v)=\langle Su,v\rangle ,}$ si bien que le gradient de ${\displaystyle f}$ en ${\displaystyle x}$ pour ce dernier produit scalaire s'écrit ${\displaystyle S^{-1}\nabla f(x)}$, ce qui montre explicitement la dépendance du gradient par rapport au produit scalaire. Il n'y a donc pas une unique direction de plus forte pente, ce qui n'apparaît pas clairement dans l'affirmation faite au début du paragraphe précédent. On peut même montrer que toute direction de descente de ${\displaystyle f}$ en ${\displaystyle x}$, c'est-à-dire toute direction ${\displaystyle d}$ telle ${\displaystyle \mathrm {d} f(x)(d)<0}$, est l'opposé du gradient de ${\displaystyle f}$ en ${\displaystyle x}$ pour un certain produit scalaire[4]. L'efficacité de l'algorithme du gradient dépendra donc du choix de ce produit scalaire.

Si ${\displaystyle \mathrm {d} f(x)\neq 0}$, la direction ${\displaystyle d=-\nabla f(x)}$ est une direction de descente de ${\displaystyle f}$ en ${\displaystyle x}$, puisque ${\displaystyle \mathrm {d} f(x)(d)=\langle \nabla f(x),-\nabla f(x)\rangle =-\|\nabla f(x)\|^{2}<0}$, si bien que pour tout ${\displaystyle \alpha >0}$ assez petit, on a

Grâce à la recherche linéaire, tant que ${\displaystyle \mathrm {d} f(x_{k})\neq 0}$, l'algorithme fait décroître la fonction strictement à chaque itération :

L'algorithme du gradient peut s'utiliser lorsque l'espace vectoriel sur lequel est définie la fonction à minimiser est de dimension infinie[5]. Dans ce cas, l'algorithme n'est pas implémentable, mais son étude peut avoir un intérêt pour connaître son comportement en grande dimension ou pour en utiliser les propriétés de convergence à des fins théoriques.

L'algorithme du gradient peut s'interpréter comme la méthode d'Euler explicite de résolution de l'équation différentielle ordinaire ${\displaystyle x'(\alpha )=-\nabla f(x(\alpha ))}$ (flot du gradient), avec un pas ${\displaystyle \alpha _{k}}$ de discrétisation adapté à l'itération ${\displaystyle k}$ courante par la recherche linéaire.

L'algorithme du gradient peut rencontrer un certain nombre de problèmes, en particulier celui de la convergence lorsque le minimum de la fonction se trouve au fond d'une vallée étroite (plus précisément lorsque le conditionnement de la matrice hessienne est élevée). Dans un tel cas, la suite des {x_k} oscille de part et d'autre de la vallée et progresse laborieusement, même lorsque les α_k sont choisis de sorte à minimiser f(b).

La figure ci-dessous illustre ce type de comportement pour une fonction de Rosenbrock à 2 dimensions.

Deux points faibles de l'algorithme du gradient sont :

• l'algorithme peut nécessiter de nombreuses itérations pour converger vers un minimum local, notamment si la courbure est très différente dans des directions différentes ;
• la recherche du pas α optimal, généralement effectuée par une recherche linéaire, peut se révéler très longue. Inversement, utiliser un pas α fixe peut conduire à de mauvais résultats. Des méthodes comme la méthode de Newton et l'inversion de la matrice hessienne en complément des techniques de gradient conjugué offrent souvent de meilleurs résultats.