Descente de gradient

Traduction à relire ---

Descente de gradient --- (+)

La descente de gradient désigne un algorithme d'optimisation. Afin de trouver un minimum local de la fonction à optimiser, cette méthode consiste à progresser par étapes proportionnelles à l'opposé du gradient (ou de son approximation) de la fonction au point courant. À l'opposé, en progressant par étapes dans la direction du gradient, on obtient alors un maximum local de la fonction ; cette méthode est alors appelée montée de gradient (gradient ascent en anglais).

La descente de gradient est également connue sous les noms de descente de plus forte pente ou méthode de la plus grand pente car l'antigradient définit la meilleure des directions de descente. 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.

Algorithme

La descente de gradient est basée sur l'observation que si une fonction $\ F(x)$ à valeurs dans $\mathbb{R}$ est définie et différentiable (dérivable pour une fonction définie sur $\mathbb{R}$ ) en un point $\ a$ , alors $\ F(x)$ décroît le plus rapidement dans une direction opposée à celle du gradient de $F$ en $\ a$ , $-\nabla F(a)$ . Ainsi, si l'on définit $\ b$ comme suit :

$b = a - \gamma \nabla F(a)$

pour $γ > 0$ suffisamment petit, alors on a $F(a) \geq F(b)\$ . Ainsi, en conservant cette observation en tête, on peut initialiser l'algorithme à une valeur $x 0$ , première approximation de la position du minimum local de $F$ , et calculer la séquence $x_1, x_2, \dots$ telle que :

$x_{n+1} = x_n - \gamma_n \nabla F(x_n),\ n \geq 0.$

On a alors

$F(x_0) \geq F(x_1) \geq F(x_2) \geq \dots$ ,

et ainsi la série $(x n)$ converge vers le minimum local désiré. Également, le pas $γ$ peut varier à chaque itération.

Descente de gradient sur une fonction de type bol (vue en plan avec lignes de niveaux).

L'évolution des points $x n$ au cours de la méthode est illustrée sur la figure de droite. Dans cette figure, on suppose que $F$ est définie sur le plan ( $\mathbb{R}^2$ ), et qu'elle représente une forme de bol. Les courbes bleues correspondent aux lignes de niveaux, c'est à dire les lignes sur lesquelles $F$ est constante. Les vecteurs rouges montrent la direction de l'opposé du gradient à leur point d'origine. Il est intéressant de noter également que le gradient (et son opposé) en un point donné est orthogonal à la ligne de niveau en ce point. On peut donc obesrver ici comment la descente de gradient progresse vers le fond du bol, c'est à dire vers le point où la valeur de $F$ est minimale.

Exemples et limitations

L'algorithme de descente de gradient peut rencontrer un certain nombre de problèmes avec des fonctions pathologiques comme par exemple la fonction de Rosenbrock illustrée ici. Cette fonction contient en effet une vallée très resserrée et courbée qui inclut le minimum. Le fond de la vallée est également très plat. A cause de cette vallée courbe et presque plane, l'optimisation zigzague au fond de la vallée vers le minimum en utilisant de très petits pas et se révèle donc très lente.

Application de la méthode de remontée de gradient à la fonction $F(x,y)=\sin\left(\frac{1}{2} x^2 - \frac{1}{4} y^2 + 3 \right) \cos(2 x+1-e^y)$ :

Vue en plan avec lignes de niveaux.

Vue en trois dimensions.

Quelques précisions

La descente de gradient peut s'appliquer à des espaces de dimension quelconque, même pour des espaces de dimension infinie. 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 Gâteaux de la fonctionnelle à minimiser.

Deux points faibles de la descente de 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é sont souvent de meilleures alternatives.

Un algorithme plus puissant 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 $γ$ .

La descente de gradient correspond en fait à la méthode d'Euler de résolution d'équations différentielles ordinaires appliquée à un flot de gradient. Comme le but est de trouver le minimum et non la ligne de flot, l'erreur commise est moins significative.

Un exemple numérique

La descente de gradient est ici appliquée afin de trouver le minimum de la fonction $f (x) = x 4 - 3 x 3 + 2$ , dont la dérivée est $f'(x) = 4 x 3 - 9 x 2$ . Voici un exemple d'implémentation de la descente de gradient sur cette fonction en langage C.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main ()
{
	// Analytiquement, on peut déterminer qu'un minimum local de la fonction est trouvé pour x=9/4
	// L'algorithme commence à x=6
 
	double xOld = 0;
	double xNew = 6;
	double eps = 0.01; // taille du pas fixe
	double precision = 0.00001;
	while (fabs(xNew - xOld) > precision)
	{
             xOld = xNew;
             xNew = xNew - eps*(4*xNew*xNew*xNew-9*xNew*xNew);
	}
 
	printf ("Le minimum local est obtenu pour x = %lg\n", xNew);
 
}

Avec la précision choisie ici, l'algorithme converge vers un minimum situé en $x = 2.24996$ en 70 itérations.

Une implémentation plus robuste que celle-ci pourrait incorporer une méthode de recherche linéaire du meilleur pas ; ou, plus simplement vérifier si la valeur de la fonction diminue bien à chaque itération et dans le cas contraire diminuer la valeur du pas de déplacement $γ$ . Une recherche linéaire du meilleur pas permettrait à l'algorithme de converger plus rapidement.

Voir aussi

Références

(en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Gradient descent ».
Mordecai Avriel (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
Jan A. Snyman (2005). Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. Springer Publishing. ISBN 0-387-24348-8

Portail des mathématiques

Ce document provient de « Descente de gradient ».

Catégories : Analyse à plusieurs variables | Algorithme d'optimisation

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Descente de gradient de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

Descente De Gradient — Traduction à relire Gradient descent → … Wikipédia en Français
Gradient de pression — Gradient Les lignes bleues représentent le gradient de couleur du plus clair vers le plus foncé En physique, en analyse vectorielle, on définit le gradient comme une grandeur vectorielle qui indique de quelle façon une grandeur physique varie… … Wikipédia en Français
Gradient de température — Gradient Les lignes bleues représentent le gradient de couleur du plus clair vers le plus foncé En physique, en analyse vectorielle, on définit le gradient comme une grandeur vectorielle qui indique de quelle façon une grandeur physique varie… … Wikipédia en Français
Gradient Thermique Adiabatique — Le gradient thermique adiabatique est, dans l atmosphère terrestre, la variation de température de l air avec l altitude (autrement dit le gradient de la température de l air), qui ne dépend que de la pression atmosphérique, c est à dire :… … Wikipédia en Français
Gradient adiabatique — Gradient thermique adiabatique Le gradient thermique adiabatique est, dans l atmosphère terrestre, la variation de température de l air avec l altitude (autrement dit le gradient de la température de l air), qui ne dépend que de la pression… … Wikipédia en Français
Gradient adiabatique humide — Gradient thermique adiabatique Le gradient thermique adiabatique est, dans l atmosphère terrestre, la variation de température de l air avec l altitude (autrement dit le gradient de la température de l air), qui ne dépend que de la pression… … Wikipédia en Français
Gradient adiabatique saturé — Gradient thermique adiabatique Le gradient thermique adiabatique est, dans l atmosphère terrestre, la variation de température de l air avec l altitude (autrement dit le gradient de la température de l air), qui ne dépend que de la pression… … Wikipédia en Français
Gradient adiabatique sec — Gradient thermique adiabatique Le gradient thermique adiabatique est, dans l atmosphère terrestre, la variation de température de l air avec l altitude (autrement dit le gradient de la température de l air), qui ne dépend que de la pression… … Wikipédia en Français
Algorithme de descente — Descente de gradient Traduction à relire Gradient descent → … Wikipédia en Français
Gradient thermique adiabatique — Le gradient thermique adiabatique est, dans l atmosphère terrestre, la variation de température de l air avec l altitude (autrement dit le gradient de la température de l air), qui ne dépend que de la pression atmosphérique, c est à dire :… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Descente de gradient