AnalyseMéthode · Glossaire
Gradient à pas optimal (méthode du)
La méthode du gradient à pas optimal (ou steepest descent avec pas exact) est une méthode d'optimisation itérative pour minimiser une fonction différentiable. À chaque itération, on se déplace dans la direction opposée au gradient en choisissant le pas qui minimise exactement la fonction dans cette direction par une recherche linéaire exacte. Bien que simple, cette méthode peut converger lentement en cas de mauvais conditionnement de la fonction objectif. Elle sert de référence pour comparer d'autres méthodes comme le gradient conjugué.
Sommaire
Ce que vous allez apprendre
- Identifier la recherche linéaire exacte qui définit le pas optimal.
- Calculer deux itérations sur une fonction quadratique.
- Distinguer pas exact, pas fixe et recherche approchée.
- Reconnaître le zigzag lié au mauvais conditionnement.
En clair
Imaginez un point posé sur un relief en forme de cuvette. La pente indique la montée la plus forte ; partir exactement en sens inverse fait donc descendre le point. Reste à choisir jusqu'où avancer.
La méthode du gradient à pas optimal examine toute la ligne de descente et s'arrête à son point le plus bas. Elle recommence ensuite avec la nouvelle pente. Chaque déplacement est le meilleur sur la ligne choisie, mais pas forcément le meilleur chemin vers le fond de la cuvette.
Définition
La méthode du gradient à pas optimal minimise par itérations une fonction différentiable réelle . À l'itération numérotée k, le point courant est xk et son gradient, c'est-à-dire le vecteur des dérivées partielles, est . Tant que ce vecteur n'est pas nul, la direction choisie est son opposée. Dans la norme euclidienne, cette direction est celle de la plus forte décroissance instantanée.
Le pas positif ou nul αk est un minimum global de la fonction d'une variable obtenue sur la demi-droite de descente : . Le nouveau point vaut alors . Ce choix porte le nom de recherche linéaire exacte. Il suppose que le minimum sur la demi-droite existe et puisse être déterminé ; il n'affirme pas que le minimum global de f est atteint en une étape.
Pour une fonction quadratique strictement convexe dont la matrice symétrique A est définie positive, le pas se calcule explicitement : . Sur des fonctions fortement convexes et suffisamment régulières, les itérés convergent vers l'unique minimum. Un fort écart entre les courbures selon les directions peut toutefois produire un zigzag lent.
Le principe
À partir d'un point x0, calculez à chaque rang k le gradient gk. Si gk est nul, arrêtez : le point est stationnaire. Sinon, cherchez une valeur αk qui minimise exactement f(xk − αgk) parmi les nombres α positifs ou nuls, puis posez xk+1 = xk − αkgk. Répétez jusqu'à ce qu'un critère d'arrêt annoncé soit satisfait, par exemple une norme du gradient inférieure à une tolérance.
Quand l'utiliser
La fonction objectif doit être différentiable au voisinage des points parcourus afin que le gradient fournisse une direction. À chaque itération non stationnaire, la restriction doit admettre un minimum pour α positif ou nul, et ce minimum doit pouvoir être calculé avec l'exactitude exigée. La convexité n'est pas nécessaire pour écrire l'algorithme, mais elle intervient dans les garanties : avec une fonction fortement convexe et un gradient lipschitzien, le minimum est unique et la convergence est assurée.
Contre-cas : si f diminue sans borne le long de la direction choisie, la recherche linéaire n'a aucun pas optimal fini. Si f est seulement accessible par des évaluations bruitées, un minimum exact est également irréaliste. Il faut alors employer une recherche linéaire approchée, avec des conditions de décroissance explicites, ou une méthode adaptée au bruit.
Un exemple, pas à pas
On minimise la fonction . Les données sont la matrice diagonale A, de coefficients diagonaux 1 et 4, le point initial x0 = (4, 1) et le minimum attendu (0, 0).
1. Le premier gradient vaut g0 = (4, 4). La formule quadratique donne .
2. Le nouveau point est x1 = (4, 1) − 0,4(4, 4) = (2,4 ; −0,6). Sa valeur est f(x1) = 3,6, contre f(x0) = 10.
3. Le gradient suivant est g1 = (2,4 ; −2,4). Le même calcul donne α1 = 0,4, puis x2 = (1,44 ; 0,36) et f(x2) = 1,296.
Le contrôle est double : les valeurs 10, 3,6 et 1,296 décroissent, et le produit scalaire g0 · g1 vaut 4 × 2,4 + 4 × (−2,4) = 0. Les deux gradients successifs sont donc orthogonaux. La trajectoire sur les courbes de niveau rend visible ce changement de direction et l'approche en zigzag du minimum.
En pratique
Sur une fonction quadratique de taille modeste, le pas exact se déduit parfois d'une formule. La méthode fournit alors un repère simple pour vérifier un calcul d'optimisation ou comparer la baisse obtenue par d'autres algorithmes.
Lorsque chaque évaluation de la fonction coûte cher, résoudre exactement une minimisation à chaque itération peut coûter davantage que le gain obtenu. Une recherche linéaire approchée est préférable dès qu'une décroissance suffisante est mesurable sans localiser exactement le minimum sur la ligne.
Si les courbes de niveau sont très allongées et que les directions alternent, le zigzag signale un mauvais conditionnement. Un préconditionnement ou la méthode du gradient conjugué est alors souvent plus approprié pour une quadratique définie positive.
À ne pas confondre
Gradient à pas fixe. Le coefficient est choisi à l'avance et reste constant, tandis que le pas optimal résout une minimisation sur la ligne à chaque itération. Si deux itérations utilisent 0,4 parce que la recherche exacte le redonne, le pas n'est pas devenu fixe pour autant.
Recherche linéaire approchée. Elle accepte un pas qui vérifie des conditions de décroissance sans exiger le minimum exact de la restriction à la ligne. Un pas satisfaisant mais distinct du minimiseur relève de cette variante approchée.
Gradient conjugué. Pour une quadratique définie positive, ses directions sont conjuguées relativement à la matrice de la forme quadratique ; elles ne sont pas simplement les opposés des gradients successifs. Le test porte donc sur les directions employées, pas sur la seule présence d'une recherche de pas.
Limites et pièges
Optimal ne signifie pas global. Le pas minimise f uniquement sur la demi-droite xk − αgk. Une fonction non convexe peut conduire à un point stationnaire qui n'est pas un minimum global ; il faut examiner la géométrie de f ou recourir à plusieurs points de départ.
Le cas gk = 0 est charnière. La direction de descente est alors nulle et tout pas laisse le point inchangé. Sans convexité, ce constat prouve seulement que le point est stationnaire ; une étude locale supplémentaire est nécessaire.
Le mauvais conditionnement ralentit la progression. Sur une quadratique définie positive, un grand rapport entre la plus forte et la plus faible courbure produit des courbes de niveau allongées. Le symptôme est une alternance de directions presque transversales au trajet vers le minimum ; un préconditionnement ou le gradient conjugué réduit ce phénomène.
L'exactitude peut être coûteuse ou illusoire. Une recherche numérique interne n'obtient généralement qu'une approximation, et des données bruitées déplacent le minimum observé sur la ligne. Il faut annoncer une tolérance et préférer une condition de décroissance lorsque le pas exact ne peut pas être certifié.
Pour aller plus loin
Le gradient conjugué montre comment remplacer le zigzag des directions de plus forte pente par des directions adaptées à une forme quadratique.
Le conditionnement précise pourquoi un fort contraste entre les courbures peut rendre la convergence lente, même lorsque chaque pas est optimal sur sa ligne.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres