Calcul I MTH1101 • Polytechnique Montréal

Fiche de révision : la méthode du gradient (MTH1101, Polytechnique)

Cette fiche de révision porte sur la méthode du gradient telle que MTH1101 l'enseigne à Polytechnique, d'après la section 5.2 de Stewart, *Calcul à plusieurs variables* (« Optimisation sans contraintes, recherche linéaire et méthode du gradient »), appuyée sur les notes du professeur : itération x⃗k+1=x⃗k−tk∇f(x⃗k)\vec x_{k+1}=\vec x_{k}-t_{k}\nabla f(\vec x_{k}), recherche linéaire exacte, pas fixe, orthogonalité des gradients successifs, critère d'arrêt.

Ce que couvre la fiche

Elle ne refait pas le cours, elle dit ce qui coûte des points. À l'examen final, sans calculatrice ; seul document permis, votre aide-mémoire d'une feuille recto verso, et cette fiche dit quoi y mettre, le bloc « à savoir par cœur » en étant le noyau. L'examen fait faire une à trois itérations à la main sur une quadratique choisie pour donner des fractions, et on JUSTIFIE : pourquoi ce pas, pourquoi cet angle droit, pourquoi ce zigzag.

  • 8 pièges qui coûtent des points
  • 11 figures
  • 15 min de lecture
Faire les exercices du chapitre

Le fil du chapitre

−∇f-\nabla f dit où la pente est la plus raide ICI, pas où se trouve le minimum. La méthode du gradient est donc un ALGORITHME qui corrige sa direction à chaque pas, et le pas tt se CHOISIT : trop grand, il fait remonter ou diverger ; exact, il impose un virage à angle droit.

Notions couvertes

  • Méthode du gradient
  • Direction de plus forte descente
  • Recherche linéaire exacte
  • Pas optimal
  • Pas fixe
  • Matrice hessienne
  • Gradients successifs orthogonaux
  • Convergence linéaire
  • Critère d'arrêt
  • Courbes de niveau
  • Taux d'apprentissage

L'essentiel

La direction de plus forte descente est locale

  • • En un point x⃗k\vec x_{k} où ∇f≠0⃗\nabla f\neq\vec 0, la direction −∇f(x⃗k)-\nabla f(\vec x_{k}) est celle où ff décroît le plus vite, au taux −∥∇f(x⃗k)∥-\|\nabla f(\vec x_{k})\|. Elle est perpendiculaire à la courbe de niveau qui passe par x⃗k\vec x_{k}.
  • • Elle ne vise le minimum que si les courbes de niveau sont des cercles, ou si le point est sur un axe de l'ellipse. Sinon il faut plusieurs pas, et la méthode CORRIGE sa direction à chaque itération : x⃗k+1=x⃗k−tk∇f(x⃗k)\vec x_{k+1}=\vec x_{k}-t_{k}\nabla f(\vec x_{k}), avec tk>0t_{k}>0.
  • • φ(t)=f(x⃗k−t∇f(x⃗k))\varphi(t)=f\left(\vec x_{k}-t\nabla f(\vec x_{k})\right) est la coupe de ff le long de la droite de recherche. Elle vérifie φ(0)=f(x⃗k)\varphi(0)=f(\vec x_{k}) et φ′(0)=−∥∇f(x⃗k)∥2<0\varphi'(0)=-\|\nabla f(\vec x_{k})\|^{2}<0 : on descend au départ, rien de plus.
x² + 2y² = 6x² + y² = 5PQ
En P(2 ;1)P(2\,;1), la flèche −∇f-\nabla f part perpendiculairement à l'ellipse et manque le centre, que vise le pointillé ; en QQ, sur le cercle, elle vise le centre.

Une direction de descente garantit qu'un pas ASSEZ PETIT fait baisser ff. Elle ne dit ni jusqu'où aller, ni où est le minimum.

Les deux façons de choisir le pas

  • • RECHERCHE LINÉAIRE EXACTE : tkt_{k} minimise φ\varphi sur [0 ;+∞[[0\,;+\infty[. Pour une quadratique f(x⃗)=12x⃗⋅Hx⃗−b⃗⋅x⃗+cf(\vec x)=\frac{1}{2}\vec x\cdot H\vec x-\vec b\cdot\vec x+c, avec g⃗=∇f(x⃗k)\vec g=\nabla f(\vec x_{k}) : tk=g⃗⋅g⃗g⃗⋅Hg⃗t_{k}=\dfrac{\vec g\cdot\vec g}{\vec g\cdot H\vec g}, où HH est la HESSIENNE.
  • • Conséquence : ∇f(x⃗k+1)⋅∇f(x⃗k)=0\nabla f(\vec x_{k+1})\cdot\nabla f(\vec x_{k})=0. Deux pas successifs sont perpendiculaires, d'où le zigzag.
  • • PAS FIXE : le même tt à chaque itération. Sur x2+κy2x^{2}+\kappa y^{2}, les coordonnées sont multipliées par 1−2t1-2t et 1−2κt1-2\kappa t ; il faut ∣1−2t∣<1|1-2t|<1 ET ∣1−2κt∣<1|1-2\kappa t|<1, la plus forte courbure impose la borne.
  • • ARRÊT : ∥∇f(x⃗k)∥<ε\|\nabla f(\vec x_{k})\|<\varepsilon, la seule quantité calculable sans connaître le minimum.
−2−112−11x₀x₁
Recherche linéaire exacte sur x2+2y2x^2+2y^2 depuis (2 ;1)(2\,;1) : chaque pas s'arrête où la droite touche une ellipse, et le suivant part à angle droit. Les itérés se rapprochent du centre en zigzag.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Oublier le signe moins de l'itération

toute la méthode, même si le point final est juste

Ce qu'il ne faut pas écrire

« x⃗1=x⃗0+t∇f(x⃗0)\vec x_{1}=\vec x_{0}+t\nabla f(\vec x_{0}), et φ\varphi est minimale en t=−14t=-\frac{1}{4}. »

Ce qu'il faut écrire

« x⃗1=x⃗0−t∇f(x⃗0)\vec x_{1}=\vec x_{0}-t\nabla f(\vec x_{0}) avec t>0t>0 ; contrôle : φ′(0)=−∥∇f(x⃗0)∥2<0\varphi'(0)=-\|\nabla f(\vec x_{0})\|^{2}<0. »

−0,4−0,20,20,40,6246810121416t = 1/4 > 0t = −1/4φ(0) = 8t
Avec le signe moins, φ(t)=80t2−40t+8\varphi(t)=80t^2-40t+8 descend au départ et atteint son minimum en t=14t=\frac14 (en vert). Avec le plus, le minimum tombe en t<0t<0 (en rouge) : on est parti vers le haut.

Pourquoi : Un pas optimal NÉGATIF est le symptôme : on est parti dans la direction de plus forte montée. Deux erreurs de signe qui se compensent donnent le bon point, et le correcteur retire quand même les points de la méthode.

2. Prendre la matrice des coefficients pour la hessienne

2 points, et aucune itération juste ensuite

Ce qu'il ne faut pas écrire

« f=2x2−3xy+3y2=x⃗⋅Ax⃗f=2x^{2}-3xy+3y^{2}=\vec x\cdot A\vec x avec A=(2−32−323)A=\begin{pmatrix}2&-\frac{3}{2}\\-\frac{3}{2}&3\end{pmatrix}, donc t0=g⃗⋅g⃗g⃗⋅Ag⃗=12t_{0}=\frac{\vec g\cdot\vec g}{\vec g\cdot A\vec g}=\frac{1}{2}. »

Ce qu'il faut écrire

« H=(4−3−36)=2AH=\begin{pmatrix}4&-3\\-3&6\end{pmatrix}=2A (dérivées secondes), donc t0=40160=14t_{0}=\frac{40}{160}=\frac{1}{4}. »

−0,10,10,20,30,40,50,612345678910t₀ = 1/4 : hessienne H1/2 : matrice A, φ = 8t
φ\varphi est une parabole symétrique autour du bon pas t0=14t_0=\frac14 (en vert) : le pas double, 12\frac12 (en rouge), ramène exactement à φ=8\varphi=8, sans aucun progrès.

Pourquoi : Depuis (2 ;2)(2\,;2), le pas doublé mène en (1 ;−1)(1\,;-1) où f=8=f(x⃗0)f=8=f(\vec x_{0}) : φ\varphi est une parabole symétrique autour de t0t_{0}, donc φ(2t0)=φ(0)\varphi(2t_{0})=\varphi(0). Aucun progrès, et la copie ne s'en aperçoit pas sans calculer ff.

3. Prendre une baisse au premier pas pour une preuve de convergence

toute la question de convergence

Ce qu'il ne faut pas écrire

« Avec t=0,3t=0{,}3 sur f=x2+4y2f=x^{2}+4y^{2}, ff passe de 1010 à 3,43{,}4 : le pas convient. »

Ce qu'il faut écrire

« Les facteurs sont 1−2t=0,41-2t=0{,}4 et 1−8t=−1,41-8t=-1{,}4 ; ∣−1,4∣>1|-1{,}4|>1, donc yky_{k} diverge. Il faut 0<t<140<t<\frac{1}{4}. »

−11234−2−1,5−1−0,50,511,52x₀x₁x₂x₃
Le trajet traverse la vallée en s'élargissant : xkx_{k} fond, mais ∣yk∣|y_{k}| est multiplié par 1,41{,}4 à chaque pas, et ff remonte dès x⃗2\vec x_{2}.

Pourquoi : Le premier pas gagne sur xx, qui pesait lourd, et perd sur yy. Ensuite ff vaut 4,0724{,}072 puis environ 7,577{,}57 : les itérés sautent d'un bord à l'autre de la vallée, toujours plus haut.

4. Croire que le meilleur pas mène au minimum

1 à 2 points d'interprétation

Ce qu'il ne faut pas écrire

« Avec la recherche exacte, on atteint le minimum de x2+2y2x^{2}+2y^{2} en un pas depuis (2 ;1)(2\,;1). »

Ce qu'il faut écrire

« Le pas exact t0=13t_{0}=\frac{1}{3} donne (23 ;−13)\left(\frac{2}{3}\,;-\frac{1}{3}\right), où f=23f=\frac{2}{3} : c'est le minimum SUR LA DROITE de recherche, pas dans le plan. »

−112−11(2 ; 1)x₁ : f = 2/3
La droite de recherche (en orange) passe à côté de l'origine : son meilleur point (23 ;−13)\left(\frac23\,;-\frac13\right) est celui où elle touche l'ellipse f=23f=\frac23 (en vert), pas le minimum.

Pourquoi : La droite de recherche ne passe par le minimum que si −∇f-\nabla f le vise. Ici ff est divisée par 99 à chaque pas, sans jamais atteindre 00.

5. Normaliser la direction et garder le même pas

1 point par itération

Ce qu'il ne faut pas écrire

« Sur x2+y2x^{2}+y^{2} depuis (−6 ;8)(-6\,;8), le pas optimal vaut 12\frac{1}{2}, donc j'avance de 12\frac{1}{2} selon 120(6 ;−8)\frac{1}{20}(6\,;-8). »

Ce qu'il faut écrire

« Avec −∇f=(12 ;−16)-\nabla f=(12\,;-16), t=12t=\frac{1}{2} ; avec le vecteur unitaire, le pas devient s=∥∇f∥ t=10s=\|\nabla f\|\,t=10. Le point d'arrivée, l'origine, est le même. »

Pourquoi : Le nombre tt dépend de la longueur du vecteur direction, le point x⃗k+1\vec x_{k+1} non. Respectez la convention de l'énoncé, x⃗k−t∇f(x⃗k)\vec x_{k}-t\nabla f(\vec x_{k}) sans normaliser.

6. Prendre un petit gradient pour la proximité du minimum

1 point d'interprétation

Ce qu'il ne faut pas écrire

« ∥∇f(x⃗k)∥<10−2\|\nabla f(\vec x_{k})\|<10^{-2}, donc x⃗k\vec x_{k} est à moins de 10−210^{-2} du minimum. »

Ce qu'il faut écrire

« Le critère dit que la pente est faible ; sur x21000+y2\frac{x^{2}}{1000}+y^{2}, le point (1 ;0)(1\,;0) a un gradient de norme 0,0020{,}002 et se trouve à distance 11 du minimum. »

−1,5−1−0,50,511,50,511,522,5en (1 ; 0) : pente 0,002, distance 1xf (millièmes)
Le profil x21000\frac{x^2}{1000}, en millièmes, est presque plat : en x=1x=1, la pente ne vaut que 0,0020{,}002 (en rouge), et pourtant le minimum (en vert) est à une distance 11.

Pourquoi : Une fonction très plate dans une direction a un petit gradient loin de son minimum. Le critère est un critère d'ARRÊT pratique, pas une garantie de précision sur x⃗\vec x.

7. Prendre le point d'arrêt pour un minimum

2 points de classification

Ce qu'il ne faut pas écrire

« Sur f(x,y)=xyf(x,y)=xy depuis (1 ;1)(1\,;1), la méthode arrive en (0 ;0)(0\,;0) où ∇f=0⃗\nabla f=\vec 0 : c'est le minimum. »

Ce qu'il faut écrire

« φ(t)=(1−t)2\varphi(t)=(1-t)^{2} donne t=1t=1 et (0 ;0)(0\,;0), point CRITIQUE ; D=0×0−12=−1<0D=0\times 0-1^{2}=-1<0 : c'est un point de selle. »

−2−1,5−1−0,50,511,52−2−1,5−1−0,50,511,52(1 ; 1)sellef = −1
Sur f=xyf=xy, la descente depuis (1 ;1)(1\,;1) s'arrête à l'origine, où ∇f=0⃗\nabla f=\vec 0 ; mais ff y est encadrée par 11 (en bleu) et −1-1 (en rouge) : c'est une selle.

Pourquoi : La méthode s'arrête où le gradient s'annule, c'est-à-dire en un point critique ; elle ne le classe pas. Le test des dérivées secondes reste à faire, et f(1 ;−1)=−1<0f(1\,;-1)=-1<0 le confirme.

8. Annoncer le minimum après deux itérations

1 point de conclusion

Ce qu'il ne faut pas écrire

« Après deux pas, x⃗2=(34 ;34)\vec x_{2}=\left(\frac{3}{4}\,;\frac{3}{4}\right) : c'est le minimum de 2x2−3xy+3y22x^{2}-3xy+3y^{2}. »

Ce qu'il faut écrire

« ∇f(x⃗2)=(34 ;94)≠0⃗\nabla f(\vec x_{2})=\left(\frac{3}{4}\,;\frac{9}{4}\right)\neq\vec 0 : on n'y est pas. Le minimum exact, par ∇f=0⃗\nabla f=\vec 0, est (0 ;0)(0\,;0), et f(x⃗2)=98f(\vec x_{2})=\frac{9}{8}. »

−1123−1123x₀x₁x₂ : ∇f ≠ 0minimum en (0 ; 0)
x⃗0\vec x_0, x⃗1\vec x_1, x⃗2\vec x_2 sur les ellipses f=8f=8, 33, 98\frac98 : le dernier itéré a encore un gradient non nul, le minimum (0 ;0)(0\,;0) (en vert) n'est pas atteint.

Pourquoi : Sur une quadratique non circulaire, la méthode du gradient n'atteint pas le minimum en un nombre fini de pas : elle s'en approche à vitesse constante. Calculer le gradient au dernier itéré est la vérification qui coûte cinq secondes.

Quelle méthode choisir

Comment trouver le pas selon l'énoncé

Regardez la forme de f et ce que l'énoncé impose.

  • Si ff quadratique, « recherche linéaire exacte » → tk=g⃗⋅g⃗g⃗⋅Hg⃗t_{k}=\frac{\vec g\cdot\vec g}{\vec g\cdot H\vec g} avec la hessienne, ou φ′(t)=0\varphi'(t)=0 sur la parabole φ\varphi

    Exemple : 2x2−3xy+3y22x^{2}-3xy+3y^{2} en (2 ;2)(2\,;2) : g⃗=(2 ;6)\vec g=(2\,;6), t0=40160=14t_{0}=\frac{40}{160}=\frac{1}{4}

  • Si ff non quadratique, « recherche linéaire exacte » → écrire φ(t)\varphi(t), chercher une racine évidente de φ′\varphi', puis prouver qu'elle est unique (monotonie de φ′\varphi')

    Exemple : φ′(t)=128t3+8t−4\varphi'(t)=128t^{3}+8t-4, croissante, racine 14\frac{1}{4}

  • Si « pas fixe tt », ff de la forme ax2+by2ax^{2}+by^{2} → écrire les facteurs 1−2at1-2at et 1−2bt1-2bt et comparer leurs valeurs absolues à 11

    Exemple : x2+4y2x^{2}+4y^{2}, t=0,3t=0{,}3 : facteurs 0,40{,}4 et −1,4-1{,}4, divergence

  • Si « choisir le meilleur pas fixe » → égaler les valeurs absolues des deux facteurs extrêmes

    Exemple : x2+4y2x^{2}+4y^{2} : 1−2t=8t−11-2t=8t-1, t=15t=\frac{1}{5}, facteur 35\frac{3}{5}

La méthode de Newton à plusieurs variables est hors du cours : on ne remplace jamais t∇ft\nabla f par H−1∇fH^{-1}\nabla f.

Que prévoir en lisant la carte de contour

Regardez la forme des courbes de niveau et la position du point de départ.

  • Si des cercles → le gradient vise le centre : un pas exact suffit

    Exemple : x2+y2x^{2}+y^{2} depuis (−6 ;8)(-6\,;8) : t=12t=\frac{1}{2}, arrivée en (0 ;0)(0\,;0)

  • Si des ellipses, départ sur un axe → un pas exact suffit aussi

    Exemple : x2+2y2x^{2}+2y^{2} depuis (3 ;0)(3\,;0) : ∇f=(6 ;0)\nabla f=(6\,;0), t=12t=\frac{1}{2}, arrivée en (0 ;0)(0\,;0)

  • Si des ellipses allongées, départ quelconque → zigzag à angles droits, convergence lente

    Exemple : x2+2y2x^{2}+2y^{2} depuis (2 ;1)(2\,;1) : ff divisée par 99 à chaque pas

  • Si une vallée courbe (bananes) → progrès rapide vers le fond, puis lent le long du fond

    Exemple : 2(x2−y)2+(1−x)22(x^{2}-y)^{2}+(1-x)^{2} : le fond est la parabole y=x2y=x^{2}

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Une itération avec recherche linéaire exacte

Quand l'utiliser : L'énoncé dit « effectuez une itération de la méthode du gradient avec recherche linéaire exacte ».

  1. 1 Calculer ∇f(x⃗k)\nabla f(\vec x_{k}) et l'écrire ; s'il est nul, s'arrêter : x⃗k\vec x_{k} est un point critique.
  2. 2 Écrire le point courant x⃗k−t∇f(x⃗k)\vec x_{k}-t\nabla f(\vec x_{k}), puis φ(t)\varphi(t) développée (ou la formule du pas si ff est quadratique, avec la HESSIENNE).
  3. 3 Résoudre φ′(t)=0\varphi'(t)=0 et justifier que c'est un minimum : φ′′>0\varphi''>0, ou g⃗⋅Hg⃗>0\vec g\cdot H\vec g>0.
  4. 4 Donner x⃗k+1\vec x_{k+1} et f(x⃗k+1)f(\vec x_{k+1}), et vérifier que ff a baissé.
  5. 5 Contrôler l'orthogonalité ∇f(x⃗k+1)⋅∇f(x⃗k)=0\nabla f(\vec x_{k+1})\cdot\nabla f(\vec x_{k})=0.

Phrase de conclusion

« Le pas optimal est tk=…>0t_{k}=…>0, minimum de φ\varphi car φ′′(t)>0\varphi''(t)>0 ; donc x⃗k+1=…\vec x_{k+1}=… et f(x⃗k+1)=…<f(x⃗k)f(\vec x_{k+1})=…<f(\vec x_{k}), avec ∇f(x⃗k+1)⊥∇f(x⃗k)\nabla f(\vec x_{k+1})\perp\nabla f(\vec x_{k}). »

Le piège : La troisième étape : un pas sans justification de minimum est un point critique de φ, pas encore un minimum.

Barème : Gradient 1 point, φ ou formule 1 point, pas justifié 1 point, nouvel itéré et valeur 1 point.

Démontrer que deux gradients successifs sont orthogonaux

Quand l'utiliser : L'énoncé demande de prouver le virage à angle droit de la recherche exacte.

  1. 1 Poser φ(t)=f(x⃗k−tg⃗k)\varphi(t)=f\left(\vec x_{k}-t\vec g_{k}\right) avec g⃗k=∇f(x⃗k)\vec g_{k}=\nabla f(\vec x_{k}).
  2. 2 Dériver par la règle de dérivation en chaîne : φ′(t)=−∇f(x⃗k−tg⃗k)⋅g⃗k\varphi'(t)=-\nabla f\left(\vec x_{k}-t\vec g_{k}\right)\cdot\vec g_{k}.
  3. 3 Écrire que tk>0t_{k}>0 est un minimum intérieur, donc φ′(tk)=0\varphi'(t_{k})=0.
  4. 4 Conclure : ∇f(x⃗k+1)⋅g⃗k=0\nabla f(\vec x_{k+1})\cdot\vec g_{k}=0.

Phrase de conclusion

« Comme tkt_{k} minimise φ\varphi sur ]0 ;+∞[]0\,;+\infty[, φ′(tk)=−∇f(x⃗k+1)⋅∇f(x⃗k)=0\varphi'(t_{k})=-\nabla f(\vec x_{k+1})\cdot\nabla f(\vec x_{k})=0 : les deux gradients sont orthogonaux. »

Le piège : Écrire la conclusion sans la règle de dérivation en chaîne : c'est elle que le correcteur note.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

  • Le signe de φ'(0)

    Calculer φ′(0)\varphi'(0) sur votre φ\varphi développée : il doit valoir −∥∇f(x⃗k)∥2-\|\nabla f(\vec x_{k})\|^{2}.

    Avec g⃗=(2 ;6)\vec g=(2\,;6), on attend φ′(0)=−40\varphi'(0)=-40 ; un φ′(0)=+40\varphi'(0)=+40 trahit un signe moins oublié.

  • f a-t-elle baissé ?

    Recalculer f(x⃗k+1)f(\vec x_{k+1}) directement dans ff, pas dans φ\varphi.

    f(x⃗1)=3<8=f(x⃗0)f(\vec x_{1})=3<8=f(\vec x_{0}) confirme ; un f(x⃗1)=8f(\vec x_{1})=8 signale le pas doublé de la hessienne.

  • L'angle droit

    Calculer ∇f(x⃗k+1)⋅∇f(x⃗k)\nabla f(\vec x_{k+1})\cdot\nabla f(\vec x_{k}) : il vaut 00 en recherche exacte.

    (2 ;6)⋅(92 ;−32)=9−9=0(2\,;6)\cdot\left(\frac{9}{2}\,;-\frac{3}{2}\right)=9-9=0 ; un résultat non nul dit que le pas ou le gradient est faux.

  • Le pas est-il positif ?

    Un tk≤0t_{k}\leq 0 est impossible avec −∇f-\nabla f comme direction.

    Un t=−14t=-\frac{1}{4} veut dire qu'on a minimisé le long de +∇f+\nabla f.

L'exercice type décortiqué

Deux itérations sur f(x,y)=2x2−3xy+3y2f(x,y)=2x^{2}-3xy+3y^{2}

Effectuez deux itérations de la méthode du gradient avec recherche linéaire exacte, à partir de x⃗0=(2 ;2)\vec x_{0}=(2\,;2). Comparez au minimum exact.

−3−2−1123−2,5−2−1,5−1−0,50,511,522,5x₀f = 8
Les courbes de niveau sont des ellipses inclinées et x⃗0\vec x_{0} n'est sur aucun de leurs axes : il faudra plusieurs pas.

Étape 1

∇f=(4x−3y ;−3x+6y)\nabla f=(4x-3y\,;-3x+6y), donc g⃗0=∇f(2 ;2)=(2 ;6)\vec g_{0}=\nabla f(2\,;2)=(2\,;6) et f(x⃗0)=8f(\vec x_{0})=8. Hessienne H=(4−3−36)H=\begin{pmatrix}4&-3\\-3&6\end{pmatrix}.

Pourquoi

Écrire la hessienne avant tout calcul de pas évite le piège du facteur 2.

Étape 2

φ(t)=f(2−2t ;2−6t)=80t2−40t+8\varphi(t)=f(2-2t\,;2-6t)=80t^{2}-40t+8, minimale en t0=14t_{0}=\frac{1}{4} (φ′′=160>0\varphi''=160>0). Formule : g⃗⋅g⃗g⃗⋅Hg⃗=40160\frac{\vec g\cdot\vec g}{\vec g\cdot H\vec g}=\frac{40}{160}.

Pourquoi

Les deux chemins donnent le même pas ; φ′(0)=−40=−∥g⃗0∥2\varphi'(0)=-40=-\|\vec g_{0}\|^{2} contrôle le signe.

Étape 3

x⃗1=(2 ;2)−14(2 ;6)=(32 ;12)\vec x_{1}=(2\,;2)-\frac{1}{4}(2\,;6)=\left(\frac{3}{2}\,;\frac{1}{2}\right), f(x⃗1)=92−94+34=3f(\vec x_{1})=\frac{9}{2}-\frac{9}{4}+\frac{3}{4}=3.

Pourquoi

On recalcule f dans f, pas dans φ : c'est la vérification de la baisse, de 8 à 3.

Étape 4

g⃗1=(6−32 ;−92+3)=(92 ;−32)\vec g_{1}=\left(6-\frac{3}{2}\,;-\frac{9}{2}+3\right)=\left(\frac{9}{2}\,;-\frac{3}{2}\right), et g⃗0⋅g⃗1=9−9=0\vec g_{0}\cdot\vec g_{1}=9-9=0.

Pourquoi

L'angle droit est attendu ; s'il manque, une erreur précède.

Étape 5

g⃗1⋅g⃗1=452\vec g_{1}\cdot\vec g_{1}=\frac{45}{2}, Hg⃗1=(452 ;−452)H\vec g_{1}=\left(\frac{45}{2}\,;-\frac{45}{2}\right), g⃗1⋅Hg⃗1=135\vec g_{1}\cdot H\vec g_{1}=135, donc t1=16t_{1}=\frac{1}{6} et x⃗2=(34 ;34)\vec x_{2}=\left(\frac{3}{4}\,;\frac{3}{4}\right), f(x⃗2)=98f(\vec x_{2})=\frac{9}{8}.

−3−2−1123−2,5−2−1,5−1−0,50,511,522,5x₀x₁x₂

Pourquoi

Le pas change d'une itération à l'autre (14\frac{1}{4} puis 16\frac{1}{6}) : la recherche exacte s'adapte à la courbure de chaque direction.

Étape 6

∇f=0⃗\nabla f=\vec 0 donne 4x=3y4x=3y et 3x=6y3x=6y, d'où (0 ;0)(0\,;0), minimum car 4>04>0 et det⁡H=15>0\det H=15>0. Et x⃗2=38x⃗0\vec x_{2}=\frac{3}{8}\vec x_{0} : ff est multipliée par 38\frac{3}{8} à chaque pas.

Pourquoi

La comparaison au minimum exact mesure la vitesse de la méthode, c'est la question qui suit toujours à l'examen.

Conclusion rédigée

« Après deux itérations, x⃗2=(34 ;34)\vec x_{2}=\left(\frac{3}{4}\,;\frac{3}{4}\right) et f(x⃗2)=98f(\vec x_{2})=\frac{9}{8}, contre f∗=0f^{*}=0 en (0 ;0)(0\,;0) ; chaque itération multiplie ff par 38\frac{3}{8}, la méthode converge sans atteindre le minimum. »

L'erreur classique sur cet exercice : Calculer le pas avec A=(2−32−323)A=\begin{pmatrix}2&-\frac{3}{2}\\-\frac{3}{2}&3\end{pmatrix} : on trouve 12\frac{1}{2} et l'on arrive en (1 ;−1)(1\,;-1), où ff vaut encore 88.

À savoir par cœur

  • • x⃗k+1=x⃗k−tk∇f(x⃗k)\vec x_{k+1}=\vec x_{k}-t_{k}\nabla f(\vec x_{k}), avec tk>0t_{k}>0 : le signe MOINS, toujours.
  • • φ(t)=f(x⃗k−t∇f(x⃗k))\varphi(t)=f\left(\vec x_{k}-t\nabla f(\vec x_{k})\right) et φ′(0)=−∥∇f(x⃗k)∥2\varphi'(0)=-\|\nabla f(\vec x_{k})\|^{2}.
  • • Quadratique : tk=g⃗⋅g⃗g⃗⋅Hg⃗t_{k}=\frac{\vec g\cdot\vec g}{\vec g\cdot H\vec g}, avec la HESSIENNE, celle des dérivées secondes.
  • • Recherche exacte : deux gradients successifs sont ORTHOGONAUX ; en dimension deux, les directions kk et k+2k+2 sont parallèles.
  • • Pas fixe sur x2+κy2x^{2}+\kappa y^{2} : facteurs 1−2t1-2t et 1−2κt1-2\kappa t, convergence si et seulement si les deux sont dans ]−1 ;1[]-1\,;1[.
  • • Zigzag sur x2+κy2x^{2}+\kappa y^{2} depuis (κ ;1)(\kappa\,;1) : ff multipliée par (κ−1κ+1)2\left(\frac{\kappa-1}{\kappa+1}\right)^{2} à chaque pas.
  • • Arrêt : ∥∇f∥<ε\|\nabla f\|<\varepsilon, en un point CRITIQUE qu'il reste à classer.

Questions fréquentes

Pourquoi la méthode du gradient avance-t-elle en zigzag ?

Parce qu'avec la recherche linéaire exacte, on s'arrête sur chaque droite au point où elle devient tangente à une courbe de niveau. Le nouveau gradient y est perpendiculaire à la droite, donc chaque pas tourne d'un angle droit par rapport au précédent. Dans une vallée allongée, ces virages successifs font un zigzag serré et lent vers le minimum.

Comment calculer le pas optimal à la main pour une fonction quadratique ?

On calcule le gradient g au point courant et la matrice hessienne H, celle des dérivées secondes. Le pas optimal vaut g scalaire g divisé par g scalaire H fois g. On peut aussi écrire la fonction phi de t le long de la droite de recherche, qui est une parabole, et prendre son sommet. Les deux calculs doivent donner le même nombre.

Pourquoi la méthode diverge-t-elle avec un pas fixe trop grand ?

Parce que la direction de descente ne garantit une baisse que pour un petit pas. Sur une fonction comme x carré plus kappa y carré, chaque coordonnée est multipliée à chaque pas par un facteur constant, un moins deux t et un moins deux kappa t. Si l'un de ces facteurs dépasse un en valeur absolue, la coordonnée grandit et les itérés s'éloignent du minimum.

Quand faut-il arrêter la méthode du gradient ?

On s'arrête quand la norme du gradient passe sous une tolérance fixée d'avance, par exemple un millième, parce que c'est la seule quantité calculable sans connaître le minimum. Ce critère ne garantit pas que le point soit proche du minimum, et le point atteint est seulement un point critique : il faut encore le classer, par le test des dérivées secondes.

Marque ici la fiche comme lue ou mets-la en favori : un compte gratuit, sans mot de passe, retient tes fiches lues et tes favoris d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander la méthode ou l'exercice qui te manque. Crée ton espace, un courriel suffit.

Passer à la pratique

Exercices corrigés : La méthode du gradient

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

  • 10 exercices corrigés
  • 100 points
  • 150 minutes
Faire les exercices
Il manque quelque chose dans cette fiche ? Une méthode, un piège, un exercice pour l'appliquer, une erreur repérée : dis-le-moi, je lis chaque demande.

L'envoi passe par ton espace gratuit : c'est ce qui me permet de te répondre et de te prévenir quand l'exercice est ajouté. Un courriel suffit, pas de mot de passe. Crée ton espace. Pas envie de créer un compte ? Écris-moi directement.

De quoi s'agit-il ?
Je lis chaque demande moi-même, personne d'autre ne la voit. Inutile d'écrire ton nom ou celui de ton école.
Quand ta demande est traitée, tu es prévenu par courriel et dans ton espace.

En envoyant, tu acceptes que je lise ta demande pour y répondre. Elle est gardée avec ton compte, effacée avec lui, et jamais publiée : politique de confidentialité.

© Ahmed Squalli Houssaini. Fiche publiée sur www.letuteurscientifique.ca/fiches/mth1101-methode-gradient. Libre pour l'usage personnel et en classe ; sa republication ailleurs demande une autorisation écrite (mentions légales).

Vous cherchez un tuteur à Montréal pour ce chapitre ?

Contactez-moi pour une première séance. On reprend les points de méthode qui font perdre des points en évaluation, puis on les met à l'épreuve sur des exercices du niveau réel de l'examen.

Site par Studio Squalli