Méthode de gradient

Leçon 1.2 : Méthode du gradient (plus forte descente)

Objectif

Maîtriser la méthode du gradient et comprendre ses propriétés de convergence.

---

1. Direction de plus forte descente

2.1.1 Définition et propriétés

Définition

La direction de plus forte descente est donnée par :

d_k = − ∇f(x_k)

Propriété fondamentale

Cette direction minimise localement la variation de la fonction.

Justification

On cherche à minimiser :

∇f(x)^T d sous la contrainte ||d|| = 1

La solution est :

d = − ∇f(x) / ||∇f(x)||

Exemple corrigé

Soit f(x,y) = x² + y²

∇f(x,y) = (2x, 2y)

Au point (1,2) :

∇f = (2,4)

d = (−2, −4)

---

2.1.2 Relation avec la norme du gradient

La vitesse de décroissance de la fonction est proportionnelle à :

||∇f(x_k)||

Plus le gradient est grand, plus la descente est rapide.

Exemple

Si ||∇f|| = 10 → descente rapide

Si ||∇f|| = 0.001 → descente lente

---

2.1.3 Interprétation géométrique

Le gradient est orthogonal aux courbes de niveau.

La direction −∇f est la direction de descente la plus rapide.

Image mentale

Comme une balle qui descend la pente la plus raide.

---

2. Convergence de la méthode du gradient

2.2.1 Convergence linéaire

La méthode du gradient converge en général de manière linéaire :

||x_k − x*|| ≤ C · q^k

avec :

• 0 < q < 1
• C constante

Interprétation

L’erreur diminue proportionnellement à chaque itération.

---

2.2.2 Rôle du conditionnement

Le conditionnement influence fortement la convergence.

Pour une fonction quadratique :

f(x) = 1/2 · x^T A x − b^Tx

Le taux dépend du nombre de condition :

κ(A) = λ_max / λ_min

Interprétation

• κ petit → convergence rapide
• κ grand → convergence lente

---

2.2.3 Lenteur dans les vallées étroites

Dans certaines fonctions, les courbes de niveau sont très allongées.

La méthode du gradient oscille :

• elle zigzague
• elle avance lentement

Exemple

f(x,y) = x² + 100y²

Les directions changent fortement à chaque itération.

---

2.2.4 Analyse sur les fonctions quadratiques

Soit :

f(x) = 1/2 · x^T A x − b^Tx

La solution exacte vérifie :

A x = b

La méthode du gradient devient :

x_k+1 = x_k − α_k (A x_k − b)

Exemple corrigé

Soit f(x) = x²

Alors :

∇f(x) = 2x

Avec α = 0.5 :

x_k+1 = x_k − 0.5 · 2x_k = 0

Convergence en une étape.

---

3. Implémentation pratique

2.3.1 Structure algorithmique

Initialiser x0

Pour k = 0,1,2,...

    Calculer le gradient ∇f(xk)

    Si ||∇f(xk)|| < ε alors arrêter

    Choisir αk

    xk+1 = xk − αk ∇f(xk)

Fin

---

2.3.2 Stockage de l’historique

On peut stocker :

• les points x_k
• les valeurs f(x_k)
• les normes ||∇f(x_k)||

Permet d’analyser la convergence.

---

2.3.3 Visualisation des itérés

On peut représenter :

• les trajectoires
• les courbes de niveau

Permet de comprendre le comportement de l’algorithme.

---

Exercices corrigés

Exercice 1

f(x) = x²

1. ∇f(x) = 2x
2. d = −2x
3. Avec x₀ = 4 et α = 0.25 :

x₁ = 4 − 0.25 × 8 = 2

4. f(4) = 16, f(2) = 4
5. Minimum en x = 0

---

Exercice 2

f(x,y) = x² + y²

1. ∇f = (2x,2y)
2. Au point (1,1) → (2,2)
3. d = (−2,−2)
4. Avec α = 0.5 :

(1,1) → (0,0)

5. ||∇f|| = √(8)

---

Exercice 3

f(x,y) = x² + 4y²

1. ∇f = (2x,8y)
2. Au point (1,1) → (2,8)
3. d = (−2,−8)
4. Avec α = 0.1 :

x₁ = (0.8, 0.2)

5. La convergence est lente (vallée étroite)

---

Exercices d’entraînement

Exercice A

• f(x) = x² + 2x
• Calculer le gradient
• Donner la direction
• Faire une itération
• Trouver le minimum
• Étudier la convergence

Exercice B

• f(x,y) = x² + 5y²
• Calculer le gradient
• Direction en (2,1)
• Faire une itération
• Calculer ||∇f||
• Interpréter la convergence

---

Conclusion

La méthode du gradient est simple mais :

• facile à implémenter
• peut être lente
• dépend du conditionnement

Elle constitue la base de nombreuses méthodes en optimisation et en apprentissage automatique.