Descente de gradients et variantes

Auteur·rice

Joseph Salmon, Tanguy Lefort

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.

Certains packages utilisés peuvent nécessiter une installation préalable. Il sera utile d’utiliser les commandes suivantes avant de leur première utilisation:

pip install ipympl
pip install numba

Trois fichiers Python annexe sont fournis avec ce TP pour les visualisations (liens cliquables): dico_math_functions.py, widget_convergence.py et widget_level_set.py.

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}: f_{test}: \begin{pmatrix} x_1 \\ x_2 \\\end{pmatrix} \mapsto (x_1 - 1)^2 + 3(x_2 + 1)^2

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

On rappelle que toute matrice symétrique définie positive de taille 2\times 2 peut s’écrire: \Sigma_{\theta,\sigma_1,\sigma_2}= \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{pmatrix}^\top \begin{pmatrix} \sigma_1 & 0 \\ 0 & \sigma_2 \end{pmatrix} \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{pmatrix} \enspace, pour un certain triplet \theta \in \mathbb{R}, \sigma_1 \in \mathbb{R}_+ et \sigma_2 \in \mathbb{R}_+,

On s’intéressera dans la suite aux fonctions quadratiques de la forme suivante:

\begin{align*} f_{\theta,\sigma_1,\sigma_2}: \mathbb{R}^2 &\to \mathbb{R}\\ x &\mapsto \tfrac{1}{2} x^\top \Sigma_{\theta,\sigma_1,\sigma_2}x \enspace. \end{align*}

Le code pour calculer le gradient de la fonction f_{\theta,\sigma_1,\sigma_2} en un point x est donné par la fonction quad_grad ci-dessous:

def angle_scalar_to_covmat(theta, sig1, sig2):
    """Créer une matrice de covariance."""
    rotation = np.zeros((2, 2))
    rotation[0, 0] = np.cos(theta)
    rotation[1, 0] = np.sin(theta)
    rotation[0, 1] = -np.sin(theta)
    rotation[1, 1] = np.cos(theta)
    Sigma = rotation.T @ np.array([[sig1, 0.0], [0.0, sig2]]) @ rotation
    return Sigma


def quad_grad(x, theta=0, sig1=1, sig2=1):
    Sigma = angle_scalar_to_covmat(theta, sig1, sig2)
    return Sigma @ x

Utiliser la fonction quad_grad pour calculer les itérés de la descente de gradient appliquée à f pour des valeurs de \theta,\sigma_1 et \sigma_2 données.

Tracer l’évolution graphique de la valeur de l’objectif f_{\theta,\sigma_1,\sigma_2}(x_k) au cours des itérations de l’algorithme de descente de gradient. On affichera des points (et non une courbe continue).

Pour visualiser l’impact des paramètres sur la fonction, on pourra utiliser les visualisations de la surface et de ses lignes de niveaux (🇬🇧: level set) disponibles dans le fichier widget_level_set.py.

Descente par coordonnée

Dans cette partie, notons e_1,\dots,e_d la base canonique de \mathbb{R}^d.

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.

    \begin{algorithm}
    \caption{Descente de coordonnée exacte}
    \begin{algorithmic}
    \INPUT $f, x_{init},$ maxiter, $\epsilon$
    \STATE $x = x_{init}$
    \COMMENT{Initialization}
    \FOR{$i=1,\dots,$maxiter}
    \FOR{$j=1,\dots,d$}
        \STATE $\tau_j \in \displaystyle\argmin_{t\in\mathbb{R}}f(x+t\cdot e_j)$
        \COMMENT{Résolution problème 1D}
        \STATE $x_j \leftarrow x_j + \tau_j$
    \ENDFOR
    \IF{critère arrêt vérifié}
        \STATE Break
    \ENDIF
    \ENDFOR
    \OUTPUT $x$
    \end{algorithmic}
    \end{algorithm}
Note

Pour une fonction g, la notation \tau \in \displaystyle\argmin_{t}g(t) signifie que \tau est un point qui atteint la valeur \displaystyle\min_{t}g(t), ainsi: g(\tau)=\displaystyle\min_{t}g(t).

Question 3: Scipy et la descente par coordonnée exacte

Coder l’algorithme de descente par coordonnée exacte. On utilisera pour cela la fonction optimize de scipy pour résoudre le problème d’optimisation 1D. On rajoutera un critère d’arrêt effectué après chaque boucle de passage sur la totalité des coordonnées du vecteur x.

Question 4: Descente de gradient par coordonnée

Résoudre le problème d’optimisation 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).

Comparer la descente de gradient classique à la descente de gradient par coordonnées pour la fonction f_{test}.

A l’aide de l’interface interactive disponible dans le fichier widget_convergence.py, comparer la convergence de la descente de gradient classique à la descente de gradient par coordonnées dans le cas quadratique. On fera notamment varier les paramètres \sigma_1,\sigma_2,\theta et la taille du pas pour chaque méthode.

    \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,d$}
        \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}
Pour aller plus loin

Ajouter la descente par coordonnée exacte dans la visualisation. Pour cela, il faudra créer une entrée dans dic_optim_algos qui associe au nom de l’algorithme la fonction renvoyant les itérés, une couleur et un type de marqueur. Pour simplifier, on pourra utiliser un curseur (🇬🇧 slider) comme pour les autres méthodes, mais qui n’aura aucun impact sur l’algorithme en question. En entrée, la fonction devra prendre les mêmes arguments que quad_coordinate (ou quad_grad_descent). On utilisera de même des valeurs par défaut identiques.