Voir la source de Algorithme du gradient

{{Infobox Méthode scientifique
| image = Gradient descent.png
| légende = Algorithme du gradient sur une fonction de type bol (vue en plan avec courbes de niveaux).
}}
L{{'}}'''algorithme du gradient''', aussi appelé algorithme de '''descente de gradient''', est un [[Algorithmique|algorithme]] d'[[Optimisation (mathématiques)|optimisation]] {{c'est-à-dire|différentiable}}. Il est destiné à minimiser une fonction réelle différentiable définie sur un [[espace euclidien]] (par exemple, <math>\R^n</math>, l'espace des {{math|''n''}}-uplets de [[Nombre réel|nombres réels]], muni d'un [[produit scalaire]]) ou, plus généralement, sur un [[espace hilbertien]]. L'algorithme est itératif et procède donc par améliorations successives. Au point courant, un déplacement est effectué dans la direction ''opposée'' au [[gradient]], de manière à faire décroître la fonction. Le déplacement le long de cette direction est déterminé par la technique numérique connue sous le nom de [[recherche linéaire (optimisation)|recherche linéaire]]. Cette description montre que l'algorithme fait partie de la famille des [[algorithme à directions de descente|algorithmes à directions de descente]].

Les algorithmes d'optimisation sont généralement écrits pour minimiser une fonction. Si l'on désire maximiser une fonction, il suffira de minimiser son opposée.

Il est important de garder à l'esprit le fait que le gradient, et donc la direction de déplacement, dépend du produit scalaire qui équipe l'espace hilbertien ; l'efficacité de l'algorithme dépend donc de ce produit scalaire.

L'algorithme du gradient est également connu sous le nom d{{'}}'''algorithme de la plus forte pente''' ou '''de la plus profonde descente''' (''{{lang|en|steepest descent}}'', en anglais) parce que le gradient est la pente de la fonction linéarisée au point courant et est donc, localement, sa plus forte pente (notion qui dépend du produit scalaire).

Dans sa version la plus simple, l'algorithme ne permet de trouver ou d'approcher qu'un point stationnaire (i.e., un point en lequel le gradient de la fonction à minimiser est nul) d'un problème d'optimisation ''sans contrainte''. De tels points sont des minima globaux, si la fonction est convexe. Des extensions sont connues pour les problèmes avec contraintes simples, par exemple des [[contraintes de borne]]. Malgré des résultats de convergence théoriques satisfaisants, cet algorithme est généralement lent si le produit scalaire définissant le gradient ne varie pas avec le point courant de manière convenable, c'est-à-dire si l'espace vectoriel n'est pas muni d'une [[Variété riemannienne|structure riemannienne]] appropriée, d'ailleurs difficilement spécifiable ''a priori''. Il est donc franchement à déconseiller, même pour minimiser une [[fonction quadratique]] strictement convexe de deux variables{{Référence nécessaire}}. Toutefois, ses qualités théoriques font que l'algorithme sert de modèle à la famille des algorithmes à directions de descente ou de sauvegarde dans les [[algorithme à régions de confiance|algorithmes à régions de confiance]].

Le principe de cet algorithme remonte au moins à [[Augustin Louis Cauchy|Cauchy]] (1847)<ref>{{article|prénom1= Augustin |nom1=Cauchy |année= 1847| titre = Méthode générale pour la résolution des systèmes d’équations simultanées | journal =[[CRAS|Comptes Rendus de l’Académie des Sciences de Paris]]|tome = 25| pages = 536-538 | url = https://gallica.bnf.fr/ark:/12148/bpt6k2982c/f540}}.</ref>.
<!--
Quand elle est connue sous ces dernières appellations, cette méthode ne doit pas être confondue avec la méthode de plus grande pente utilisée pour l'approximation d'intégrales.
-->

== L'algorithme ==

Soient <math>\mathbb{E}</math> un espace hilbertien ([[produit scalaire]] noté <math>\langle\cdot,\cdot\rangle</math> et norme associée notée <math>\|\cdot\|</math>) et <math>x\in\mathbb{E}\mapsto f(x)\in\R</math> une [[fonction différentiable]]. On note <math>\mathrm{d}f(x)</math> la différentielle de <math>f</math> en <math>x</math> et <math>\nabla f(x)</math> le [[gradient]] de <math>f</math> en <math>x</math>, si bien que pour tout direction <math>d\in\mathbb{E}</math>, <math>\mathrm{d}f(x) (d)=\langle\nabla f(x),d\rangle</math><ref>{{Article |prénom1=M. |nom1=Annad |prénom2=A. |nom2=Lefkir |prénom3=M. |nom3=Mammar-kouadri |prénom4=I. |nom4=Bettahar |titre=Development of a local scour prediction model clustered by soil class |périodique=Water Practice and Technology |numéro=wpt2021065 |date=2021-07-07 |issn=1751-231X |doi=10.2166/wpt.2021.065 |lire en ligne=https://doi.org/10.2166/wpt.2021.065 |consulté le=2021-09-03 }}</ref>.

{{Théorème|Algorithme du gradient|On se donne un point/itéré initial <math>x_0\in\mathbb{E}</math> et un seuil de tolérance <math>\varepsilon\geqslant 0</math>. L'algorithme du gradient définit une suite d'itérés <math>x_1, x_2, \ldots \in\mathbb{E}</math>, jusqu'à ce qu'un test d'arrêt soit satisfait. Il passe de <math>x_k</math> à <math>x_{k+1}</math> par les étapes suivantes.
# ''Simulation'' : calcul de <math>\nabla f(x_k)</math>.
# ''Test d'arrêt'' : si <math>\|\nabla f(x_k)\| \leqslant \varepsilon</math>, arrêt.
# ''Calcul du pas'' <math>\alpha_k>0</math> par une règle de [[recherche linéaire (optimisation)|recherche linéaire]] sur <math>f</math> en <math>x_k</math> le long de la direction <math>-\nabla f(x_k)</math>.
# ''Nouvel itéré'' : <math>x_{k+1} = x_k - \alpha_k \nabla f(x_k).</math>}}

En pratique, il faudra prendre <math>\varepsilon>0</math> ; 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 <math>x</math>, la fonction <math>f</math> décroît le plus fortement dans la direction opposée à celle du gradient de <math>f</math> en <math>x</math>, à savoir dans la direction <math>-\nabla f(x)</math>. De manière plus précise, cette affirmation exprime en termes suggestifs le fait que, si <math>\mathrm{d} f(x)\ne0</math>, la solution du problème d'optimisation
<center>
<math>
\min_{\|d\|=1}\,\langle\nabla f(x), d\rangle
</math>
</center>
est la direction <math>d=-\nabla f(x)/\|\nabla f(x)\|</math>, orientée donc vers l'opposé du gradient<ref>Par l'[[inégalité de Cauchy-Schwarz]] la valeur optimale de ce problème est supérieure à <math>-\|\nabla f(x)\|</math>, borne atteinte par la solution donnée.</ref>.

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 <math>\mathbb{E}</math>. En effet, si <math>\sigma:(u,v)\mapsto\sigma(u,v)</math> est un autre produit scalaire sur <math>\mathbb{E}</math>, il existe un opérateur linéaire continu <math>S:\mathbb{E}\to\mathbb{E}</math> auto-adjoint et défini positif tel que <math>\sigma(u,v)=\langle Su,v\rangle,</math> si bien que le gradient de <math>f</math> en <math>x</math> pour ce dernier produit scalaire s'écrit <math>S^{-1}\nabla f(x)</math>, 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 <math>f</math> en <math>x</math>, c'est-à-dire toute direction <math>d</math> telle <math>\mathrm{d}f(x) (d)<0</math>, est l'opposé du gradient de <math>f</math> en <math>x</math> pour un certain produit scalaire''<ref>En effet, supposons que <math>\mathrm{d}f(x)(d)<0</math> et que <math>\nabla f(x)</math> soit le gradient de <math>f</math> en <math>x</math> pour le produit scalaire <math>(u,v)\mapsto\langle u,v\rangle</math>. On considère l'application <math>\sigma:(u,v)\mapsto\langle Su,v\rangle</math> avec
<center>
<math>
S:=I-\frac{\nabla f(x)\otimes\nabla f(x)}{\langle\nabla f(x),d\rangle}-\frac{d\otimes d}{\|d\|^2},
</math>
</center>
où <math>I</math> est l'identité sur <math>\mathbb{E}</math> et <math>u\otimes v:\mathbb{E}\to\mathbb{E}</math> est l'opérateur défini en <math>z\in\mathbb{E}</math> par <math>(u\otimes v)z=\langle v,z\rangle u</math> (on reconnaît la formule de [[BFGS]] directe de mise à jour de l'identité). Comme <math>S</math> est auto-adjoint et défini positif pour le produit scalaire <math>\langle\cdot,\cdot\rangle</math>, l'application bilinéaire <math>\sigma</math> est un produit scalaire. Par ailleurs, on a <math>Sd=-\nabla f(x)</math>, si bien que le gradient de <math>f</math> pour le produit scalaire <math>\sigma</math>, qui vaut <math>S^{-1}\nabla f(x)</math>, n'est autre que <math>-d</math>, comme annoncé.</ref>. L'efficacité de l'algorithme du gradient dépendra donc du choix de ce produit scalaire.

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

<center>
<math>f(x-\alpha\nabla f(x))<f(x)</math>.
</center>

Grâce à la recherche linéaire, tant que <math>\mathrm{d}f(x_k)\ne0</math>, l'algorithme fait décroître la fonction strictement à chaque [[itération]] :

<center>
<math>f(x_{k+1}) < f(x_k).</math>
</center>

L'algorithme du gradient peut s'utiliser lorsque l'espace vectoriel sur lequel est définie la fonction à minimiser est de dimension infinie<ref>K. Ito, K. Kunisch (2008), ''Lagrange Multiplier Approach to Variational Problems and Applications'', Advances in Design and Control, SIAM Publication, Philadelphia.</ref>. 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 <math>x'(\alpha)=-\nabla f(x(\alpha))</math> ([[flot (mathématiques)|flot]] du gradient), avec un pas <math>\alpha_k</math> de discrétisation adapté à l'itération <math>k</math> courante par la recherche linéaire. <!-- Comme le but est de trouver le minimum et non la ligne de flot, l'erreur commise est moins significative.-->
<!--
 Dans ce dernier cas, l'espace de recherche est l'espace des fonctions, et la direction de descente est déterminée en calculant la dérivée de [[René Gâteaux|Gâteaux]] de la fonctionnelle à minimiser.
-->

== Résultats de convergence ==
{{...}}
=== Problèmes quadratiques ===

On considère dans un premier temps le cas où le critère est une fonction quadratique strictement convexe, définie sur un [[espace euclidien]] <math>\mathbb{E}</math> (donc de dimension finie) :

<center>
<math>f:x\in\mathbb{E}\mapsto f(x):=\langle g,x\rangle+\frac{1}{2}\langle Hx,x\rangle,</math>
</center>

où <math>g\in\mathbb{E}</math> et <math>H:\mathbb{E}\to\mathbb{E}</math> est un opérateur [[auto-adjoint]] [[Matrice définie positive|défini positif]]. Dans ce cas, l'algorithme du gradient avec [[Algorithme à directions de descente#Règles exactes|recherche linéaire exacte]] (i.e., à chaque itération le critère est minimisé le long de la direction opposée au gradient) converge [[Vitesse de convergence des suites#Convergence q-linéaire|q-linéairement]] vers l'unique minimum du problème. De manière plus précise, on a le résultat de convergence suivant, qui utilise le conditionnement <math>\ell_2</math> du hessien {{math|''H''}} du critère {{math|''f''}}, c'est-à-dire le rapport entre sa plus grande valeur propre <math>\lambda_{\max}(H)</math> et sa plus petite valeur propre <math>\lambda_{\min}(H)</math>,
<center>
<math>\kappa_2:=\kappa_2(H):=\frac{\lambda_{\max}(H)}{\lambda_{\min}(H)},
</math>
</center>
et la [[Norme (mathématiques)|norme]] associée à {{math|''H''}} qui est définie par
<center>
<math>
v\in\mathbb{E}\mapsto\|v\|_H=\langle Hv,v\rangle^{1/2}.
</math>
</center>

{{Théorème|Convergence sur une fonction quadratique strictement convexe|Soit {{math|''f''}} une fonction quadratique strictement convexe sur un espace euclidien, de hessien {{math|''H''}}. Utilisé pour minimiser cette fonction, l'algorithme du gradient ci-dessus, avec <math>\varepsilon=0</math> et [[Algorithme à directions de descente#Règles exactes|recherche linéaire exacte]], génère une suite <math>\{x_k\}_{k\geqslant 1}</math> convergeant [[Vitesse de convergence des suites#Convergence q-linéaire|q-linéairement]] vers l'unique minimum {{math|''x''<sub>*</sub>}} de {{math|''f''}}. Plus précisément, on a
<center>
<math>
\forall\;k\geqslant 1:\qquad\|x_{k+1}-x_*\|_H\leqslant\left(\frac{\kappa_2-1}{\kappa_2+1}\right)\|x_k-x_*\|_H.
</math>
</center>
}}

Comme <math>\|x-x_*\|_H^2=2[f(x)-f(x_*)]</math>, l'estimation de la vitesse de convergence ci-dessus s'applique aussi à celle du critère {{math|''f''(''x'')}} vers sa valeur optimale {{math|''f''(''x''<sub>*</sub>)}}.

Ce résultat pourrait paraître attrayant et laisser penser que l'algorithme du gradient est une méthode performante, mais en général, ce n'est pas le cas. D'une part, la convergence linéaire est une propriété relativement faible en optimisation différentiable, d'autant plus faible que le taux de convergence (ici <math>(\kappa_2-1)/(\kappa_2+1)</math>) est proche de 1. Cela se produit dans l'algorithme du gradient lorsque <math>\kappa_2</math> est grand, c'est-à-dire pour les problèmes mal conditionnés. À l'inverse, lorsque <math>\kappa_2=1</math> (i.e., le hessien est un multiple de l'identité), l'algorithme converge en 1 itération. On rappelle par ailleurs que pour minimiser une fonction quadratique strictement convexe, l'[[Méthode du gradient conjugué|algorithme du gradient conjugué]] ou toute méthode directe de résolution du système linéaire associé trouve le minimum en un nombre fini d'opérations (en arithmétique exacte), alors que l'algorithme du gradient requiert en général un nombre infini d'itérations.

=== Problèmes non linéaires ===
{{...}}

== Exemples ==

=== Minimisation d'une fonction de 2 variables ===
L'évolution des itérés <math>x_k</math> au cours de l'algorithme est illustrée sur la figure de droite : {{math|''f''}} est une [[fonction convexe]] de deux variables (définie sur le plan <math>\R^2</math>) et son graphe représente une forme de bol. Chaque courbe bleue représente une [[ligne de niveau|courbe de niveau]] de {{math|''f''}}, un lieu de points en lesquels {{math|''f''}} vaut une constante donnée. Chaque [[vecteur]] rouge représente un déplacement <math>x_{k+1}-x_k</math>, qui est orienté suivant l'opposé de la direction du gradient en {{math|''x<sub>k</sub>''}}. Ici, le gradient en {{math|''x<sub>k</sub>''}} est celui associé au [[Espace euclidien#Exemples|produit scalaire euclidien]], si bien qu'il est [[orthogonal]] (pour le produit scalaire euclidien) à la tangente en {{math|''x<sub>k</sub>''}} à la courbe de niveau auquel {{math|''x<sub>k</sub>''}} appartient. La figure illustre la progression des itérés vers le fond du bol, c'est-à-dire vers le point où la valeur de {{math|''f''}} est minimale.

=== Maximisation d'une fonction de 2 variables ===

Application de la méthode de remontée de gradient à la fonction

<center>
<math>f(x,y)=\sin\left(\frac{1}{2} x^2 - \frac{1}{4} y^2 + 3 \right) \cos(2 x+1-e^y)</math>
</center>

<!--
{|
[[Image:gradient ascent (contour).png|200px|left|thumb|Vue en plan avec [[ligne de niveau|courbes de niveaux]].]]
[[Image:gradient ascent (surface).png|240px|center|thumb|Vue en trois dimensions.]]
|}
-->

<center>
<gallery style="text-align:center;" perrow="2">
Fichier:gradient ascent (contour).png|Vue en plan avec [[ligne de niveau|courbes de niveaux]]
Fichier:gradient ascent (surface).png|Vue en trois dimensions
</gallery>
</center>
<br>

Une illustration de cette [[fonction trigonométrique]], ci-dessus, permet de constater le caractère zigzagant de la méthode du gradient, dû au fait que le gradient d'un itéré est orthogonal au gradient du précédent. On notera que malgré la convergence de l'algorithme, cette dernière est relativement lente à cause de cette avancée en zigzag.

=== Problème de terminaison de l’algorithme à pas constant ===

Un défaut facilement observable de l'algorithme du gradient à pas constant, est sa non-convergence pour des pas trop élevés, ce même pour des fonctions qui en théorie devraient le faire converger. La fonction ci-dessous en est un cas typique. Dans la pratique avec un pas de 0.01 l'algorithme converge en moins 150 itérations. Mais si l'on décide d'opter pour un pas de 0.1, l'algorithme ne convergera tout simplement pas. On pourra vérifier que l'algorithme boucle entre les deux mêmes valeurs indéfiniment.

== Points faibles, remèdes et extensions ==

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 (analyse numérique)|conditionnement]] de la [[matrice hessienne]] est élevée). Dans un tel cas, la suite des {{math|{''x<sub>k</sub>''}<nowiki/>}} oscille de part et d'autre de la vallée et progresse laborieusement, même lorsque les {{mvar|α{{ind|k}}}} sont choisis de sorte à minimiser {{math|''f''(''b'')}}.

La figure ci-dessous illustre ce type de comportement pour une [[fonction de Rosenbrock]] à 2 dimensions. 
:[[Image:Banana-SteepDesc.gif|200px]]

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 {{mvar|α}} optimal, généralement effectuée par une [[recherche linéaire (optimisation)|recherche linéaire]], peut se révéler très longue. Inversement, utiliser un pas {{mvar|α}} 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.

=== Amélioration et alternatives dans le cas général ===

L’amélioration la plus naturelle de l’algorithme est la méthode de Newton avec recherche linéaire, dont la convergence est quadratique, et garantie si on dispose des hypothèses mentionnées dans Résultats de convergence.

Une alternative efficace est la méthode [[BFGS]], qui consiste à calculer en chaque étape une matrice, qui multipliée au gradient permet d’obtenir une meilleure direction. De plus, cette méthode peut être combinée avec une méthode plus efficace de recherche linéaire afin d’obtenir la meilleure valeur de {{mvar|α}}.

L’algorithme du gradient est mal défini pour minimiser des fonctions non lisses, même si elles sont convexes. Lorsque le critère est localement lipschitzien, et spécialement s’il est convexe, l’[[algorithme des faisceaux]] apporte un remède à l’absence de convergence<ref>{{en}} K. C. Kiwiel (2001), « {{Langue|en|Convergence and efficiency of subgradient methods for quasiconvex minimization}} », ''{{Langue|en|Mathematical Programming (Series A)}}'', 90, 1-25.</ref>.

== Notes et références ==
{{Traduction/Référence|en|Gradient descent|221253722|type=n}}
{{Références|colonnes=2}}

== Voir aussi ==

=== Articles connexes ===
* [[Algorithme du gradient stochastique]]
* [[Algorithme proximal (optimisation)]]
* [[Analyse vectorielle]]
* [[Dérivée directionnelle]]
*[[Dérivation automatique]]

=== Bibliographie ===
* {{ouvrage|lang=en|auteur=Mordecai Avriel|année=2003|titre=Nonlinear Programming: Analysis and Methods|éditeur=Dover Publishing|isbn=0-486-43227-0}}.
* {{ouvrage|lang=en|auteur=[[Dimitri Bertsekas|D. P. Bertsekas]]|année=1995|titre=Nonlinear Programming|éditeur=Athena Scientific|ISBN=1-886529-14-0}}
* {{ouvrage|lang=en|auteur=J. F. Bonnans|auteur2=J. Ch. Gilbert|auteur3=[[Claude Lemaréchal|C. Lemaréchal]]|auteur4=C. Sagastizábal|année=2006|titre=Numerical Optimization - Theoretical and Numerical Aspects}}
* {{ouvrage|lang=en|auteur=Jan A. Snyman|année=2005|titre=Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and  New Gradient-Based Algorithms|éditeur=Springer Publishing|isbn=0-387-24348-8}}
* {{ouvrage|auteur=Michel Bierlaire|année=2006|titre=Introduction à l'optimisation différentiable|isbn=978-2-88074-669-8}}
* {{ouvrage|auteur=Marie-Hélène Meurisse|année=2018|titre=Algorithme numériques, Fondement théoriques et analyse pratique, Cours, exercices et applications avec MATLAB|isbn=9782340-021860}}
* {{ouvrage|auteur1=Patrick Lascaux|auteur2=Raymond Théodor|année=2000|titre=Analyse numérique matricielle appliquée à l'art de l'ingénieur 2. Méthodes itératives}}
* {{ouvrage|auteur1=Jacques Rappaz|auteur2=Marco Picasso|année=2017|titre=Introduction à l'analyse numérique}}

=== Lien externe ===
J. Ch. Gilbert, ''[http://www-rocq.inria.fr/~gilbert/ensta/optim.html Éléments d'Optimisation Différentiable — Théorie et Algorithmes]'', syllabus de cours à l'[[École nationale supérieure de techniques avancées|ENSTA ParisTech]], Paris.
* [http://numerentur.org/gradiente-descendente/ Gradient descendant (en Espagnol)]
{{Palette|optimisation}}
{{Portail|analyse|informatique théorique}}

[[Catégorie:Analyse à plusieurs variables]]
[[Catégorie:Algorithme d'optimisation|Gradient]]