Descente de gradients et variantes

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.

\DeclareMathOperator*{\argmin}{argmin}

    \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