Calcul I MTH1101 • Polytechnique Montréal • La méthode du gradient

La méthode du gradient : exercices corrigés de MTH1101 (Polytechnique)

Voici dix exercices corrigés sur la méthode du gradient, l'algorithme d'optimisation de la section 5.2 de Stewart, *Calcul à plusieurs variables* (« Optimisation sans contraintes, recherche linéaire et méthode du gradient »), que le cours MTH1101 de Polytechnique Montréal appuie sur les notes du professeur, après les extrema sans contrainte et avant les multiplicateurs de Lagrange. Le chapitre est évalué à l'examen final. On ne cherche plus le minimum en résolvant $\nabla f=\vec 0$ : on part d'un point et on descend, $\vec x_{k+1}=\vec x_{k}-t_{k}\nabla f(\vec x_{k})$ , comme le font les logiciels d'ingénierie et d'apprentissage automatique.

Le fil de la série : $-\nabla f$ dit où la pente est la plus raide ICI, pas où se trouve le minimum. La méthode est donc un ALGORITHME qui corrige sa direction à chaque pas, et le pas $t$ se CHOISIT : trop grand, il fait remonter ou diverger ; exact, il impose un virage à angle droit, d'où le zigzag dans une vallée allongée.

Les pièges nommés en chemin : le signe moins oublié, un pas négatif qui trahit la mauvaise direction, la matrice des coefficients prise pour la hessienne (le pas doublé ne fait aucun progrès), une baisse au premier pas prise pour une preuve de convergence, un petit gradient pris pour la proximité du minimum, un point de selle pris pour un minimum. Tout se fait sans calculatrice, comme à l'examen, où le seul document permis est votre aide-mémoire d'une feuille recto verso : les fonctions sont choisies pour que les itérés tombent en fractions.

Faites chaque exercice au complet avant d'ouvrir la correction : c'est en cherchant qu'on apprend, pas en lisant la solution.

Série autocorrigée Tape tes réponses et vérifie-les question par question : la page te dit juste ou faux avant d'ouvrir la correction. Avec un compte, chaque bonne réponse du premier coup rapporte des points, et tes réponses justes restent remplies quand tu reviens.

Ce chapitre fait partie de Calcul I MTH1101, Polytechnique Montréal : exercices corrigés et fiches, chapitre par chapitre

Avant de commencer Fiche de révision : les pièges et la méthode de ce chapitre

Avant ce chapitre

Ces notions sont supposées acquises ici. Si le premier exercice résiste, le blocage vient presque toujours de l'une d'elles, pas du chapitre lui-même.

Remonter plus loin : la chaîne complète (8 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

Rappel de cours

• ITÉRATION : $\vec x_{k+1}=\vec x_{k}-t_{k}\nabla f(\vec x_{k})$ , avec $t_{k}>0$ . La direction $-\nabla f(\vec x_{k})$ est celle de plus forte descente, de taux $-\|\nabla f(\vec x_{k})\|$ .
• RECHERCHE LINÉAIRE EXACTE : $t_{k}$ minimise $\varphi(t)=f\left(\vec x_{k}-t\nabla f(\vec x_{k})\right)$ pour $t\geq 0$ ; $\varphi'(0)=-\|\nabla f(\vec x_{k})\|^{2}<0$ .
• QUADRATIQUE $f(\vec x)=\frac{1}{2}\vec x\cdot H\vec x-\vec b\cdot\vec x+c$ , $H$ la hessienne, $\vec g=\nabla f(\vec x_{k})$ : $t_{k}=\dfrac{\vec g\cdot\vec g}{\vec g\cdot H\vec g}$ , et $f$ baisse de $\dfrac{(\vec g\cdot\vec g)^{2}}{2\,\vec g\cdot H\vec g}$ .
• ORTHOGONALITÉ : en recherche exacte, $\nabla f(\vec x_{k+1})\cdot\nabla f(\vec x_{k})=0$ ; la droite de recherche est tangente à une courbe de niveau au point d'arrivée.
• PAS FIXE sur $x^{2}+\kappa y^{2}$ : chaque coordonnée est multipliée par $1-2t$ et $1-2\kappa t$ ; convergence si et seulement si $0<t<\frac{1}{\kappa}$ (pour $\kappa\geq 1$ ).
• ZIGZAG : sur $x^{2}+\kappa y^{2}$ depuis $(\kappa\,;1)$ , $f$ est multipliée par $\left(\frac{\kappa-1}{\kappa+1}\right)^{2}$ à chaque pas ; des cercles ( $\kappa=1$ ) donnent le minimum en un pas.
• ARRÊT : $\|\nabla f(\vec x_{k})\|<\varepsilon$ . On s'arrête en un point CRITIQUE, qui reste à classer, et un petit gradient ne garantit pas la proximité du minimum.

Partie A : les bases (/50)

Exercice 1 : La direction de plus forte descente, et le pas qui fait remonter

On cherche le minimum de $f(x,y)=x^{2}+4y^{2}$ par la méthode du gradient. Partant d'un point $\vec x_{k}$ , la méthode se déplace dans la direction $-\nabla f(\vec x_{k})$ : $\vec x_{k+1}=\vec x_{k}-t\,\nabla f(\vec x_{k})$ , où le nombre $t>0$ s'appelle le PAS.

La figure donne les courbes de niveau $f=2$ , $f=8$ et $f=18$ , et le point de départ $P(2\,;1)$ , qui est sur la courbe $f=8$ .

a) Calculez $\nabla f(P)$ et sa norme, au centième.
b) Donnez le vecteur unitaire $\vec u$ de plus forte descente en $P$ et la dérivée directionnelle $D_{\vec u}f(P)$ , au centième. La direction $-\nabla f(P)$ pointe-t-elle vers le minimum $(0\,;0)$ ? Justifiez, puis dites ce que la figure montre.
c) Faites un pas avec $t=\frac{1}{10}$ : donnez $\vec x_{1}$ et $f(\vec x_{1})$ .
d) Refaites ce pas avec $t=\frac{1}{2}$ et calculez $f(\vec x_{1})$ . En étudiant $\varphi(t)=f\left(P-t\,\nabla f(P)\right)$ , trouvez tous les pas $t>0$ qui font réellement descendre.

Tape tes réponses, la page te dit juste ou faux 0/10

a)

\frac{\partial f}{\partial x}(P)

\frac{\partial f}{\partial y}(P)

\|\nabla f(P)\|

b)

D_{\vec u}f(P)

Vers le minimum ?

c)

x

de

\vec x_{1}

y

de

\vec x_{1}

f(\vec x_{1})

d)

f(\vec x_{1})

pour

t=\frac{1}{2}

Pas qui font descendre ;

Voir la correction

Réponses

a) $\nabla f(P)=(4\,;8)$ , $\|\nabla f(P)\|=4\sqrt{5}\approx 8{,}94$
b) $\vec u=-\frac{1}{\sqrt{5}}(1\,;2)$ , $D_{\vec u}f(P)=-4\sqrt{5}\approx -8{,}94$ ; non, la droite de descente passe par $(0\,;-3)$ , pas par l'origine
c) $\vec x_{1}=\left(\frac{8}{5}\,;\frac{1}{5}\right)$ , $f(\vec x_{1})=\frac{68}{25}=2{,}72$
d) $\vec x_{1}=(0\,;-3)$ , $f(\vec x_{1})=36>8$ ; $\varphi(t)=272t^{2}-80t+8<8\iff 0<t<\frac{5}{17}$

a) $\frac{\partial f}{\partial x}=2x$ et $\frac{\partial f}{\partial y}=8y$ , donc $\nabla f(P)=(4\,;8)$ et $\|\nabla f(P)\|=\sqrt{16+64}=\sqrt{80}=4\sqrt{5}\approx 8{,}94$ . Le gradient a une composante en $y$ double de celle en $x$ alors que $P$ est deux fois plus loin de l'axe des ordonnées que de l'axe des abscisses : c'est le facteur $4$ devant $y^{2}$ qui rend la fonction quatre fois plus « raide » dans la direction $y$ .

b) La plus forte descente se fait dans la direction opposée au gradient : $\vec u=-\dfrac{\nabla f(P)}{\|\nabla f(P)\|}=-\dfrac{1}{\sqrt{5}}(1\,;2)$ , et le taux de variation y vaut $D_{\vec u}f(P)=\nabla f(P)\cdot\vec u=-\|\nabla f(P)\|=-4\sqrt{5}\approx -8{,}94$ . Cette direction ne vise PAS le minimum. La droite de descente est $(2-s\,;1-2s)$ : elle coupe l'axe des ordonnées en $s=2$ , au point $(0\,;-3)$ , et ne passe jamais par l'origine, puisque $2-s=0$ et $1-2s=0$ demandent deux valeurs de $s$ différentes. La direction vers le minimum serait $(-2\,;-1)$ . Sur la figure, $-\nabla f(P)$ est perpendiculaire à la courbe de niveau $f=8$ en $P$ (chapitre du gradient), et comme l'ellipse est aplatie, cette perpendiculaire plonge vers l'axe des abscisses au lieu de viser le centre. C'est tout le fil du chapitre : $-\nabla f$ est la meilleure direction LOCALE, pas la bonne direction GLOBALE, et c'est pourquoi la méthode a besoin de plusieurs pas.

c) $\vec x_{1}=(2\,;1)-\frac{1}{10}(4\,;8)=\left(\frac{8}{5}\,;\frac{1}{5}\right)$ , et $f(\vec x_{1})=\frac{64}{25}+4\times\frac{1}{25}=\frac{68}{25}=2{,}72$ . La valeur passe de $8$ à $2{,}72$ : le pas a fait descendre, et bien. Remarquez que $\vec x_{1}$ est déjà proche de l'axe des abscisses : la coordonnée $y$ , la plus pénalisée, a été corrigée en premier.

d) $\vec x_{1}=(2\,;1)-\frac{1}{2}(4\,;8)=(0\,;-3)$ et $f(\vec x_{1})=36$ : on a REMONTÉ de $8$ à $36$ , en partant pourtant dans la direction de plus forte descente. La dérivée directionnelle négative ne garantit la descente que pour un pas assez petit, parce qu'elle décrit $f$ AU POINT $P$ . Pour savoir jusqu'où on peut aller, on étudie la fonction d'une variable $\varphi(t)=f(2-4t\,;1-8t)=(2-4t)^{2}+4(1-8t)^{2}=272t^{2}-80t+8$ . Alors $\varphi(t)<8\iff 272t^{2}-80t<0\iff 8t(34t-10)<0\iff 0<t<\frac{5}{17}$ , avec $\frac{5}{17}\approx 0{,}294$ . Le pas $\frac{1}{10}$ est dans cet intervalle, le pas $\frac{1}{2}$ en sort. $\varphi$ est une parabole tournée vers le haut, de sommet $t=\frac{5}{34}$ , exactement au milieu de l'intervalle : un pas DEUX fois trop grand ramène au niveau de départ, un pas plus grand encore fait monter. Cette fonction $\varphi$ est l'outil central du chapitre : la recherche linéaire exacte consiste à prendre son minimum.

Coche ici les exercices faits ou à revoir : un compte gratuit, sans mot de passe, retient tes coches et tes réponses justes d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander l'exercice qui te manque. Crée ton espace, un courriel suffit.

Exercice 2 : Une itération avec recherche linéaire exacte

Soit $f(x,y)=x^{2}-2xy+2y^{2}-2x-2y$ et le point de départ $\vec x_{0}=(0\,;1)$ .

Une itération de la méthode du gradient avec RECHERCHE LINÉAIRE EXACTE choisit le pas $t_{0}$ qui minimise la fonction d'une variable $\varphi(t)=f\left(\vec x_{0}-t\,\nabla f(\vec x_{0})\right)$ pour $t\geq 0$ , puis pose $\vec x_{1}=\vec x_{0}-t_{0}\,\nabla f(\vec x_{0})$ .

a) Calculez $\nabla f(x,y)$ , puis $\nabla f(\vec x_{0})$ et $f(\vec x_{0})$ .
b) Écrivez $\varphi(t)$ sous forme développée et déterminez le pas optimal $t_{0}$ . Justifiez qu'il s'agit bien d'un minimum.
c) Donnez $\vec x_{1}$ et $f(\vec x_{1})$ , puis calculez le produit scalaire $\nabla f(\vec x_{0})\cdot\nabla f(\vec x_{1})$ .
d) Un élève écrit $\vec x_{0}+t\,\nabla f(\vec x_{0})$ au lieu de $\vec x_{0}-t\,\nabla f(\vec x_{0})$ , minimise sa fonction de $t$ et trouve $t=-\frac{1}{4}$ . Que s'est-il passé, et à quel point arrive-t-il s'il garde ce $t$ ?
e) Trouvez le minimum exact $\vec x^{*}$ de $f$ en résolvant $\nabla f=\vec 0$ , et la valeur $f^{*}$ . Par quel facteur l'écart $f-f^{*}$ a-t-il été multiplié en une itération ?

Tape tes réponses, la page te dit juste ou faux 0/13

a)

\frac{\partial f}{\partial x}(\vec x_{0})

\frac{\partial f}{\partial y}(\vec x_{0})

f(\vec x_{0})

b)

t_{0}

c)

x

de

\vec x_{1}

y

de

\vec x_{1}

f(\vec x_{1})

Produit scalaire

d)

L'élève a suivi

e)

x^{*}

y^{*}

f^{*}

Facteur de l'écart

Voir la correction

Réponses

a) $\nabla f=(2x-2y-2\,;-2x+4y-2)$ , $\nabla f(\vec x_{0})=(-4\,;2)$ , $f(\vec x_{0})=0$
b) $\varphi(t)=40t^{2}-20t$ , $t_{0}=\frac{1}{4}$ ( $\varphi''=80>0$ )
c) $\vec x_{1}=\left(1\,;\frac{1}{2}\right)$ , $f(\vec x_{1})=-\frac{5}{2}$ , $\nabla f(\vec x_{1})=(-1\,;-2)$ , produit scalaire $0$
d) Il a suivi $+\nabla f$ , la montée ; $t=-\frac{1}{4}$ redonne le même point $\left(1\,;\frac{1}{2}\right)$
e) $\vec x^{*}=(3\,;2)$ , $f^{*}=-5$ ; l'écart passe de $5$ à $\frac{5}{2}$ , facteur $\frac{1}{2}$

a) $\frac{\partial f}{\partial x}=2x-2y-2$ et $\frac{\partial f}{\partial y}=-2x+4y-2$ . En $\vec x_{0}=(0\,;1)$ : $\nabla f(\vec x_{0})=(0-2-2\,;0+4-2)=(-4\,;2)$ , et $f(\vec x_{0})=2-2=0$ . La direction de descente est donc $-\nabla f(\vec x_{0})=(4\,;-2)$ : on part vers la droite et vers le bas.

b) Le point courant de la droite de recherche est $\vec x_{0}-t\,\nabla f(\vec x_{0})=(4t\,;1-2t)$ . On substitue : $\varphi(t)=16t^{2}-2(4t)(1-2t)+2(1-2t)^{2}-8t-2(1-2t)$ , soit $16t^{2}-8t+16t^{2}+2-8t+8t^{2}-8t-2+4t=40t^{2}-20t$ . Alors $\varphi'(t)=80t-20$ s'annule en $t_{0}=\frac{1}{4}$ , et $\varphi''(t)=80>0$ : c'est le minimum de la parabole, donc le minimum de $\varphi$ sur $[0\,;+\infty[$ . Contrôle utile : $\varphi(0)=0=f(\vec x_{0})$ , et $\varphi'(0)=-20=-\|\nabla f(\vec x_{0})\|^{2}$ , négatif comme il se doit en direction de descente. Le piège de ce calcul est purement algébrique : un signe perdu dans $-2(4t)(1-2t)$ déplace le sommet, et toute la suite est fausse. Développez lentement.

c) $\vec x_{1}=(0\,;1)-\frac{1}{4}(-4\,;2)=\left(1\,;\frac{1}{2}\right)$ et $f(\vec x_{1})=\varphi\left(\frac{1}{4}\right)=\frac{40}{16}-5=-\frac{5}{2}$ ; on recalcule directement : $1-1+\frac{1}{2}-2-1=-\frac{5}{2}$ . Puis $\nabla f(\vec x_{1})=\left(2-1-2\,;-2+2-2\right)=(-1\,;-2)$ et $\nabla f(\vec x_{0})\cdot\nabla f(\vec x_{1})=(-4)(-1)+(2)(-2)=0$ . Les deux gradients sont ORTHOGONAUX : ce n'est pas une coïncidence, c'est la propriété de la recherche exacte, démontrée à l'exercice 5. Au point où l'on s'arrête, la droite de recherche est tangente à une courbe de niveau, donc le nouveau gradient lui est perpendiculaire, et le pas suivant tourne d'un angle droit.

d) Avec $\vec x_{0}+t\,\nabla f(\vec x_{0})=(-4t\,;1+2t)$ , la fonction devient $40t^{2}+20t$ , de minimum en $t=-\frac{1}{4}$ . Un pas NÉGATIF est le signal d'alarme : l'élève a pris la direction de plus forte MONTÉE, et sa fonction de $t$ ne fait que monter pour $t>0$ . S'il garde $t=-\frac{1}{4}$ , il arrive en $(-4t\,;1+2t)=\left(1\,;\frac{1}{2}\right)$ , le même point : deux erreurs de signe se sont compensées. Sur une copie, ce n'est pas un calcul juste, c'est une méthode fausse ; le correcteur retire les points de la méthode. Retenez le contrôle : $\varphi'(0)$ doit valoir $-\|\nabla f\|^{2}<0$ , et le pas optimal doit être positif.

e) $\nabla f=\vec 0$ donne $2x-2y=2$ et $-2x+4y=2$ ; en additionnant, $2y=4$ , donc $y=2$ et $x=3$ . La hessienne a $f_{xx}=2>0$ et $D=2\times 4-(-2)^{2}=4>0$ : c'est un minimum, et même le minimum global d'une quadratique à hessienne définie positive. $f^{*}=f(3\,;2)=9-12+8-6-4=-5$ . L'écart à l'optimum valait $f(\vec x_{0})-f^{*}=5$ et vaut $-\frac{5}{2}+5=\frac{5}{2}$ après une itération : il a été divisé par $2$ . Une seconde itération, à partir de $\nabla f(\vec x_{1})=(-1\,;-2)$ , donnerait le pas $\frac{1}{2}$ , le point $\vec x_{2}=\left(\frac{3}{2}\,;\frac{3}{2}\right)$ et $f(\vec x_{2})=-\frac{15}{4}$ : l'écart vaut $\frac{5}{4}$ , encore divisé par $2$ . La méthode s'approche du minimum sans jamais l'atteindre exactement, et c'est la comparaison avec $f^{*}$ qui mesure sa vitesse.

Exercice 3 : Le pas optimal par la formule, et le facteur 2 de la hessienne

Pour une fonction quadratique dont la hessienne est $H$ , la recherche linéaire exacte a une formule : en notant $\vec g=\nabla f(\vec x_{k})$ , le pas optimal est $t_{k}=\dfrac{\vec g\cdot\vec g}{\vec g\cdot H\vec g}$ (on l'admet ici ; l'exercice 5 la démontre).

On l'applique à $f(x,y)=x^{2}+2xy+3y^{2}$ , dont le minimum est $(0\,;0)$ , à partir de $\vec x_{0}=(3\,;0)$ .

a) Écrivez la hessienne $H$ de $f$ sous forme de tableau $2\times 2$ .
b) Calculez $\nabla f(\vec x_{0})$ , le pas $t_{0}$ par la formule, le point $\vec x_{1}$ et $f(\vec x_{1})$ .
c) Un élève écrit $f(\vec x)=\vec x\cdot A\vec x$ avec $A=\begin{pmatrix}1&1\\1&3\end{pmatrix}$ , et met $A$ à la place de $H$ dans la formule. Quel pas trouve-t-il, et que vaut $f$ au point où il arrive ? Expliquez le résultat avec la parabole $\varphi$ .
d) Faites la deuxième itération : $\nabla f(\vec x_{1})$ , $t_{1}$ , $\vec x_{2}$ et $f(\vec x_{2})$ .
e) Comparez $\vec x_{2}$ à $\vec x_{0}$ et déduisez-en $f(\vec x_{k})$ pour tout $k$ . Après combien d'itérations a-t-on, pour la première fois, $f(\vec x_{k})<10^{-4}$ ?

Voir la correction

Réponses

a) $H=\begin{pmatrix}2&2\\2&6\end{pmatrix}$
b) $\nabla f(\vec x_{0})=(6\,;6)$ , $t_{0}=\frac{72}{432}=\frac{1}{6}$ , $\vec x_{1}=(2\,;-1)$ , $f(\vec x_{1})=3$
c) $t=\frac{1}{3}$ , double du bon ; il arrive en $(1\,;-2)$ où $f=9=f(\vec x_{0})$ : aucun progrès
d) $\nabla f(\vec x_{1})=(2\,;-2)$ , $t_{1}=\frac{1}{2}$ , $\vec x_{2}=(1\,;0)$ , $f(\vec x_{2})=1$
e) $\vec x_{2}=\frac{1}{3}\vec x_{0}$ , $f(\vec x_{k})=\frac{9}{3^{k}}$ ; $f(\vec x_{k})<10^{-4}$ dès $k=11$

a) $f_{xx}=2$ , $f_{xy}=f_{yx}=2$ et $f_{yy}=6$ , donc $H=\begin{pmatrix}2&2\\2&6\end{pmatrix}$ . Les coefficients de $f$ sont $1$ , $2$ et $3$ ; ceux de $H$ sont leurs dérivées secondes, ce qui DOUBLE les termes carrés ( $x^{2}$ donne $2$ , $3y^{2}$ donne $6$ ) et garde le terme croisé ( $2xy$ donne $2$ ). C'est exactement l'endroit où la question c) va piéger.

b) $\nabla f=(2x+2y\,;2x+6y)$ , donc $\nabla f(\vec x_{0})=(6\,;6)$ . Puis $\vec g\cdot\vec g=72$ , $H\vec g=(12+12\,;12+36)=(24\,;48)$ et $\vec g\cdot H\vec g=144+288=432$ , d'où $t_{0}=\frac{72}{432}=\frac{1}{6}$ . Alors $\vec x_{1}=(3\,;0)-\frac{1}{6}(6\,;6)=(2\,;-1)$ et $f(\vec x_{1})=4-4+3=3$ . Contrôle par $\varphi$ : $\varphi(t)=f(3-6t\,;-6t)=216t^{2}-72t+9$ , de sommet $t=\frac{72}{432}=\frac{1}{6}$ , le même. La formule évite de développer $\varphi$ , mais elle exige la vraie hessienne.

c) Avec $A$ : $A\vec g=(12\,;24)$ et $\vec g\cdot A\vec g=216$ , d'où $t=\frac{72}{216}=\frac{1}{3}$ , exactement le double du bon pas, puisque $H=2A$ . Le point obtenu est $(3\,;0)-\frac{1}{3}(6\,;6)=(1\,;-2)$ , et $f(1\,;-2)=1-4+12=9$ : la valeur de DÉPART. Aucun progrès, ce qui s'explique sans calcul : $\varphi$ est une parabole symétrique autour de son sommet $t_{0}$ , donc $\varphi(2t_{0})=\varphi(0)$ . Le pas doublé saute par-dessus la vallée et retombe à la même hauteur de l'autre côté. Avec un pas triplé, $f$ aurait augmenté. Retenez le geste : la formule s'écrit avec la hessienne, celle des DÉRIVÉES SECONDES, et $f(\vec x)=\frac{1}{2}\vec x\cdot H\vec x$ , avec le facteur $\frac{1}{2}$ .

d) $\nabla f(\vec x_{1})=(4-2\,;4-6)=(2\,;-2)$ , orthogonal à $(6\,;6)$ comme il se doit après une recherche exacte. $\vec g\cdot\vec g=8$ , $H\vec g=(4-4\,;4-12)=(0\,;-8)$ , $\vec g\cdot H\vec g=16$ , d'où $t_{1}=\frac{8}{16}=\frac{1}{2}$ . Alors $\vec x_{2}=(2\,;-1)-\frac{1}{2}(2\,;-2)=(1\,;0)$ et $f(\vec x_{2})=1$ . Le pas a changé d'une itération à l'autre ( $\frac{1}{6}$ puis $\frac{1}{2}$ ) : la recherche exacte s'adapte à la courbure de $f$ dans chaque direction, c'est son avantage sur un pas fixe.

e) $\vec x_{2}=(1\,;0)=\frac{1}{3}\vec x_{0}$ . Or $f$ n'a pas de terme du premier degré : si l'on multiplie le point par $\lambda$ , le gradient est multiplié par $\lambda$ et la formule du pas donne le MÊME pas. Les itérations à partir de $\vec x_{2}$ sont donc celles à partir de $\vec x_{0}$ , divisées par $3$ : $\vec x_{2k}=\frac{\vec x_{0}}{3^{k}}$ et $\vec x_{2k+1}=\frac{\vec x_{1}}{3^{k}}$ . Comme $f(\lambda\vec x)=\lambda^{2}f(\vec x)$ , on obtient $f(\vec x_{2k})=\frac{9}{9^{k}}$ et $f(\vec x_{2k+1})=\frac{3}{9^{k}}$ , soit dans les deux cas $f(\vec x_{k})=\frac{9}{3^{k}}$ : chaque itération divise $f$ par $3$ . Enfin $\frac{9}{3^{k}}<10^{-4}\iff 3^{k}>90\,000$ ; or $3^{10}=59\,049$ et $3^{11}=177\,147$ , donc $k=11$ . La méthode converge, mais à vitesse constante : un facteur $3$ par pas, onze pas pour gagner quatre décimales.

Exercice 4 : Le pas fixe : quand la méthode diverge

Pour éviter une recherche linéaire à chaque itération, on peut garder un PAS FIXE $t>0$ : $\vec x_{k+1}=\vec x_{k}-t\,\nabla f(\vec x_{k})$ pour tout $k$ . On étudie ce choix sur $f(x,y)=x^{2}+5y^{2}$ , de minimum $(0\,;0)$ , en notant $\vec x_{k}=(x_{k}\,;y_{k})$ .

a) Montrez que $x_{k+1}=(1-2t)\,x_{k}$ et $y_{k+1}=(1-10t)\,y_{k}$ . Donnez les deux facteurs pour $t=\frac{1}{4}$ .
b) Avec $t=\frac{1}{4}$ et $\vec x_{0}=(5\,;1)$ , calculez $f(\vec x_{0})$ , $f(\vec x_{1})$ et $f(\vec x_{2})$ . Le fait que $f$ ait diminué au premier pas prouve-t-il que la suite converge ?
c) Pour quelles valeurs de $t$ la suite converge-t-elle vers $(0\,;0)$ quel que soit le point de départ ?
d) Le pas fixe le plus rapide est celui qui rend le plus petit possible le plus grand des deux facteurs $|1-2t|$ et $|1-10t|$ . Trouvez-le et donnez ce facteur.
e) Avec ce pas, montrez que $\|\vec x_{k}\|$ est multiplié par ce facteur à chaque itération, et trouvez le plus petit $k$ pour lequel la distance au minimum est divisée par au moins $100$ .

Voir la correction

Réponses

a) $\nabla f=(2x\,;10y)$ ; pour $t=\frac{1}{4}$ : facteurs $\frac{1}{2}$ et $-\frac{3}{2}$
b) $f(\vec x_{0})=30$ , $f(\vec x_{1})=\frac{35}{2}$ , $f(\vec x_{2})=\frac{215}{8}$ ; non, $y_{k}=\left(-\frac{3}{2}\right)^{k}$ diverge
c) $|1-2t|<1$ et $|1-10t|<1$ , soit $0<t<\frac{1}{5}$
d) $1-2t=10t-1$ , $t=\frac{1}{6}$ , facteur $\frac{2}{3}$
e) $\|\vec x_{k}\|=\left(\frac{2}{3}\right)^{k}\|\vec x_{0}\|$ ; $\left(\frac{3}{2}\right)^{12}\approx 129{,}7>100$ , donc $k=12$

a) $\nabla f(x,y)=(2x\,;10y)$ , donc $x_{k+1}=x_{k}-2t\,x_{k}=(1-2t)\,x_{k}$ et $y_{k+1}=y_{k}-10t\,y_{k}=(1-10t)\,y_{k}$ . Les deux coordonnées évoluent SÉPARÉMENT, chacune multipliée à chaque pas par un facteur constant, d'où $x_{k}=(1-2t)^{k}x_{0}$ et $y_{k}=(1-10t)^{k}y_{0}$ . Pour $t=\frac{1}{4}$ : $1-\frac{1}{2}=\frac{1}{2}$ et $1-\frac{10}{4}=-\frac{3}{2}$ . Le facteur en $y$ est plus grand que $1$ en valeur absolue : c'est déjà la réponse à la question suivante.

b) $f(\vec x_{0})=25+5=30$ . $\vec x_{1}=\left(\frac{5}{2}\,;-\frac{3}{2}\right)$ et $f(\vec x_{1})=\frac{25}{4}+\frac{45}{4}=\frac{35}{2}=17{,}5$ . $\vec x_{2}=\left(\frac{5}{4}\,;\frac{9}{4}\right)$ et $f(\vec x_{2})=\frac{25}{16}+\frac{405}{16}=\frac{215}{8}=26{,}875$ . La valeur a baissé puis REMONTÉ. Le premier pas a trompé : il a beaucoup gagné sur $x$ , qui pesait $25$ dans $f(\vec x_{0})$ , et perdu sur $y$ , qui ne pesait que $5$ . Mais $y_{k}=\left(-\frac{3}{2}\right)^{k}$ change de signe et grandit à chaque pas : les itérés sautent d'un bord de la vallée à l'autre, toujours plus haut, et $f(\vec x_{k})\to+\infty$ . Une baisse au premier pas ne prouve RIEN ; c'est le facteur de chaque coordonnée qui décide.

c) $x_{k}\to 0$ pour tout $x_{0}$ si et seulement si $|1-2t|<1$ , soit $0<t<1$ ; $y_{k}\to 0$ pour tout $y_{0}$ si et seulement si $|1-10t|<1$ , soit $0<t<\frac{1}{5}$ . Il faut les DEUX, donc $0<t<\frac{1}{5}$ . La contrainte vient de la direction la plus courbée : la dérivée seconde $f_{yy}=10$ impose $t<\frac{2}{10}$ . Plus la vallée est étroite dans une direction, plus le pas fixe doit être petit pour TOUTES les directions, y compris celles où l'on avancerait vite.

d) Pour $0<t<\frac{1}{5}$ , $|1-2t|=1-2t$ décroît et $|1-10t|$ décroît jusqu'en $\frac{1}{10}$ puis croît. Le plus grand des deux est minimal quand ils sont égaux, avec $1-10t<0$ : $1-2t=10t-1$ , d'où $t=\frac{1}{6}$ , et les deux facteurs valent $\frac{2}{3}$ et $-\frac{2}{3}$ . À gauche de $\frac{1}{6}$ , la coordonnée $x$ est trop lente ; à droite, la coordonnée $y$ oscille trop fort. Même le meilleur pas fixe ne fait gagner qu'un facteur $\frac{2}{3}$ par pas.

e) Avec $t=\frac{1}{6}$ , $\vec x_{k+1}=\left(\frac{2}{3}x_{k}\,;-\frac{2}{3}y_{k}\right)$ , donc $\|\vec x_{k+1}\|=\frac{2}{3}\|\vec x_{k}\|$ et $\|\vec x_{k}\|=\left(\frac{2}{3}\right)^{k}\|\vec x_{0}\|$ . On cherche $\left(\frac{3}{2}\right)^{k}\geq 100$ . À la main : $\left(\frac{3}{2}\right)^{2}=2{,}25$ , $\left(\frac{3}{2}\right)^{4}\approx 5{,}06$ , $\left(\frac{3}{2}\right)^{8}\approx 25{,}6$ , $\left(\frac{3}{2}\right)^{12}\approx 25{,}6\times 5{,}06\approx 129{,}7$ et $\left(\frac{3}{2}\right)^{11}\approx 86{,}5$ . Donc $k=12$ . Douze itérations pour deux décimales, sur une fonction de deux variables : c'est le prix du pas fixe, et la raison pour laquelle on règle le pas sur la direction la plus courbée.

Exercice 5 : Démontrer : gradients successifs orthogonaux et formule du pas

Soit $f$ une fonction de deux variables dont les dérivées partielles sont continues, $\vec x_{k}$ un point où $\vec g_{k}=\nabla f(\vec x_{k})\neq\vec 0$ , et $\varphi(t)=f\left(\vec x_{k}-t\,\vec g_{k}\right)$ . La recherche linéaire exacte prend pour $t_{k}>0$ le minimum de $\varphi$ , et $\vec x_{k+1}=\vec x_{k}-t_{k}\vec g_{k}$ .

a) Par la dérivation en chaîne, montrez que $\varphi'(t)=-\nabla f\left(\vec x_{k}-t\,\vec g_{k}\right)\cdot\vec g_{k}$ . Que vaut $\varphi'(0)$ ? Application : $\vec g_{k}=(1\,;-2)$ .
b) Déduisez-en que $\nabla f(\vec x_{k+1})\cdot\nabla f(\vec x_{k})=0$ . Interprétez avec les courbes de niveau : où le pas s'arrête-t-il ?
c) On suppose $f(\vec x)=\frac{1}{2}\vec x\cdot H\vec x-\vec b\cdot\vec x+c$ , de gradient $H\vec x-\vec b$ . Montrez que $\varphi(t)=f(\vec x_{k})-t\,\vec g_{k}\cdot\vec g_{k}+\frac{t^{2}}{2}\,\vec g_{k}\cdot H\vec g_{k}$ , puis donnez $t_{k}$ et la baisse $f(\vec x_{k})-f(\vec x_{k+1})$ . Application : $H=\begin{pmatrix}4&1\\1&2\end{pmatrix}$ et $\vec g_{k}=(1\,;-2)$ .
d) Pourquoi a-t-on $\vec g\cdot H\vec g>0$ pour tout $\vec g\neq\vec 0$ avec cette matrice $H$ ? Que se passerait-il pour $\varphi$ sinon ?
e) Dans le plan, comparez la direction de $\vec g_{k+2}$ à celle de $\vec g_{k}$ . Qu'en déduit-on pour le trajet des itérés ?

Tape tes réponses, la page te dit juste ou faux 0/7

a)

\varphi'(0)

b)

Le pas s'arrête

c)

\vec g\cdot H\vec g

t_{k}

Baisse de

f

d)

\det H

e)

\vec g_{k+2}

et

\vec g_{k}

sont

Voir la correction

Réponses

a) $\varphi'(0)=-\|\vec g_{k}\|^{2}<0$ ; ici $\varphi'(0)=-5$
b) $\varphi'(t_{k})=0$ donne $\vec g_{k+1}\cdot\vec g_{k}=0$ ; le pas s'arrête où la droite de recherche est tangente à une courbe de niveau
c) $t_{k}=\frac{\vec g\cdot\vec g}{\vec g\cdot H\vec g}$ , baisse $\frac{(\vec g\cdot\vec g)^{2}}{2\,\vec g\cdot H\vec g}$ ; ici $\vec g\cdot H\vec g=8$ , $t_{k}=\frac{5}{8}$ , baisse $\frac{25}{16}$
d) $\vec g\cdot H\vec g=4\left(g_{1}+\frac{g_{2}}{4}\right)^{2}+\frac{7}{4}g_{2}^{2}>0$ ( $\det H=7>0$ , $4>0$ ) ; sinon $\varphi$ n'aurait pas de minimum
e) $\vec g_{k+2}$ est parallèle à $\vec g_{k}$ : le trajet zigzague entre deux directions perpendiculaires

a) Posons $\vec r(t)=\vec x_{k}-t\,\vec g_{k}$ , dont la dérivée est le vecteur constant $\vec r\,'(t)=-\vec g_{k}$ . La dérivation en chaîne pour $\varphi(t)=f(\vec r(t))$ donne $\varphi'(t)=\nabla f(\vec r(t))\cdot\vec r\,'(t)=-\nabla f\left(\vec x_{k}-t\,\vec g_{k}\right)\cdot\vec g_{k}$ . En $t=0$ : $\varphi'(0)=-\vec g_{k}\cdot\vec g_{k}=-\|\vec g_{k}\|^{2}$ , strictement négatif puisque $\vec g_{k}\neq\vec 0$ . Pour $\vec g_{k}=(1\,;-2)$ : $\varphi'(0)=-5$ . C'est la preuve que $-\vec g_{k}$ est une direction de DESCENTE : $\varphi$ décroît au départ, donc il existe des pas $t>0$ qui font baisser $f$ . Rien ne dit en revanche jusqu'où (exercice 1).

b) Le minimum $t_{k}>0$ de $\varphi$ est un point intérieur où $\varphi$ est dérivable, donc $\varphi'(t_{k})=0$ , c'est-à-dire $-\nabla f(\vec x_{k+1})\cdot\vec g_{k}=0$ : $\nabla f(\vec x_{k+1})\cdot\nabla f(\vec x_{k})=0$ . Géométriquement, en $\vec x_{k+1}$ le nouveau gradient est perpendiculaire à la droite de recherche ; or il est aussi perpendiculaire à la courbe de niveau qui passe par $\vec x_{k+1}$ . La droite de recherche est donc TANGENTE à cette courbe de niveau : on avance tant qu'on traverse des niveaux de plus en plus bas, et l'on s'arrête au point où la droite ne fait plus que frôler un niveau. C'est ce qui produit le virage à angle droit de chaque itération.

c) Avec $\vec g=\vec g_{k}$ et $H$ symétrique, développons : $f(\vec x_{k}-t\vec g)=\frac{1}{2}(\vec x_{k}-t\vec g)\cdot H(\vec x_{k}-t\vec g)-\vec b\cdot(\vec x_{k}-t\vec g)+c$ $=f(\vec x_{k})-t\,\vec g\cdot(H\vec x_{k}-\vec b)+\frac{t^{2}}{2}\,\vec g\cdot H\vec g$ , et $H\vec x_{k}-\vec b=\vec g$ . Donc $\varphi(t)=f(\vec x_{k})-t\,\vec g\cdot\vec g+\frac{t^{2}}{2}\,\vec g\cdot H\vec g$ , parabole de sommet $t_{k}=\dfrac{\vec g\cdot\vec g}{\vec g\cdot H\vec g}$ , et la baisse vaut $\varphi(0)-\varphi(t_{k})=\dfrac{(\vec g\cdot\vec g)^{2}}{2\,\vec g\cdot H\vec g}$ . Application : $H\vec g=(4-2\,;1-4)=(2\,;-3)$ , $\vec g\cdot H\vec g=2+6=8$ , $\vec g\cdot\vec g=5$ , donc $t_{k}=\frac{5}{8}$ et la baisse vaut $\frac{25}{16}$ . Le $\frac{1}{2}$ devant $\vec x\cdot H\vec x$ est indispensable : c'est lui qui fait que $H$ est la hessienne.

d) $\vec g\cdot H\vec g=4g_{1}^{2}+2g_{1}g_{2}+2g_{2}^{2}=4\left(g_{1}+\frac{g_{2}}{4}\right)^{2}+\frac{7}{4}g_{2}^{2}$ , somme de deux carrés à coefficients positifs, nulle seulement si $g_{2}=0$ puis $g_{1}=0$ . C'est le critère du test des dérivées secondes : $f_{xx}=4>0$ et $\det H=8-1=7>0$ . Le coefficient de $t^{2}$ dans $\varphi$ est alors positif, la parabole est tournée vers le haut et son sommet est un minimum. Si $\vec g\cdot H\vec g$ était négatif ou nul (point de selle, maximum), $\varphi$ décroîtrait sans fin dans certaines directions : la formule donnerait un « pas » négatif ou infini, et la recherche exacte n'aurait pas de sens.

e) Par b), $\vec g_{k+1}\perp\vec g_{k}$ et $\vec g_{k+2}\perp\vec g_{k+1}$ . Dans le plan, deux vecteurs perpendiculaires au même vecteur non nul sont PARALLÈLES : $\vec g_{k+2}$ est parallèle à $\vec g_{k}$ . Les pas successifs n'utilisent donc que deux directions perpendiculaires, en alternance : le trajet est un escalier, ou un zigzag, et jamais une ligne droite vers le minimum. C'est ce qu'on lit sur les cartes des exercices 6 et 10. En dimension $3$ ou plus, seul l'angle droit entre deux pas CONSÉCUTIFS subsiste.

Partie B : problèmes et raisonnement (/50)

Exercice 6 : Le zigzag lu sur une carte de contour

La figure montre les courbes de niveau $f=12$ , $f=3$ et $f=\frac{3}{4}$ de $f(x,y)=x^{2}+3y^{2}$ , et les quatre premiers itérés $\vec x_{0}=(3\,;1)$ , $\vec x_{1}$ , $\vec x_{2}$ , $\vec x_{3}$ de la méthode du gradient avec recherche linéaire exacte. Le repère est orthonormé : les angles se lisent tels qu'ils sont.

a) Lisez $\vec x_{1}$ sur la figure, puis retrouvez-le par le calcul : $\nabla f(\vec x_{0})$ , le pas $t_{0}$ et $\vec x_{1}$ .
b) Calculez $\vec x_{2}$ , puis vérifiez par un produit scalaire l'angle droit que la figure montre en $\vec x_{1}$ .
c) Montrez par récurrence que $\vec x_{k}=\left(\frac{1}{2}\right)^{k}\left(3\,;(-1)^{k}\right)$ , et donnez $f(\vec x_{k})$ . Calculez $f(\vec x_{4})$ .
d) On arrête l'algorithme dès que $\|\nabla f(\vec x_{k})\|<10^{-3}$ . À quelle itération s'arrête-t-il ? On utilisera $\sqrt{2}\approx 1{,}414$ .
e) Plus généralement, pour $f(x,y)=x^{2}+\kappa y^{2}$ avec $\kappa\geq 1$ et $\vec x_{0}=(\kappa\,;1)$ , montrez que $\vec x_{1}=\rho\,(\kappa\,;-1)$ avec $\rho=\frac{\kappa-1}{\kappa+1}$ . Que se passe-t-il pour $\kappa=1$ ? Donnez $\rho$ et le facteur de baisse de $f$ par itération pour $\kappa=9$ .

Voir la correction

Réponses

a) $\nabla f(\vec x_{0})=(6\,;6)$ , $t_{0}=\frac{1}{4}$ , $\vec x_{1}=\left(\frac{3}{2}\,;-\frac{1}{2}\right)$
b) $\vec x_{2}=\left(\frac{3}{4}\,;\frac{1}{4}\right)$ ; $(\vec x_{1}-\vec x_{0})\cdot(\vec x_{2}-\vec x_{1})=0$
c) $f(\vec x_{k})=\frac{12}{4^{k}}$ ; $f(\vec x_{4})=\frac{3}{64}$
d) $\|\nabla f(\vec x_{k})\|=\frac{6\sqrt{2}}{2^{k}}$ ; $2^{k}>8485$ dès $k=14$
e) $\kappa=1$ : minimum atteint en un pas ; $\kappa=9$ : $\rho=\frac{4}{5}$ , $f$ multipliée par $\frac{16}{25}$

a) La figure place $\vec x_{1}$ vers $(1{,}5\,;-0{,}5)$ . Calcul : $\nabla f=(2x\,;6y)$ , donc $\nabla f(\vec x_{0})=(6\,;6)$ . Avec la hessienne $H=\begin{pmatrix}2&0\\0&6\end{pmatrix}$ , $\vec g\cdot\vec g=72$ et $\vec g\cdot H\vec g=72+216=288$ , d'où $t_{0}=\frac{72}{288}=\frac{1}{4}$ et $\vec x_{1}=(3\,;1)-\frac{1}{4}(6\,;6)=\left(\frac{3}{2}\,;-\frac{1}{2}\right)$ . On peut aussi minimiser $\varphi(t)=(3-6t)^{2}+3(1-6t)^{2}$ , dont la dérivée $-12(3-6t)-36(1-6t)$ s'annule en $t=\frac{1}{4}$ . Le point est sur la courbe $f=3$ : la valeur est passée de $12$ à $3$ , et le segment $[\vec x_{0}\vec x_{1}]$ touche cette ellipse sans la traverser.

b) $\nabla f(\vec x_{1})=(3\,;-3)$ ; $\vec g\cdot\vec g=18$ , $\vec g\cdot H\vec g=18+54=72$ , $t_{1}=\frac{1}{4}$ et $\vec x_{2}=\left(\frac{3}{2}-\frac{3}{4}\,;-\frac{1}{2}+\frac{3}{4}\right)=\left(\frac{3}{4}\,;\frac{1}{4}\right)$ . Les deux déplacements sont $\vec x_{1}-\vec x_{0}=\left(-\frac{3}{2}\,;-\frac{3}{2}\right)$ et $\vec x_{2}-\vec x_{1}=\left(-\frac{3}{4}\,;\frac{3}{4}\right)$ , de produit scalaire $\frac{9}{8}-\frac{9}{8}=0$ . L'angle droit vu sur la figure est la propriété démontrée à l'exercice 5 : chaque déplacement est parallèle au gradient, et deux gradients successifs sont orthogonaux. Attention, cet angle ne se VOIT droit que dans un repère orthonormé ; avec des unités différentes sur les axes, le zigzag paraîtrait oblique.

c) Pour $k=0$ , $\left(3\,;1\right)$ convient. Si $\vec x_{k}=s\,(3\,;\pm 1)$ avec $s=\left(\frac{1}{2}\right)^{k}$ , le gradient vaut $s\,(6\,;\pm 6)$ ; les deux sommes de la formule sont multipliées par $s^{2}$ , donc le pas reste $\frac{1}{4}$ et $\vec x_{k+1}=s\left(3-\frac{6}{4}\,;\pm\left(1-\frac{6}{4}\right)\right)=\frac{s}{2}\,(3\,;\mp 1)$ . D'où $\vec x_{k}=\left(\frac{1}{2}\right)^{k}\left(3\,;(-1)^{k}\right)$ pour tout $k$ . Alors $f(\vec x_{k})=\frac{1}{4^{k}}(9+3)=\frac{12}{4^{k}}$ : chaque itération divise $f$ par $4$ , et $f(\vec x_{4})=\frac{12}{256}=\frac{3}{64}$ .

d) $\nabla f(\vec x_{k})=\left(\frac{1}{2}\right)^{k}\left(6\,;\pm 6\right)$ , de norme $\frac{6\sqrt{2}}{2^{k}}$ . La condition $\frac{6\sqrt{2}}{2^{k}}<10^{-3}$ équivaut à $2^{k}>6000\sqrt{2}\approx 8485$ . Or $2^{13}=8192<8485$ et $2^{14}=16\,384$ : l'algorithme s'arrête à $k=14$ . À ce moment, $f(\vec x_{14})=\frac{12}{4^{14}}\approx 4{,}5\times 10^{-8}$ et $\|\vec x_{14}\|=\frac{\sqrt{10}}{2^{14}}\approx 1{,}9\times 10^{-4}$ . Le critère porte sur le gradient parce que, dans un vrai problème, on ne connaît ni $\vec x^{*}$ ni $f^{*}$ : c'est la seule quantité qu'on peut calculer.

e) $\nabla f(\vec x_{0})=(2\kappa\,;2\kappa)$ et $\varphi(t)=(\kappa-2\kappa t)^{2}+\kappa(1-2\kappa t)^{2}$ . En posant $s=2\kappa t$ , $\varphi'=0$ donne $(\kappa-s)+\kappa(1-s)=0$ , soit $s=\frac{2\kappa}{\kappa+1}$ . Alors $\vec x_{1}=(\kappa-s\,;1-s)=\left(\frac{\kappa(\kappa-1)}{\kappa+1}\,;\frac{1-\kappa}{\kappa+1}\right)=\rho\,(\kappa\,;-1)$ . Le même raisonnement qu'en c) donne $\vec x_{k}=\rho^{k}\left(\kappa\,;(-1)^{k}\right)$ et $f(\vec x_{k})=\rho^{2k}f(\vec x_{0})$ . Pour $\kappa=1$ , les courbes de niveau sont des cercles, $\rho=0$ et $\vec x_{1}=(0\,;0)$ : le gradient vise le centre, un seul pas suffit. Pour $\kappa=3$ on retrouve $\rho=\frac{1}{2}$ . Pour $\kappa=9$ , $\rho=\frac{8}{10}=\frac{4}{5}$ et $f$ n'est multipliée que par $\frac{16}{25}$ à chaque pas ; pour $\kappa=99$ , par $\left(\frac{49}{50}\right)^{2}\approx 0{,}96$ . Plus la vallée est allongée, plus le zigzag est serré et lent : c'est la faiblesse connue de la méthode.

Exercice 7 : Une vallée courbe : la méthode hors des quadratiques

Soit $f(x,y)=2\left(x^{2}-y\right)^{2}+(1-x)^{2}$ . La figure montre les courbes de niveau $f=1$ , $f=\frac{3}{8}$ et $f=\frac{1}{4}$ , la parabole $y=x^{2}$ en pointillé, le point de départ $\vec x_{0}=(0\,;0)$ et le point $(1\,;1)$ . Les courbes de niveau sont des « bananes » qui suivent la parabole.

Ici $f$ n'est PAS quadratique : la formule du pas des exercices précédents ne s'applique plus, il faut minimiser $\varphi$ elle-même.

a) Montrez que $(1\,;1)$ est le minimum global de $f$ . Calculez $f(\vec x_{0})$ et $\nabla f(\vec x_{0})$ .
b) Première itération avec recherche exacte : écrivez $\varphi(t)$ , montrez que $\varphi'$ a une seule racine et que c'est $t_{0}=\frac{1}{4}$ . Donnez $\vec x_{1}$ et $f(\vec x_{1})$ .
c) Deuxième itération : $\nabla f(\vec x_{1})$ , le pas $t_{1}$ , $\vec x_{2}$ et $f(\vec x_{2})$ .
d) Pour la troisième itération, $\nabla f(\vec x_{2})=(-1\,;0)$ et $\varphi'(t)=4t(1+t)(1+2t)+2t-1$ . Calculez $\varphi'\left(\frac{1}{10}\right)$ et $\varphi'\left(\frac{1}{5}\right)$ en fractions, et concluez sur $t_{2}$ .
e) Où se trouve $\vec x_{2}$ par rapport à la parabole ? Calculez sa distance au minimum, au centième, et expliquez pourquoi la méthode progresse lentement dans cette vallée.

Voir la correction

Réponses

a) $f\geq 0$ et $f(1\,;1)=0$ ; $f(\vec x_{0})=1$ , $\nabla f(\vec x_{0})=(-2\,;0)$
b) $\varphi(t)=32t^{4}+(1-2t)^{2}$ , $\varphi'(t)=128t^{3}+8t-4$ croissante, racine unique $\frac{1}{4}$ ; $\vec x_{1}=\left(\frac{1}{2}\,;0\right)$ , $f(\vec x_{1})=\frac{3}{8}$
c) $\nabla f(\vec x_{1})=(0\,;-1)$ , $t_{1}=\frac{1}{4}$ , $\vec x_{2}=\left(\frac{1}{2}\,;\frac{1}{4}\right)$ , $f(\vec x_{2})=\frac{1}{4}$
d) $\varphi'\left(\frac{1}{10}\right)=-\frac{34}{125}$ , $\varphi'\left(\frac{1}{5}\right)=\frac{93}{125}$ : $t_{2}\in\left]\frac{1}{10}\,;\frac{1}{5}\right[$ , racine d'un polynôme de degré 3
e) $\vec x_{2}$ est sur la parabole ; distance $\frac{\sqrt{13}}{4}\approx 0{,}90$ ; les pas perpendiculaires ne peuvent pas suivre une vallée courbe

a) $f$ est une somme de deux carrés, donc $f\geq 0$ , et $f(1\,;1)=2(1-1)^{2}+0=0$ : $(1\,;1)$ est un minimum global. Il est même unique : $f=0$ exige $x=1$ et $y=x^{2}=1$ . Pas besoin du test des dérivées secondes, l'inégalité $f\geq 0$ décide. Le premier terme est nul sur toute la parabole $y=x^{2}$ : c'est le FOND DE LA VALLÉE, et le second terme le fait descendre doucement vers $x=1$ . $f(\vec x_{0})=0+1=1$ . Puis $f_{x}=8x\left(x^{2}-y\right)-2(1-x)$ et $f_{y}=-4\left(x^{2}-y\right)$ , donc $\nabla f(\vec x_{0})=(-2\,;0)$ .

b) On se déplace selon $-\nabla f(\vec x_{0})=(2\,;0)$ : le point courant est $(2t\,;0)$ et $\varphi(t)=2(4t^{2})^{2}+(1-2t)^{2}=32t^{4}+(1-2t)^{2}$ . Alors $\varphi'(t)=128t^{3}-4(1-2t)=128t^{3}+8t-4$ et $\varphi''(t)=384t^{2}+8>0$ : $\varphi'$ est strictement croissante, elle s'annule une seule fois, et c'est en un minimum de $\varphi$ . On vérifie $\varphi'\left(\frac{1}{4}\right)=2+2-4=0$ . Donc $t_{0}=\frac{1}{4}$ , $\vec x_{1}=\left(\frac{1}{2}\,;0\right)$ et $f(\vec x_{1})=2\times\frac{1}{16}+\frac{1}{4}=\frac{3}{8}$ . L'équation $\varphi'=0$ est de degré $3$ : on l'a résolue parce qu'elle avait une racine évidente, et l'argument de monotonie garantit qu'il n'y en a pas d'autre. Sans lui, la réponse est incomplète.

c) En $\vec x_{1}$ : $x^{2}-y=\frac{1}{4}$ , donc $f_{x}=8\times\frac{1}{2}\times\frac{1}{4}-2\times\frac{1}{2}=0$ et $f_{y}=-1$ : $\nabla f(\vec x_{1})=(0\,;-1)$ , orthogonal à $(-2\,;0)$ comme le veut la recherche exacte, même pour une fonction non quadratique. Le point courant est $\left(\frac{1}{2}\,;t\right)$ et $\varphi(t)=2\left(\frac{1}{4}-t\right)^{2}+\frac{1}{4}$ , minimale en $t_{1}=\frac{1}{4}$ . Donc $\vec x_{2}=\left(\frac{1}{2}\,;\frac{1}{4}\right)$ et $f(\vec x_{2})=0+\frac{1}{4}=\frac{1}{4}$ .

d) En $\vec x_{2}$ , $x^{2}-y=0$ , donc $f_{x}=-1$ , $f_{y}=0$ . Le point courant est $\left(\frac{1}{2}+t\,;\frac{1}{4}\right)$ , avec $x^{2}-y=t+t^{2}$ , et $\varphi(t)=2\left(t+t^{2}\right)^{2}+\left(\frac{1}{2}-t\right)^{2}$ , de dérivée $4t(1+t)(1+2t)+2t-1$ . En $\frac{1}{10}$ : $4\times\frac{1}{10}\times\frac{11}{10}\times\frac{12}{10}=\frac{528}{1000}$ , et $\frac{528}{1000}+\frac{200}{1000}-1=-\frac{272}{1000}=-\frac{34}{125}$ . En $\frac{1}{5}$ : $4\times\frac{1}{5}\times\frac{6}{5}\times\frac{7}{5}=\frac{168}{125}$ , et $\frac{168}{125}+\frac{50}{125}-\frac{125}{125}=\frac{93}{125}$ . Comme $\varphi'$ est continue et change de signe, le théorème des valeurs intermédiaires donne une racine dans $\left]\frac{1}{10}\,;\frac{1}{5}\right[$ , unique car $\varphi'$ est croissante sur $[0\,;+\infty[$ (produit de facteurs positifs croissants, plus $2t$ ). Le pas n'a plus de forme simple : en pratique, une recherche linéaire se fait alors par un algorithme à une variable (bissection), ou on se contente d'un pas qui fait « assez » baisser $f$ .

e) $\frac{1}{4}=\left(\frac{1}{2}\right)^{2}$ : $\vec x_{2}$ est SUR la parabole, au fond de la vallée, après deux pas. Pourtant sa distance au minimum vaut $\sqrt{\frac{1}{4}+\frac{9}{16}}=\frac{\sqrt{13}}{4}\approx 0{,}90$ , contre $\sqrt{2}\approx 1{,}41$ au départ et $\frac{\sqrt{5}}{2}\approx 1{,}12$ après un pas : $f$ a été divisée par $4$ , la distance seulement par $1{,}6$ . Au fond d'une vallée, la pente transversale est nulle et la pente LE LONG de la vallée est faible ; or la méthode n'avance qu'en segments perpendiculaires entre eux, alors que le fond est COURBE. Chaque pas sort de la parabole, le suivant y revient, et l'itéré remonte vers $(1\,;1)$ par petits zigzags. C'est le comportement classique sur la fonction de Rosenbrock, dont celle-ci est une version douce.

Exercice 8 : Cinq affirmations à corriger

Chacune des cinq affirmations ci-dessous est FAUSSE. Pour chacune, faites le calcul demandé, qui la réfute, puis écrivez l'énoncé juste.

Toutes viennent de la même confusion : prendre la direction de plus forte descente, qui est une information LOCALE, pour une information sur le minimum.

a) « Avec la recherche linéaire exacte, la méthode du gradient atteint le minimum d'une quadratique en un seul pas, puisqu'elle prend le meilleur pas. » Pour $f(x,y)=x^{2}+9y^{2}$ et $\vec x_{0}=(9\,;1)$ , calculez $f(\vec x_{0})$ et $f(\vec x_{1})$ .
b) « Si l'on remplace $-\nabla f$ par le vecteur unitaire de même direction, la recherche exacte donne le même pas $t$ . » Pour $f(x,y)=x^{2}+y^{2}$ et $\vec x_{0}=(3\,;4)$ , donnez le pas optimal $t$ avec $-\nabla f(\vec x_{0})$ , puis le pas optimal $s$ avec le vecteur unitaire.
c) « Deux directions de descente successives sont parallèles, puisque la méthode suit toujours la pente. » Pour $f(x,y)=2x^{2}+y^{2}$ et $\vec x_{0}=(1\,;2)$ , faites une itération exacte et calculez $\nabla f(\vec x_{0})\cdot\nabla f(\vec x_{1})$ .
d) « Si $\|\nabla f(\vec x_{k})\|<10^{-2}$ , alors $\vec x_{k}$ est à moins de $10^{-2}$ du minimum. » Pour $f(x,y)=\frac{x^{2}}{200}+y^{2}$ , calculez $\|\nabla f\|$ au point $\left(\frac{1}{2}\,;0\right)$ et la distance de ce point au minimum.
e) « Quand la méthode du gradient s'arrête parce que $\nabla f=\vec 0$ , elle a trouvé un minimum. » Pour $f(x,y)=x^{2}-y^{2}$ et $\vec x_{0}=(1\,;0)$ , faites une itération exacte et dites où l'on arrive.

Tape tes réponses, la page te dit juste ou faux 0/8

a)

f(\vec x_{0})

f(\vec x_{1})

b)

t

avec le gradient

s

avec le vecteur unitaire

c)

Produit scalaire

d)

\|\nabla f\|

Distance au minimum

e)

Point atteint

Voir la correction

Réponses

a) $f(\vec x_{0})=90$ , $\vec x_{1}=\left(\frac{36}{5}\,;-\frac{4}{5}\right)$ , $f(\vec x_{1})=\frac{288}{5}=57{,}6$ ; un seul pas seulement si $\nabla f(\vec x_{0})$ vise le centre
b) $t=\frac{1}{2}$ mais $s=5=\|\nabla f(\vec x_{0})\|\,t$ ; le PAS change, le POINT $\vec x_{1}=(0\,;0)$ est le même
c) $t_{0}=\frac{1}{3}$ , $\vec x_{1}=\left(-\frac{1}{3}\,;\frac{2}{3}\right)$ , produit scalaire $0$ : elles sont orthogonales
d) $\|\nabla f\|=\frac{1}{200}=0{,}005$ mais la distance vaut $\frac{1}{2}$
e) $t=\frac{1}{2}$ , $\vec x_{1}=(0\,;0)$ , où $\nabla f=\vec 0$ : c'est un point de selle

a) Faux. $f(\vec x_{0})=81+9=90$ , $\nabla f(\vec x_{0})=(18\,;18)$ , et avec $H=\begin{pmatrix}2&0\\0&18\end{pmatrix}$ : $t_{0}=\frac{648}{648+5832}=\frac{1}{10}$ . Donc $\vec x_{1}=(9-1{,}8\,;1-1{,}8)=\left(\frac{36}{5}\,;-\frac{4}{5}\right)$ et $f(\vec x_{1})=\frac{1296}{25}+\frac{144}{25}=\frac{288}{5}=57{,}6$ . Le meilleur pas sur la droite de recherche n'est pas le meilleur point du plan : la droite ne passe pas par le minimum. Énoncé juste : « la recherche exacte minimise $f$ SUR LA DROITE de recherche ; le minimum n'est atteint en un pas que si $-\nabla f(\vec x_{0})$ pointe vers lui, ce qui arrive pour des courbes de niveau circulaires ou un départ sur un axe de l'ellipse ».

b) Faux. $\nabla f(\vec x_{0})=(6\,;8)$ , de norme $10$ . Avec $-\nabla f$ : $\varphi(t)=(3-6t)^{2}+(4-8t)^{2}=25(1-2t)^{2}$ , minimale en $t=\frac{1}{2}$ . Avec le vecteur unitaire $-\frac{1}{5}(3\,;4)$ : le point courant est $\left(3-\frac{3s}{5}\,;4-\frac{4s}{5}\right)$ , minimal en $s=5$ . Dans les deux cas on arrive en $(0\,;0)$ : le POINT ne dépend pas de la longueur du vecteur direction, mais le nombre $t$ en dépend, $s=\|\nabla f\|\,t$ . Le piège est réel sur une copie : un pas donné « $t=0{,}1$ » n'a de sens qu'avec la convention de l'énoncé, $\vec x_{k}-t\,\nabla f(\vec x_{k})$ sans normalisation dans le cours de MTH1101. Énoncé juste : « normaliser la direction multiplie le pas optimal par $\|\nabla f\|$ et laisse $\vec x_{k+1}$ inchangé ».

c) Faux. $\nabla f=(4x\,;2y)$ , $\nabla f(\vec x_{0})=(4\,;4)$ , $t_{0}=\frac{32}{64+32}=\frac{1}{3}$ , $\vec x_{1}=\left(1-\frac{4}{3}\,;2-\frac{4}{3}\right)=\left(-\frac{1}{3}\,;\frac{2}{3}\right)$ et $\nabla f(\vec x_{1})=\left(-\frac{4}{3}\,;\frac{4}{3}\right)$ . Produit scalaire : $-\frac{16}{3}+\frac{16}{3}=0$ . Énoncé juste : « avec la recherche exacte, deux gradients successifs sont ORTHOGONAUX ; ce sont les directions $k$ et $k+2$ qui sont parallèles, en dimension deux ». La méthode suit la pente au départ de chaque pas, pas pendant le pas : une fois lancée sur sa droite, elle ne tourne plus jusqu'au point de tangence.

d) Faux. $\nabla f=\left(\frac{x}{100}\,;2y\right)$ , donc en $\left(\frac{1}{2}\,;0\right)$ : $\nabla f=\left(\frac{1}{200}\,;0\right)$ , de norme $0{,}005<10^{-2}$ . Pourtant la distance au minimum $(0\,;0)$ vaut $\frac{1}{2}$ , cinquante fois plus. Une fonction TRÈS PLATE dans une direction a un petit gradient loin de son minimum. Énoncé juste : « un petit gradient dit que la pente est faible, pas que l'on est près du minimum ; le critère $\|\nabla f\|<\varepsilon$ est un critère d'arrêt pratique, pas une garantie de précision sur $\vec x$ ». Sur ce point, $f=\frac{1}{800}$ : c'est plutôt la VALEUR de $f$ qui est presque optimale.

e) Faux. $\nabla f=(2x\,;-2y)$ , $\nabla f(\vec x_{0})=(2\,;0)$ , et $\varphi(t)=(1-2t)^{2}$ , minimale en $t=\frac{1}{2}$ : $\vec x_{1}=(0\,;0)$ , où $\nabla f=\vec 0$ . L'algorithme s'arrête. Mais $f(0\,;y)=-y^{2}<0=f(0\,;0)$ : l'origine est un point de SELLE, le test des dérivées secondes donne $D=(2)(-2)-0=-4<0$ . Énoncé juste : « la méthode s'arrête en un POINT CRITIQUE ; il faut ensuite le classer ». En pratique un départ générique, comme $(1\,;0{,}01)$ , s'éloigne de la selle, car la composante en $y$ grandit à chaque itération, mais rien n'est garanti sans hypothèse sur $f$ .

Exercice 9 : Apprentissage automatique : le taux d'apprentissage et l'échelle des variables

Un modèle prédit une valeur $\hat y=w_{1}x_{1}+w_{2}x_{2}$ à partir de deux variables $x_{1}$ et $x_{2}$ . On règle les poids $(w_{1}\,;w_{2})$ en minimisant la PERTE $L=\frac{1}{2}\sum\left(\hat y-y\right)^{2}$ sur les exemples d'entraînement, par la méthode du gradient à pas fixe : en apprentissage automatique, le pas s'appelle le TAUX D'APPRENTISSAGE $\eta$ , et une itération une ÉPOQUE.

Jeu A : deux exemples, $(x_{1}\,;x_{2}\,;y)=(1\,;1\,;3)$ et $(1\,;-1\,;1)$ . Jeu B : les mêmes, mais $x_{2}$ est mesuré dans une unité trois fois plus petite, d'où $(1\,;3\,;3)$ et $(1\,;-3\,;1)$ . La figure montre deux courbes de niveau de chaque perte : $L_{A}$ en pointillé, $L_{B}$ en trait plein. Partout, on part de $\vec w_{0}=(0\,;0)$ .

a) Montrez que $L_{B}=w_{1}^{2}+9w_{2}^{2}-4w_{1}-6w_{2}+5$ et donnez son minimum et la valeur de la perte en ce minimum. (On admet $L_{A}=w_{1}^{2}+w_{2}^{2}-4w_{1}-2w_{2}+5$ .)
b) Sur le jeu A, avec $\eta=\frac{1}{2}$ : faites une époque. Où arrive-t-on ?
c) Sur le jeu B, notez $e_{1}=w_{1}-2$ et $e_{2}=w_{2}-\frac{1}{3}$ . Montrez que chaque époque multiplie $e_{1}$ par $1-2\eta$ et $e_{2}$ par $1-18\eta$ . Pour quels $\eta$ l'apprentissage converge-t-il ? Que se passe-t-il avec le taux $\eta=\frac{1}{2}$ du jeu A ?
d) Sur le jeu B, avec $\eta=\frac{1}{10}$ : calculez $\vec w_{1}$ , puis la perte après une et deux époques. Justifiez que $\frac{1}{10}$ est le meilleur taux fixe pour ce jeu.
e) Avec $\eta=\frac{1}{10}$ , combien d'époques faut-il pour diviser la distance au minimum par $100$ ? On donne $\ln 2\approx 0{,}693$ et $\ln 10\approx 2{,}303$ . Quelle leçon pratique en tirer ?

Voir la correction

Réponses

a) minimum $\left(2\,;\frac{1}{3}\right)$ , perte $0$ ; $L_{B}=(w_{1}-2)^{2}+9\left(w_{2}-\frac{1}{3}\right)^{2}$
b) $\vec w_{1}=(0\,;0)-\frac{1}{2}(-4\,;-2)=(2\,;1)$ , le minimum de $L_{A}$ , en une époque
c) $0<\eta<\frac{1}{9}$ ; avec $\eta=\frac{1}{2}$ , $e_{2}$ est multiplié par $-8$ : divergence
d) $\vec w_{1}=\left(\frac{2}{5}\,;\frac{3}{5}\right)$ , $L=\frac{16}{5}=3{,}2$ puis $\frac{256}{125}=2{,}048$ ; $|1-2\eta|=|1-18\eta|$ en $\eta=\frac{1}{10}$
e) $\left(\frac{5}{4}\right)^{k}>100$ , $k>\frac{4{,}606}{0{,}224}\approx 20{,}6$ , donc $21$ époques ; mettre les variables à la même échelle

a) $L_{B}=\frac{1}{2}\left[(w_{1}+3w_{2}-3)^{2}+(w_{1}-3w_{2}-1)^{2}\right]$ . En développant, les doubles produits $\pm 6w_{1}w_{2}$ se compensent et $L_{B}=\frac{1}{2}\left[2w_{1}^{2}+18w_{2}^{2}-8w_{1}-12w_{2}+10\right]=w_{1}^{2}+9w_{2}^{2}-4w_{1}-6w_{2}+5$ . En complétant les carrés, $L_{B}=(w_{1}-2)^{2}+9\left(w_{2}-\frac{1}{3}\right)^{2}$ : le minimum est $\left(2\,;\frac{1}{3}\right)$ et la perte y vaut $0$ , car deux poids suffisent à reproduire exactement deux exemples. Le modèle appris est le même que pour le jeu A, de minimum $(2\,;1)$ : $w_{2}$ est divisé par $3$ parce que $x_{2}$ est multiplié par $3$ .

b) $\nabla L_{A}=(2w_{1}-4\,;2w_{2}-2)$ , qui vaut $(-4\,;-2)$ en $\vec w_{0}$ . Avec $\eta=\frac{1}{2}$ , $\vec w_{1}=(0\,;0)-\frac{1}{2}(-4\,;-2)=(2\,;1)$ : c'est le minimum, atteint en UNE époque. Ce n'est pas de la chance : $L_{A}=(w_{1}-2)^{2}+(w_{2}-1)^{2}$ a des courbes de niveau circulaires (les cercles en pointillé), le gradient vise donc toujours le centre, et le pas $\frac{1}{2}$ est exactement celui qui l'atteint.

c) $\nabla L_{B}=(2w_{1}-4\,;18w_{2}-6)=(2e_{1}\,;18e_{2})$ . Une époque donne $e_{1}\leftarrow e_{1}-2\eta e_{1}=(1-2\eta)e_{1}$ et $e_{2}\leftarrow(1-18\eta)e_{2}$ . L'apprentissage converge pour tout départ si et seulement si $|1-2\eta|<1$ et $|1-18\eta|<1$ , soit $0<\eta<\frac{1}{9}$ . Avec le taux du jeu A, $\eta=\frac{1}{2}$ , le facteur de $e_{2}$ vaut $1-9=-8$ : l'erreur sur $w_{2}$ est multipliée par $-8$ à chaque époque et la perte explose. Même modèle, même taux : un simple CHANGEMENT D'UNITÉ suffit à faire diverger l'entraînement : la variable $x_{2}$ multipliée par $3$ multiplie la courbure $\frac{\partial^{2}L}{\partial w_{2}^{2}}$ par $9$ , et c'est la plus forte courbure qui impose le taux.

d) $\nabla L_{B}(\vec w_{0})=(-4\,;-6)$ , donc $\vec w_{1}=\left(\frac{4}{10}\,;\frac{6}{10}\right)=\left(\frac{2}{5}\,;\frac{3}{5}\right)$ . Les facteurs valent $\frac{4}{5}$ et $-\frac{4}{5}$ ; comme $L_{B}=e_{1}^{2}+9e_{2}^{2}$ , chaque époque multiplie la perte par $\frac{16}{25}$ : $L(\vec w_{0})=4+1=5$ , $L(\vec w_{1})=\frac{16}{5}=3{,}2$ , $L(\vec w_{2})=\frac{256}{125}=2{,}048$ . Contrôle direct : $\left(\frac{2}{5}-2\right)^{2}+9\left(\frac{3}{5}-\frac{1}{3}\right)^{2}=\frac{64}{25}+9\times\frac{16}{225}=\frac{64}{25}+\frac{16}{25}=\frac{16}{5}$ . Le taux $\frac{1}{10}$ est le meilleur : le plus grand des deux facteurs $|1-2\eta|$ (décroissant) et $|1-18\eta|$ (croissant au-delà de $\frac{1}{18}$ ) est minimal quand ils sont égaux, $1-2\eta=18\eta-1$ , soit $\eta=\frac{1}{10}$ . Le zigzag de $w_{2}$ autour de $\frac{1}{3}$ est la signature de ce compromis.

e) $|e_{1}|$ et $|e_{2}|$ sont tous deux multipliés par $\frac{4}{5}$ , donc la distance au minimum aussi. On veut $\left(\frac{4}{5}\right)^{k}\leq\frac{1}{100}$ , soit $k\ln\frac{5}{4}\geq\ln 100$ . Or $\ln\frac{5}{4}=\ln 10-3\ln 2\approx 2{,}303-2{,}079=0{,}224$ et $\ln 100\approx 4{,}606$ , d'où $k\geq 20{,}6$ : il faut $21$ époques, contre UNE pour le jeu A. Contrôle : $\left(\frac{5}{4}\right)^{20}\approx 86{,}7$ et $\left(\frac{5}{4}\right)^{21}\approx 108{,}4$ . La leçon est celle de tous les praticiens : avant d'entraîner un modèle par descente de gradient, on remet les variables à la MÊME ÉCHELLE (on les « normalise »). Cela arrondit les courbes de niveau de la perte, et un taux unique convient alors à toutes les directions.

Exercice 10 : Le coût d'un réseau à régler : la puissance dissipée

Un réseau relie une source à $12$ V à la masse par trois résistances de $1\ \Omega$ en série. On note $u$ et $v$ les potentiels des deux nœuds intermédiaires. Pour des potentiels $(u\,;v)$ quelconques, la puissance dissipée serait $P(u,v)=(12-u)^{2}+(u-v)^{2}+v^{2}$ , en watts. Les potentiels réels sont ceux qui minimisent $P$ : c'est le principe de dissipation minimale.

Sur un réseau de milliers de nœuds, on ne résout pas le système à la main : on fait descendre le coût $P$ par un algorithme. On le fait ici sur deux nœuds, avec la recherche linéaire exacte, dont la hessienne vaut $H=\begin{pmatrix}4&-2\\-2&4\end{pmatrix}$ .

a) Trouvez le minimum exact de $P$ en résolvant $\nabla P=\vec 0$ , et la puissance minimale $P^{*}$ . Interprétez.
b) À partir de $\vec x_{0}=(0\,;0)$ , faites une itération : $\nabla P(\vec x_{0})$ , le pas $t_{0}$ , $\vec x_{1}$ et $P(\vec x_{1})$ .
c) Faites deux itérations de plus. Donnez $\vec x_{2}$ , $\vec x_{3}$ , $P(\vec x_{3})$ , et la suite des écarts $P(\vec x_{k})-P^{*}$ pour $k=0$ à $3$ .
d) Dans un vrai réseau, $P^{*}$ est inconnue : on s'arrête quand $\|\nabla P(\vec x_{k})\|<10^{-2}$ . Calculez $\|\nabla P(\vec x_{k})\|$ pour $k=1,2,3$ , devinez la loi et donnez l'itération d'arrêt.
e) Un technicien part plutôt de $\vec x_{0}=(6\,;6)$ . Faites une itération et expliquez le résultat.

Voir la correction

Réponses

a) $(u\,;v)=(8\,;4)$ , $P^{*}=48$ W : le diviseur de tension, $4$ A dans chaque résistance
b) $\nabla P(\vec x_{0})=(-24\,;0)$ , $t_{0}=\frac{1}{4}$ , $\vec x_{1}=(6\,;0)$ , $P(\vec x_{1})=72$
c) $\vec x_{2}=(6\,;3)$ , $\vec x_{3}=\left(\frac{15}{2}\,;3\right)$ , $P(\vec x_{3})=49{,}5$ ; écarts $96$ , $24$ , $6$ , $\frac{3}{2}$
d) $\|\nabla P(\vec x_{k})\|=\frac{12}{2^{k-1}}$ : $12$ , $6$ , $3$ ; arrêt à $k=12$
e) $\nabla P=(-12\,;12)$ , $t=\frac{1}{6}$ , $\vec x_{1}=(8\,;4)$ : le minimum en un pas, car $\nabla P(\vec x_{0})=6(\vec x_{0}-\vec x^{*})$

a) $P_{u}=-2(12-u)+2(u-v)=4u-2v-24$ et $P_{v}=-2(u-v)+2v=-2u+4v$ . $\nabla P=\vec 0$ donne $u=2v$ , puis $8v-2v=24$ : $v=4$ et $u=8$ . La hessienne a $P_{uu}=4>0$ et $D=16-4=12>0$ : c'est le minimum, unique. $P^{*}=16+16+16=48$ W. On retrouve le diviseur de tension : trois résistances égales se partagent les $12$ V en trois chutes de $4$ V, un courant de $4$ A les traverse, et $3\times 4^{2}\times 1=48$ W. Le principe de dissipation minimale redonne les lois de Kirchhoff.

b) $\nabla P(\vec x_{0})=(-24\,;0)$ . Formule du pas : $\vec g\cdot\vec g=576$ , $H\vec g=(-96\,;48)$ , $\vec g\cdot H\vec g=2304$ , d'où $t_{0}=\frac{576}{2304}=\frac{1}{4}$ . Alors $\vec x_{1}=(0\,;0)-\frac{1}{4}(-24\,;0)=(6\,;0)$ et $P(\vec x_{1})=36+36+0=72$ . Le gradient ne portait que sur $u$ : la méthode n'a réglé que le premier nœud, en lui donnant le potentiel qui équilibre ses deux voisins, $\frac{12+0}{2}=6$ .

c) $\nabla P(\vec x_{1})=(24-0-24\,;-12)=(0\,;-12)$ , orthogonal au précédent ; $\vec g\cdot\vec g=144$ , $\vec g\cdot H\vec g=4\times 144=576$ , $t_{1}=\frac{1}{4}$ et $\vec x_{2}=(6\,;3)$ , avec $P(\vec x_{2})=36+9+9=54$ . Puis $\nabla P(\vec x_{2})=(24-6-24\,;-12+12)=(-6\,;0)$ , $t_{2}=\frac{1}{4}$ et $\vec x_{3}=\left(\frac{15}{2}\,;3\right)$ , avec $P(\vec x_{3})=\frac{81}{4}+\frac{81}{4}+9=49{,}5$ . Les écarts à $P^{*}$ valent $96$ , $24$ , $6$ , $\frac{3}{2}$ : divisés par $4$ à chaque itération après la première. Le trajet est un ESCALIER, un nœud réglé à la fois sur son équilibre local, ce que l'exercice 5 annonçait : en dimension deux, les directions alternent.

d) $\|\nabla P(\vec x_{1})\|=12$ , $\|\nabla P(\vec x_{2})\|=6$ , $\|\nabla P(\vec x_{3})\|=3$ : la norme est divisée par $2$ à chaque pas, $\|\nabla P(\vec x_{k})\|=\frac{12}{2^{k-1}}$ pour $k\geq 1$ , ce qu'on prouve comme à l'exercice 6, la configuration se reproduisant à l'échelle $\frac{1}{4}$ tous les deux pas. Le critère $\frac{12}{2^{k-1}}<10^{-2}$ équivaut à $2^{k-1}>1200$ ; or $2^{10}=1024$ et $2^{11}=2048$ , donc $k-1=11$ et l'algorithme s'arrête à $k=12$ . L'écart vaut alors $\frac{24}{4^{11}}$ , environ $6\times 10^{-6}$ W : le critère sur le gradient est ici plus exigeant que nécessaire sur le coût, et c'est le seul qu'on peut calculer sans connaître $P^{*}$ .

e) $\nabla P(6\,;6)=(24-12-24\,;-12+24)=(-12\,;12)$ , $\vec g\cdot\vec g=288$ , $H\vec g=(-72\,;72)$ , $\vec g\cdot H\vec g=1728$ , donc $t=\frac{1}{6}$ et $\vec x_{1}=(6+2\,;6-2)=(8\,;4)$ : le minimum exact, en UN pas. Ce n'est pas un hasard : $\vec x_{0}-\vec x^{*}=(-2\,;2)$ et $\nabla P(\vec x_{0})=(-12\,;12)=6\,(\vec x_{0}-\vec x^{*})$ . Le gradient est colinéaire au vecteur qui va du minimum au point : $-\nabla P$ VISE le minimum, parce que le point de départ est sur un axe des ellipses de niveau. C'est l'exception qui confirme le fil du chapitre : en général $-\nabla P$ ne vise pas le minimum, et la méthode zigzague.

Il manque quelque chose dans cette série ? Un type d'exercice que ton prof donne, un énoncé qui te bloque, 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.

Chapitre précédent Extrema et optimisation sans contrainte Chapitre suivant Les multiplicateurs de Lagrange

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

Voir aussi

Tous les exercices Cours préparatoires de Polytechnique Études supérieures

La méthode du gradient : exercices corrigés de MTH1101 (Polytechnique)

Rappel de cours

Partie A : les bases (/50)

Exercice 1 : La direction de plus forte descente, et le pas qui fait remonter

Exercice 2 : Une itération avec recherche linéaire exacte

Exercice 3 : Le pas optimal par la formule, et le facteur 2 de la hessienne

Exercice 4 : Le pas fixe : quand la méthode diverge

Exercice 5 : Démontrer : gradients successifs orthogonaux et formule du pas

Partie B : problèmes et raisonnement (/50)

Exercice 6 : Le zigzag lu sur une carte de contour

Exercice 7 : Une vallée courbe : la méthode hors des quadratiques

Exercice 8 : Cinq affirmations à corriger

Exercice 9 : Apprentissage automatique : le taux d'apprentissage et l'échelle des variables

Exercice 10 : Le coût d'un réseau à régler : la puissance dissipée

Voir aussi

La méthode du gradient bloque en MTH1101 ?