Exercices Corrigés : Optimisation Numérique (Gradient et Newton)
Bienvenue dans cette série d'exercices dédiée à l'optimisation numérique. Tu vas y explorer les fondements des méthodes du gradient et de Newton, deux algorithmes puissants pour trouver les minima (ou maxima) de fonctions. Ces méthodes sont au cœur de nombreux domaines, de l'apprentissage automatique à la recherche opérationnelle. Nous allons les aborder de manière progressive avec 8 exercices et leurs corrections détaillées.
Compétences travaillées
- Compréhension des principes des méthodes du gradient et de Newton.
- Calcul du gradient et de la matrice Hessienne d'une fonction.
- Mise en œuvre des algorithmes de mise à jour itérative.
- Analyse de la convergence et comparaison des méthodes.
- Application à des fonctions d'optimisation concrètes.
Erreurs fréquentes à éviter
- Erreurs dans le calcul des dérivées partielles (gradient) ou des dérivées secondes (Hessienne).
- Mauvaise compréhension de la direction de descente (gradient ascendant vs descendant).
- Choix d'un pas (learning rate) trop grand ou trop petit dans la méthode du gradient.
- Gestion des singularités de la matrice Hessienne dans la méthode de Newton.
- Arrêt prématuré de l'itération sans atteindre la précision souhaitée.
Exercice 1 : Calcul du Gradient
Exercice 1 : Soit la fonction $f(x, y) = x^2 + y^2$. Calcule son gradient.
Correction :
Le gradient d'une fonction $f(x, y)$ est un vecteur dont les composantes sont les dérivées partielles par rapport à chaque variable :
$$ \nabla f(x, y) = \begin{pmatrix} \frac{\partial f}{\partial x} \\ \frac{\partial f}{\partial y} \end{pmatrix} $$Étape 1 : Calculer la dérivée partielle de $f$ par rapport à $x$.
$\frac{\partial f}{\partial x} = \frac{\partial}{\partial x}(x^2 + y^2) = 2x$.
Étape 2 : Calculer la dérivée partielle de $f$ par rapport à $y$.
$\frac{\partial f}{\partial y} = \frac{\partial}{\partial y}(x^2 + y^2) = 2y$.
Étape 3 : Assembler les composantes pour former le gradient.
Résultat :
$$ \nabla f(x, y) = \begin{pmatrix} 2x \\ 2y \end{pmatrix} $$Exercice 2 : Calcul du Gradient d'une Fonction Plus Complexe
Exercice 2 : Soit la fonction $f(x, y) = x^3 - 3xy + y^2 + 5$. Calcule son gradient.
Correction :
On calcule les dérivées partielles par rapport à $x$ et $y$.
Étape 1 : Dérivée partielle par rapport à $x$.
$\frac{\partial f}{\partial x} = \frac{\partial}{\partial x}(x^3 - 3xy + y^2 + 5) = 3x^2 - 3y$.
Étape 2 : Dérivée partielle par rapport à $y$.
$\frac{\partial f}{\partial y} = \frac{\partial}{\partial y}(x^3 - 3xy + y^2 + 5) = -3x + 2y$.
Étape 3 : Assembler le gradient.
Résultat :
$$ \nabla f(x, y) = \begin{pmatrix} 3x^2 - 3y \\ -3x + 2y \end{pmatrix} $$Exercice 3 : Méthode du Gradient - Première Itération
Exercice 3 : Utilise la méthode du gradient pour trouver le minimum de la fonction $f(x, y) = x^2 + y^2$. Commence avec le point initial $P_0 = (2, 1)$ et un pas d'apprentissage $\alpha = 0.1$. Calcule la première itération $P_1$.
Correction :
La formule de mise à jour pour la méthode du gradient est : $P_{k+1} = P_k - \alpha \nabla f(P_k)$.
Nous avons $f(x, y) = x^2 + y^2$, dont le gradient est $\nabla f(x, y) = \begin{pmatrix} 2x \\ 2y \end{pmatrix}$ (calculé à l'exercice 1).
Le point initial est $P_0 = \begin{pmatrix} 2 \\ 1 \end{pmatrix}$. Le pas d'apprentissage est $\alpha = 0.1$.
Étape 1 : Calculer le gradient au point $P_0$.
$\nabla f(2, 1) = \begin{pmatrix} 2(2) \\ 2(1) \end{pmatrix} = \begin{pmatrix} 4 \\ 2 \end{pmatrix}$.
Étape 2 : Appliquer la formule de mise à jour pour $P_1$.
$P_1 = P_0 - \alpha \nabla f(P_0)$
$P_1 = \begin{pmatrix} 2 \\ 1 \end{pmatrix} - 0.1 \begin{pmatrix} 4 \\ 2 \end{pmatrix}$
$P_1 = \begin{pmatrix} 2 \\ 1 \end{pmatrix} - \begin{pmatrix} 0.4 \\ 0.2 \end{pmatrix}$
$P_1 = \begin{pmatrix} 1.6 \\ 0.8 \end{pmatrix}$.
Résultat :
$$ P_1 = \begin{pmatrix} 1.6 \\ 0.8 \end{pmatrix} $$Point méthode : Le gradient pointe dans la direction de la plus forte augmentation de la fonction. Pour minimiser, on se déplace dans la direction opposée au gradient.
Exercice 4 : Méthode du Gradient - Deuxième Itération
Exercice 4 : En utilisant le point $P_1 = (1.6, 0.8)$ obtenu à l'exercice 3, et toujours avec $\alpha = 0.1$, calcule la deuxième itération $P_2$ pour minimiser $f(x, y) = x^2 + y^2$.
Correction :
On applique à nouveau la formule $P_{k+1} = P_k - \alpha \nabla f(P_k)$ avec $P_1 = \begin{pmatrix} 1.6 \\ 0.8 \end{pmatrix}$ et $\alpha = 0.1$. Le gradient reste $\nabla f(x, y) = \begin{pmatrix} 2x \\ 2y \end{pmatrix}$.
Étape 1 : Calculer le gradient au point $P_1$.
$\nabla f(1.6, 0.8) = \begin{pmatrix} 2(1.6) \\ 2(0.8) \end{pmatrix} = \begin{pmatrix} 3.2 \\ 1.6 \end{pmatrix}$.
Étape 2 : Appliquer la formule de mise à jour pour $P_2$.
$P_2 = P_1 - \alpha \nabla f(P_1)$
$P_2 = \begin{pmatrix} 1.6 \\ 0.8 \end{pmatrix} - 0.1 \begin{pmatrix} 3.2 \\ 1.6 \end{pmatrix}$
$P_2 = \begin{pmatrix} 1.6 \\ 0.8 \end{pmatrix} - \begin{pmatrix} 0.32 \\ 0.16 \end{pmatrix}$
$P_2 = \begin{pmatrix} 1.28 \\ 0.64 \end{pmatrix}$.
Résultat :
$$ P_2 = \begin{pmatrix} 1.28 \\ 0.64 \end{pmatrix} $$Astuce : On observe que les composantes de $P_2$ sont $\alpha=0.1$ plus petites que celles de $P_1$. Ce phénomène, où le pas est fixe, est caractéristique de la méthode du gradient à pas fixe. Dans la pratique, un pas d'apprentissage optimal est souvent recherché à chaque étape.
Exercice 5 : Calcul de la Matrice Hessienne
Exercice 5 : Soit la fonction $f(x, y) = x^2 + y^2$. Calcule sa matrice Hessienne.
Correction :
La matrice Hessienne $H$ d'une fonction $f(x, y)$ est une matrice carrée de taille 2x2 dont les éléments sont les dérivées secondes :
$$ H f(x, y) = \begin{pmatrix} \frac{\partial^2 f}{\partial x^2} & \frac{\partial^2 f}{\partial x \partial y} \\ \frac{\partial^2 f}{\partial y \partial x} & \frac{\partial^2 f}{\partial y^2} \end{pmatrix} $$Nous avons déjà calculé $\nabla f(x, y) = \begin{pmatrix} 2x \\ 2y \end{pmatrix}$ à l'exercice 1.
Étape 1 : Calculer $\frac{\partial^2 f}{\partial x^2}$.
$\frac{\partial}{\partial x}\left(\frac{\partial f}{\partial x}\right) = \frac{\partial}{\partial x}(2x) = 2$.
Étape 2 : Calculer $\frac{\partial^2 f}{\partial x \partial y}$.
$\frac{\partial}{\partial y}\left(\frac{\partial f}{\partial x}\right) = \frac{\partial}{\partial y}(2x) = 0$.
Étape 3 : Calculer $\frac{\partial^2 f}{\partial y \partial x}$.
$\frac{\partial}{\partial x}\left(\frac{\partial f}{\partial y}\right) = \frac{\partial}{\partial x}(2y) = 0$. (Note : par le théorème de Schwarz, cette dérivée est égale à la précédente pour les fonctions suffisamment régulières).
Étape 4 : Calculer $\frac{\partial^2 f}{\partial y^2}$.
$\frac{\partial}{\partial y}\left(\frac{\partial f}{\partial y}\right) = \frac{\partial}{\partial y}(2y) = 2$.
Étape 5 : Assembler la matrice Hessienne.
Résultat :
$$ H f(x, y) = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} $$Exercice 6 : Méthode de Newton - Première Itération
Exercice 6 : Utilise la méthode de Newton pour trouver le minimum de la fonction $f(x, y) = x^2 + y^2$. Commence avec le point initial $P_0 = (2, 1)$. Calcule la première itération $P_1$.
Correction :
La formule de mise à jour pour la méthode de Newton est : $P_{k+1} = P_k - (H f(P_k))^{-1} \nabla f(P_k)$.
Nous avons $f(x, y) = x^2 + y^2$. À l'exercice 1, nous avons trouvé $\nabla f(x, y) = \begin{pmatrix} 2x \\ 2y \end{pmatrix}$. À l'exercice 5, nous avons trouvé $H f(x, y) = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}$.
Le point initial est $P_0 = \begin{pmatrix} 2 \\ 1 \end{pmatrix}$.
Étape 1 : Calculer le gradient au point $P_0$.
$\nabla f(2, 1) = \begin{pmatrix} 2(2) \\ 2(1) \end{pmatrix} = \begin{pmatrix} 4 \\ 2 \end{pmatrix}$.
Étape 2 : Calculer la matrice Hessienne au point $P_0$.
$H f(2, 1) = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}$.
Étape 3 : Calculer l'inverse de la matrice Hessienne.
$(H f(2, 1))^{-1} = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}^{-1} = \begin{pmatrix} 1/2 & 0 \\ 0 & 1/2 \end{pmatrix}$.
Étape 4 : Appliquer la formule de mise à jour pour $P_1$.
$P_1 = P_0 - (H f(P_0))^{-1} \nabla f(P_0)$
$P_1 = \begin{pmatrix} 2 \\ 1 \end{pmatrix} - \begin{pmatrix} 1/2 & 0 \\ 0 & 1/2 \end{pmatrix} \begin{pmatrix} 4 \\ 2 \end{pmatrix}$
$P_1 = \begin{pmatrix} 2 \\ 1 \end{pmatrix} - \begin{pmatrix} (1/2)4 + 02 \\ 0*4 + (1/2)*2 \end{pmatrix}$
$P_1 = \begin{pmatrix} 2 \\ 1 \end{pmatrix} - \begin{pmatrix} 2 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$.
Résultat :
$$ P_1 = \begin{pmatrix} 0 \\ 0 \end{pmatrix} $$Astuce : Pour cette fonction quadratique simple, la méthode de Newton converge en une seule étape car le minimum est atteint directement. L'Hessienne est constante et l'application de la formule de Newton amène exactement au minimum.
Exercice 7 : Comparaison Gradient vs Newton
Exercice 7 : Soit la fonction $f(x) = x^4 - 3x^2 + 2$. Nous voulons trouver un minimum local de cette fonction.
a) Calcule le gradient (dérivée première) et l'Hessienne (dérivée seconde) de $f(x)$.
b) Appliqu'une itération de la méthode du gradient avec un pas d'apprentissage fixe $\alpha = 0.1$, en partant de $x_0 = 1.5$. Calcule $x_1$.
c) Appliqu'une itération de la méthode de Newton, en partant de $x_0 = 1.5$. Calcule $x_1$.
d) Compare les résultats des deux méthodes.
Correction :
a) Gradient et Hessienne :
Gradient : $f'(x) = 4x^3 - 6x$.
Hessienne : $f''(x) = 12x^2 - 6$.
b) Méthode du Gradient :
Point initial $x_0 = 1.5$. Pas $\alpha = 0.1$.
Gradient en $x_0$: $f'(1.5) = 4(1.5)^3 - 6(1.5) = 4(3.375) - 9 = 13.5 - 9 = 4.5$.
Mise à jour : $x_1 = x_0 - \alpha f'(x_0) = 1.5 - 0.1(4.5) = 1.5 - 0.45 = 1.05$.
c) Méthode de Newton :
Point initial $x_0 = 1.5$.
Gradient en $x_0$: $f'(1.5) = 4.5$ (calculé ci-dessus).
Hessienne en $x_0$: $f''(1.5) = 12(1.5)^2 - 6 = 12(2.25) - 6 = 27 - 6 = 21$.
Mise à jour : $x_1 = x_0 - \frac{f'(x_0)}{f''(x_0)} = 1.5 - \frac{4.5}{21} \approx 1.5 - 0.2143 = 1.2857$.
d) Comparaison :
Après une itération :
- Gradient : $x_1 = 1.05$.
- Newton : $x_1 \approx 1.2857$.
La fonction $f(x) = x^4 - 3x^2 + 2$ a des minima locaux en $x = \pm \sqrt{3/2} \approx \pm 1.2247$. Les maxima locaux sont en $x=0$. Notre point de départ $x_0=1.5$ est plus proche du minimum positif.
La méthode de Newton a rapproché la valeur de $x$ de manière plus significative vers le minimum que la méthode du gradient avec un pas fixe, car elle utilise l'information de la courbure (Hessienne).
Résultat :
a) $f'(x) = 4x^3 - 6x$, $f''(x) = 12x^2 - 6$.
b) $x_1 = 1.05$ (Gradient).
c) $x_1 \approx 1.2857$ (Newton).
d) La méthode de Newton a effectué un pas plus important et plus proche du minimum local à partir du point initial donné.
Point méthode : La méthode de Newton converge plus rapidement (quadratiquement) que la méthode du gradient (linéairement) lorsqu'elle est applicable, mais elle est plus coûteuse par itération (calcul et inversion de la Hessienne) et peut échouer si l'Hessienne est singulière ou mal conditionnée.
Exercice 8 : Problème d'un pas d'apprentissage inadéquat
Exercice 8 : Soit la fonction $g(x) = x^2$. Nous voulons trouver son minimum en partant de $x_0 = 1$.
a) Calcule le gradient de $g(x)$ et sa Hessienne.
b) Applique la méthode du gradient avec un pas d'apprentissage $\alpha = 1.1$. Calcule $x_1$. Qu'observes-tu ?
c) Applique la méthode du gradient avec un pas d'apprentissage $\alpha = 0.9$. Calcule $x_1$. Qu'observes-tu ?
d) Applique la méthode de Newton. Calcule $x_1$.
Correction :
a) Gradient et Hessienne :
Gradient : $g'(x) = 2x$.
Hessienne : $g''(x) = 2$.
b) Gradient avec $\alpha = 1.1$ :
Point initial $x_0 = 1$.
Gradient en $x_0$: $g'(1) = 2(1) = 2$.
Mise à jour : $x_1 = x_0 - \alpha g'(x_0) = 1 - 1.1(2) = 1 - 2.2 = -1.2$.
Observation : Le point $x_1$ s'est éloigné du minimum ($x=0$). Le pas d'apprentissage est trop grand.
c) Gradient avec $\alpha = 0.9$ :
Point initial $x_0 = 1$.
Gradient en $x_0$: $g'(1) = 2$.
Mise à jour : $x_1 = x_0 - \alpha g'(x_0) = 1 - 0.9(2) = 1 - 1.8 = -0.8$.
Observation : Le point $x_1$ est plus proche de $0$ que $x_0$. Le pas d'apprentissage est raisonnable.
d) Méthode de Newton :
Point initial $x_0 = 1$.
Gradient en $x_0$: $g'(1) = 2$.
Hessienne en $x_0$: $g''(1) = 2$.
Mise à jour : $x_1 = x_0 - \frac{g'(x_0)}{g''(x_0)} = 1 - \frac{2}{2} = 1 - 1 = 0$.
Observation : La méthode de Newton a atteint le minimum exact en une seule étape.
Résultat :
b) Avec $\alpha = 1.1$, $x_1 = -1.2$. Le pas est trop grand, l'algorithme s'éloigne du minimum.
c) Avec $\alpha = 0.9$, $x_1 = -0.8$. Le pas est approprié, l'algorithme se rapproche du minimum.
d) Avec Newton, $x_1 = 0$. Le minimum est atteint en une étape.
Point méthode : Le choix du pas d'apprentissage (learning rate) dans la méthode du gradient est crucial. Un pas trop grand peut entraîner une divergence ou une oscillation autour du minimum. La méthode de Newton, en utilisant la courbure, choisit intrinsèquement un pas qui est souvent plus efficace pour les fonctions bien conditionnées.
Comment ORBITECH Peut T'aider
ORBITECH AI Academy met à ta disposition des outils concrets pour réviser plus efficacement et progresser à ton rythme.
- Générateur de Quiz : crée des quiz personnalisés pour tester tes connaissances et identifier tes lacunes.
- Générateur d'Exercices : crée des exercices d'entraînement adaptés à ton niveau avec corrections détaillées.
- Calculatrice Scientifique : effectue des calculs avancés avec historique et graphiques de fonctions.
- Générateur de Résumés : transforme tes cours en fiches de révision claires et structurées.
Tous ces outils sont disponibles sur ta plateforme ORBITECH. Connecte-toi et explore ceux qui correspondent le mieux à tes besoins !
Commencer gratuitement