Bus Nono

Leçon 1.1 : Fondements des méthodes de descente

Objectif

Comprendre comment fonctionnent les algorithmes de descente pour minimiser une fonction sans contraintes.

---

1. Structure générale d’un algorithme de descente

1.1.1 Principe itératif

Idée générale

On veut résoudre un problème de la forme :

min f(x), avec x appartenant à R^n

On ne connaît pas directement la solution. On va donc l’approcher progressivement.

Principe

On construit une suite : x0, x1, x2, ...

avec la règle :

x(k+1) = x(k) + alpha(k) * d(k)

• x(k) : point courant
• d(k) : direction de descente
• alpha(k) : pas

Intuition

À chaque étape, on choisit une direction, on avance, et on cherche à diminuer la fonction.

Exemple corrigé

Soit f(x) = x^2, avec x0 = 2

f'(x) = 2x

d0 = -2(2) = -4

x1 = 2 + 0.1 * (-4) = 1.6

f(2) = 4 et f(1.6) = 2.56

La fonction diminue.

---

1.1.2 Choix de la direction de descente

Définition

Une direction d(k) est de descente si :

gradient f(x(k))^T * d(k) < 0

Direction classique

d(k) = - gradient f(x(k))

Interprétation

Le gradient indique la direction de plus forte augmentation. Donc son opposé donne la plus forte descente.

Exemple corrigé

f(x,y) = x^2 + y^2

gradient f = (2x, 2y)

Au point (1,1) : gradient = (2,2)

Direction : d = (-2,-2)

Produit : 2*(-2) + 2*(-2) = -8 < 0

C’est une direction de descente.

---

1.1.3 Détermination du pas

Problème

Quelle distance parcourir dans la direction choisie ?

Solution

Choisir alpha(k) > 0

Recherche linéaire

On minimise :

phi(alpha) = f(x(k) + alpha * d(k))

Exemple corrigé

f(x) = x^2, x0 = 2, d = -4

phi(alpha) = (2 - 4alpha)^2

phi'(alpha) = -8(2 - 4alpha)

phi'(alpha) = 0 donne alpha = 0.5

x1 = 2 - 4 * 0.5 = 0

Minimum atteint en une seule itération.

---

1.1.4 Critères d’arrêt

Pourquoi arrêter ?

On ne peut pas itérer indéfiniment.

Critères

• ||gradient f(x(k))|| < epsilon
• ||x(k+1) - x(k)|| < epsilon
• Nombre maximal d’itérations atteint

Exemple

Si ||gradient|| = 0.0001 et epsilon = 0.001, alors on arrête.

---

1.1.5 Conditions d’optimalité du premier ordre

Résultat

Si x* est un minimum local :

gradient f(x*) = 0

Attention

Ce n’est pas toujours un minimum : cela peut être un maximum ou un point selle.

Exemple

f(x) = x^3

f'(x) = 3x^2

f'(0) = 0 mais ce n’est pas un minimum.

---

2. Conditions de Wolfe pour la recherche linéaire

1.2.1 Condition d’Armijo

f(x(k) + alpha * d(k)) ≤ f(x(k)) + beta1 * alpha * gradient f(x(k))^T * d(k)

avec 0 < beta1 < 1

On impose une diminution suffisante.

---

1.2.2 Condition de Wolfe

gradient f(x(k) + alpha * d(k))^T * d(k) ≥ beta2 * gradient f(x(k))^T * d(k)

avec beta1 < beta2 < 1

On évite un pas trop petit.

---

1.2.3 Algorithme de recherche linéaire

1. Choisir alpha
2. Tester Armijo
3. Tester Wolfe
4. Ajuster alpha

---

1.2.4 Choix des paramètres

beta1 = 0.0001 et beta2 = 0.9

---

Exercices corrigés

Exercice 1

f(x) = x^2 + 4x

1. f'(x) = 2x + 4
2. d = -(2x + 4)
3. x1 = 1 - 0.1 * 6 = 0.4
4. f(1) = 5 et f(0.4) = 1.76
5. Minimum : x = -2

---

Exercice 2

f(x,y) = x^2 + y^2

1. gradient = (2x,2y)
2. au point (2,1) : (4,2)
3. produit = -20 < 0
4. (2,1) + 0.5(-4,-2) = (0,0)
5. norme = racine(20)

---

Exercice 3

f(x) = x^3

1. f'(x) = 3x^2
2. x = 0
3. point selle
4. d = -3
5. x1 = 0.7

---

Exercices d’entraînement

Exercice A

• f(x) = x^2 - 6x
• Calculer le gradient
• Donner la direction
• Faire une itération
• Trouver le minimum
• Vérifier l’arrêt

Exercice B

• f(x,y) = x^2 + 3y^2
• Calculer le gradient
• Direction en (1,2)
• Vérifier descente
• Faire une itération
• Norme du gradient

---

Conclusion

Cette leçon introduit les bases des méthodes de descente :

• structure d’un algorithme
• rôle du gradient
• choix du pas
• conditions d’arrêt
• conditions de Wolfe