Descente de gradient à deux variables

La descente de gradient utilise les pentes suivant les deux coordonnées pour chercher un minimum de $f(x,y)$. Un premier calcul montre comment les deux coordonnées sont mises à jour ensemble.

Exemple pratique

Considérons cette fonction illustrative de température dans une pièce :

$$f(x,y)=85-\frac{1}{90}x^2(x-6)^2-y^2(y-6)^2, \qquad (x,y)\in[0,5]^2.$$

Ce modèle diffère de celui du sauna précédent et n'est pas un modèle physique de température étalonné. Les limites de la pièce comptent : sans restriction du domaine, le polynôme est non borné inférieurement et il n'existe donc pas de point le plus frais.

Calcul du premier pas

Partons de $(x_0,y_0)=(0.5,0.6)$ avec un taux d'apprentissage $\alpha=0.05$. Pour calculer les dérivées partielles, posons $h(t)=t^2(t-6)^2$. Alors $f=85-h(x)/90-h(y)$ et $h'(t)=4t(t-3)(t-6)$, d'où le gradient

$$\nabla f(x,y)=\left(-\frac{4x(x-3)(x-6)}{90},\;-4y(y-3)(y-6)\right).$$

Au point initial, $\nabla f(0.5,0.6)\approx(-0.3055556,-31.104)$. Retranchons $0.05$ fois chaque composante :

$$\begin{aligned} x_1&=0.5-0.05\left(-\frac{11}{36}\right)\approx0.5152778,\\ y_1&=0.6-0.05(-31.104)=2.1552. \end{aligned}$$

Les deux composantes doivent être calculées au même ancien point, avant toute mise à jour. Le nouveau point reste dans la pièce et $f$ passe d'environ $74.418372$ à $16.248271$.

Vue conceptuelle

Le gradient $\nabla f=\left(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\right)$ rassemble les deux dérivées partielles. Lorsqu'il est non nul, il indique la direction de plus forte croissance instantanée ; sa norme est ce taux maximal par unité de distance. La descente de gradient suit la direction opposée, celle de plus forte décroissance locale. Cette direction locale ne garantit ni une diminution pour n'importe quel pas fini ni l'arrivée à un minimum.

Formulation mathématique

Depuis le point courant $(x_k,y_k)$, la mise à jour s'écrit

$$\begin{aligned} (x_{k+1},y_{k+1}) &=(x_k,y_k)-\alpha\nabla f(x_k,y_k)\\ &=(x_k,y_k)-\alpha\left(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\right)_{(x_k,y_k)}. \end{aligned}$$

Le taux d'apprentissage $\alpha$ multiplie les deux composantes du déplacement. Un pas trop grand peut dépasser un minimum ; un pas très petit peut ralentir la convergence.

Algorithme à deux variables

Choisir un point initial $(x_0,y_0)$, calculer son gradient et répéter la mise à jour. Pour une pièce soumise à une contrainte de boîte, garder chaque nouveau point admissible en projetant la mise à jour :

$$q_{k+1}=\Pi_{[0,5]^2}(q_k-\alpha\nabla f(q_k)), \qquad q_k=(x_k,y_k),$$

où $\Pi$ ramène chaque coordonnée dans $[0,5]$. Surveiller la diminution de l'objectif et le résidu de gradient projeté

$$\frac{\|q-\Pi_{[0,5]^2}(q-\alpha\nabla f(q))\|_2}{\alpha}.$$

Fixer aussi une limite d'itérations. De petites variations entre les points ne prouvent pas un minimum. Avec la contrainte de boîte, le seul gradient brut ne suffit pas : un optimum au bord n'a pas forcément un gradient nul. Même un petit résidu projeté ne teste que la stationnarité dans ce problème non convexe.

Défis et considérations

Pour ce modèle, on peut aussi calculer le minimum exact. Sur $[0,5]$, $h$ atteint son unique maximum $81$ en $3$. Maximiser séparément les deux termes soustraits donne le minimum global $(3,3)$ avec $f=3.1$. En revanche, partir de $(0,0)$ donne un gradient nul : l'itération reste immobile sans atteindre ce minimum. En général, la descente peut converger vers un minimum local plutôt que global ; essayer plusieurs points initiaux peut réduire ce risque, sans prouver l'optimalité globale.

En $(3,3)$, la Hessienne est $\operatorname{diag}(0.4,36)$. La linéarisation de l'itération donne la plage suffisante de contraction locale $0<\alpha<1/18$. Ainsi, $0.05$ est proche de la limite de stabilité en $y$, mais avance lentement en $x$. Depuis le départ indiqué, 1000 pas donnent approximativement $(3,3)$ ; cet essai ne prouve pas la convergence depuis tout point initial.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.