Descente de gradients et variantes

Auteur·rice

Joseph Salmon, Tanguy Lefort, Amélie Vernay

Pour ce TP noté, vous devrez charger votre fichier sur Moodle, avant 23h59, mercredi 13/03/2024.

Important

Pour ce travail vous devez déposer un unique fichier au format .py ou .ipynb, structuré avec des cellules, dont le nom est tp_note_HAX606X_Prenom_Nom.py (ou tp_note_HAX606X_Prenom_Nom.ipynb). Vous remplirez votre nom, prénom de manière adéquate. Si le nom de fichier ne suit pas cette forme, vous perdez 1 pt.

Soumettez une version préalable par sécurité sur Moodle (que vous modifierez par la suite).

La note totale est sur 20 points répartis comme suit :

qualité des réponses aux questions : 18 pts,
qualité du code (noms de variables clairs, commentaires, code synthétique, etc.) : 1 pt
reproductibilité (exécution correcte) et absence de bug : 1 pt

Objectifs de ce TP

Comment optimiser une fonction 2D ou en dimension supérieure? Etude de l’impact de la stratégie de descente sur la trajectoire des itérés au cours de l’optimisation.
Application de la descente de gradient. Stocker des variables d’intérêt. Visualiser une expérience numérique et comparer deux méthodes d’optimisations.

Dans ce TP, nous allons proposer deux algorithmes pour trouver un minimiseur d’une fonction f:\mathbb{R}^d\rightarrow\mathbb{R} avec d\geq 2.

Algorithme de la descente de gradient

Dans cette partie, on suppose f une fonction lisse et notre but est d’introduire la méthode de descente de gradient (🇬🇧: gradient descent, GD) pour trouver son (ou un de ses) minima.

    \begin{algorithm}
    \caption{Descente de gradient à pas fixe}
    \begin{algorithmic}
    \INPUT $\nabla f, x_{init}, \gamma,$ maxiter, $\epsilon$
    \STATE $x = x_{init}$
    \COMMENT{Initialization}
    \FOR{$i=1,\dots,$maxiter}
        \STATE $g\leftarrow \nabla f(x)$
        \COMMENT{Evaluation du gradient en l'itéré courant}
    \IF{$\|g\|^2 \leq \epsilon^2$ }
        \COMMENT{Caractérisation d'un extremum}
        \STATE Break
    \ELSE
    \STATE $x \leftarrow x - \gamma g$
    \COMMENT{Pas dans la direction opposée au gradient}
    \ENDIF
    \ENDFOR
    \OUTPUT $x$
    \end{algorithmic}
    \end{algorithm}

Question 1: Coder la descente de gradient

Adapter en Python l’algorithme de la descente de gradient pour avoir en sortie la liste de la suite des itérés (x_k)_k.

Vérifier que votre méthode obtient bien le minimum global pour la fonction f_{test}: \begin{align*} f_{test}:\quad \mathbb{R}^2 &\to \mathbb{R}\\ \begin{pmatrix} x_1 \\ x_2 \\\end{pmatrix} & \mapsto (x_1 - 1)^2 + 3(x_2 + 1)^2 \end{align*}

Code

import matplotlib.pyplot as plt
from matplotlib import cm
import numpy as np

def ftest(x, y):
    return (x - 1) ** 2 + 3*(y + 1)**2

fig, ax = plt.subplots(subplot_kw={"projection": "3d"})
X = np.arange(-5, 5, 0.25)
Y = np.arange(-5, 5, 0.25)
X, Y = np.meshgrid(X, Y)
Z = ftest(X, Y)

# Plot the surface.
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm,
                       linewidth=0, antialiased=False)

# Add a color bar which maps values to colors.
fig.colorbar(surf, shrink=0.5, aspect=5)
plt.show()

Figure 1: Visualisation de la fonction test

Note

La méthode de la descent de gradient ne nécessite pas en entrée la fonction, mais uniquement son gradient. Il est donc nécessaire de calculer le gradient de f_{test} et de l’implémenter séparément.

Question 2: application au cas quadratique

Soit la fonction quadratique

f_{\alpha, \beta}(x,y) = \frac{y^2}{\alpha} + \frac{x^2}{\beta}, \alpha,\beta>0.

Tracer sur un même graphique l’évolution graphique de la valeur de l’objectif f_{\alpha,\beta}(x_k) au cours des itérations de l’algorithme de descente de gradient. Prendre \alpha=\beta et \alpha=1 puis faire de même avec \alpha=10, 50, 100. Le nombre de pas sera fixé à 1000 avec un pas de 0.01.
Tracer les lignes de niveaux de chaque fonction f_{\alpha,\beta} et les points des itérés. On pourra s’aider de la foncton contour de matplotlib.
Que remarquez vous sur les vitesses de convergence ? Comparer sur un graphique la distance à l’optimum en norme \ell_2 pour chacun des cas avec une échelle logarithmique. Donnez une explication.
Proposer deux couples de valeurs de (\alpha,\beta) avec \alpha\neq\beta et un même nombre d’itérations et taille de pas permettant d’explorer des courbures différentes. Retrouve-t-on les mêmes problèmes sur la difficulté de minimiser f_{\alpha,\beta}.

Descente par coordonnée

Les méthodes de descente par coordonnée (🇬🇧: coordinate descent, CD) consistent à résoudre le problème d’optimisation en résolvant itérativement des problèmes (potentiellement beaucoup) plus petits.

Question 3: Descente de gradient par coordonnée

Résoudre le problème d’optimisation exacte 1D pour chaque coordonnée peut être coûteux selon la fonction en question. On préfère donc souvent utiliser des méthodes de descente à pas fixe (ou variable).

    \begin{algorithm}
    \caption{Descente de gradient par coordonnée à pas fixe}
    \begin{algorithmic}

        \INPUT{$\nabla f = (\frac{\partial f}{\partial x_1}, \dots, \frac{\partial f}{\partial x_p}), x_{\rm init},\gamma, n_{\rm iter}$}
        \STATE{$x\gets x_{\rm init}$}

        \FOR{$i=1,\dots,n_{\rm iter}$}

        \FOR{$j=1,\dots,p$}
        \STATE $x_j \gets x_j - \gamma \frac{\partial f}{\partial x_j}(x)$
        \COMMENT{Itération de descente de gradient sur la coordonnée $j$}
        \ENDFOR
        \ENDFOR
        \OUTPUT{$x$}
    \end{algorithmic}
    \end{algorithm}

Coder la méthode de la descente de gradient par coordonnées avec le même critère d’arrêt que la descente de gradient classique.
Comparer la descente de gradient classique à la descente de gradient par coordonnées pour la fonction f_{\alpha,\beta} avec différentes valeurs de \alpha=\beta.
Intepréter la forme des trajectoires obtenues pour les itérés de chaque méthode. Pour la descente de gradient, on représentera sur les lignes de niveaux la suite des (x_k)_k. Pour la méthode de descente de gradient par coordonnées, on représentera les points après chaque mise à jour de coordonnée (il y aura donc deux fois plus de points pour cette dernière méthode).

Question 4: Avec scipy

En pratique, il existe beaucoup d’autres méthodes d’optimisation. Un catalogue non exhaustif est disponible dans la librairie scipy de calcul scientifique avec Python. La méthode minimize (documentation disponible au lien suivant) permet notamment d’explorer ce catalogue.

Est-ce que la méthode de desente de gradient fait partie du catalogue de méthodes disponibles dans la fonction minimize ?

Partie a) problème convexe

Minimiser la fonction f_{20,20} avec la méthode de Nelder-Mead et CG dans scipy avec une précision de l’ordre de 10^{-10}. On pourra s’aider de la ligne de code ci-dessous.

res = minimize(..., method="...", tol=...)

Comparer les résultats obtenus: - En nombre d’itérations - En résultat obtenu: res.x Expliquer les sorties des arguments res.success, res.message et res.nfev. Comparer entre les deux méthodes.

Partie b) problème non convexe

Soit la fonction de Rosenbrock f_r définie par:

f_r(x,y) = (1-x)^2 + 100 (y-x^2)^2

Cette fonction très connue en optimisation présente un minimum global en (1,1) mais les algorithmes y convergent difficilement.

Représenter la fonction de Rosenbrock en 3D et ses lignes de niveaux sur [-5,5]^2
Représenter les lignes de niveau sur [0, 1.5]^2. D’où vient la difficulté d’optimiser cette fonction ?
Minimiser la fonction de Rosenbrock avec la descente de gradient classique puis la descente de gradient par coordonnées en initialisant avec 3 points différents dans [-3,3]^2 (n’étant pas la solution). Vous utiliserez la même taille de pas et le même nombre d’itérations pour chaque point initial (utilisez des valeurs qui permettent de voir des convergences).
Proposer deux visualisations graphiques permettant de comparer les trajectoires de convergence.
Utiliser la méthode de Nelder-Mead de scipy pour minimiser la fonction de Rosenbrock. Comparer le nombre d’itérations effectuées avec celui de la descente de gradient (classique et par coordonnées) pour un même seuil de tolérance. Interpréter.