Descente de gradient projeté

Auteur·rice

Joseph Salmon, Tanguy Lefort, Amélie Vernay

Objectifs de ce TP

Comment optimiser une fonction sous contraintes? Application au problème des moindres carrés linéaires avec données réelles. Application du théorème de projection sur un ensemble convexe fermé.

Dans ce TP, nous allons utiliser la méthode de descente de gradient pour trouver un minimiseur d’une fonction f:\mathbb{R}^d\rightarrow\mathbb{R} pour d\geq 2 en posant des contraintes sur f ou sur l’ensemble \mathcal{C} des solutions du problème.

Algorithme de la descente de gradient projeté

Dans cette partie, on suppose que l’on a une fonction f, et on va introduire la descente de gradient projeté (🇬🇧 projected gradient descent) avec l’ensemble de contraintes convexe fermé \mathcal{C}. On note \Pi_{\mathcal{C}} la projection convexe, i.e. LA¹ fonction convexe qui envoie un élément dans l’ensemble convexe fermé \mathcal{C}.

¹ théorème de projection sur un convexe fermé

    \begin{algorithm}
    \caption{Descente de gradient projeté (à pas fixe)}
    \begin{algorithmic}
    \INPUT $\nabla f, \Pi_{\mathcal{C}}, 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 \Pi_{\mathcal{C}}\big(x - \gamma g\big)$
    \COMMENT{Pas dans la direction opposée au gradient}
    \ENDIF
    \ENDFOR
    \OUTPUT $x$
    \end{algorithmic}
    \end{algorithm}

Dans la suite de cette partie, on travaillera avec la fonction f_{test} définie ainsi:

\begin{align*} f_{test}:\quad \mathbb{R}^2 &\to \mathbb{R}^2\\ \begin{pmatrix} x_1 \\ x_2 \\\end{pmatrix} & \mapsto (x_1 - 1)^2 + 3(x_2 + 1)^2 \end{align*}

Question 1: Minimiser avec ou sans contraintes

Quel est le minimum global de f_{test} ? (on pourra utiliser la descente de gradient du TP précédent). Utiliser la méthode minimize de la librairie scipy pour trouver le minimum de f_{test} sur \mathbb{R}^2_+. Pour cela, utiliser l’argument bounds et une méthode d’optimisation qui supporte cette contrainte, par exemple method="TNC". Voir la documentation si besoin.

Question 2: Descente de gradient projeté

Implémenter la méthode de descente du gradient projeté à pas fixe en prenant comme argument une fonction de projection \Pi_{\mathcal{C}}:\mathbb{R}^d\to \mathbb{R}^d quelconque.

Question 3: Application à la contrainte de positivité

Avec l’algorithme précédent, résoudre numériquement : \begin{aligned} \min_{x\in\mathbb{R}^2}\ & f_{\text{test}}(x) \\ & \text{ s.c. } \begin{cases} x_1 \geq 0 \\ x_2 \geq 0 \end{cases} \end{aligned}

Note

Cette formulation induit la positivité des paramètres. Elle est notamment utilisée en physique quand il y a une interprétation directe comme la vitesse ou la masse d’un objet.

Question 4: Application aux projections sur les boules

Avec l’algorithme précédent, résoudre numériquement : \begin{aligned} \min_{x\in\mathbb{R}^2}\ & f_{\text{test}}(x) \\ & \text{ s.c. } \|x\|_2^2\leq 1 \end{aligned} Adapter l’exemple ci-dessus pour résoudre avec la contrainte \|x\|^2\leq 1/2. Vous pouvez dans un premier temps tester votre fonction de projection sur quelques points dont les projetés sont faciles à calculer à la main.

Pour aller plus loin

En s’aidant de l’exemple dans la documentation de la fonction minimize de scipy, résoudre le problème suivant : \begin{aligned} \min_{x\in\mathbb{R}^2}\ f_{\text{test}}(x) \text{ s.c. } \begin{cases} x_1 - 3 x_2 \geq -2 \\ x_1 + x_2 \geq 0 \end{cases} \enspace. \end{aligned} Ce problème est avec des contraintes d’inégalités linéaires. Pour le résoudre à la main, il serait possible d’utiliser la méthode des multiplicateurs de Lagrange.