Algorithme de Newton et plus forte pente
Exercice
1
Soit 𝑓 (𝑥, 𝑦, 𝑧) = 2 (𝑥 2 + 2𝑦 2 + 3𝑧 2 ) est (𝑋 𝑘 )𝑘 la suite engendrée par l’algorithme de plus forte
1
pente (gradient à pas optimal) pour minimiser la fonction 𝑓 sur ℝ3 avec 𝑋 0 = (1,0, 3)𝑡
1/ Calculer le pas de déplacement optimal en fonction des coordonnées du point 𝑋 𝑘 et calculer 𝑋1 .
1 (−1) 𝑘 𝑡
2/ Montrer par récurrence que 𝑋 𝑘 = 2𝑘 (1,0, 3
) ∀𝑘 ∈ ℕ … (1)
3/La suite obtenue est elle convergente ? Justifier.
4/Quel est le nombre d’itérations à effectuer pour que 𝑋 𝑘 soit une approximation de la solution
optimale du minimum global de 𝑓 sur ℝ3 à 10−2 près ?
Solution :
1/𝑋 𝑘+1 = 𝑋 𝑘 + 𝜆𝑘 𝑑𝑘 où 𝜆𝑘 = 𝐴𝑟𝑔𝑚𝑖𝑛𝑓(𝑋 𝑘 + 𝜆𝑑𝑘 ); 𝜆 ≥ 0
𝑋 𝑘 + 𝜆𝑑𝑘 = (𝑥𝑘 , 𝑦𝑘 , 𝑧𝑘 ) − 𝜆(𝑥𝑘 , 2𝑦𝑘 , 3𝑧𝑘 )
1
𝑓(𝑋 𝑘 + 𝜆𝑑𝑘 ) = ((1 − 𝜆)2 𝑥𝑘2 + 2(1 − 2𝜆)2 𝑦𝑘2 + 3(1 − 3𝜆)2 𝑧𝑘2 ) = 𝑔(𝜆)
2
𝑔′ (𝜆) = −(1 − 𝜆)𝑥𝑘2 − 4(1 − 2𝜆)𝑦𝑘2 − 9(1 − 3𝜆)𝑧𝑘2
𝑥 2+4𝑦 2 +9𝑧 2
Le point stationnaire de la fonction 𝑔(𝜆) est 𝜆𝑘 = 𝑥 2𝑘+8𝑦2𝑘+27𝑧𝑘2 et comme 𝑔′′ (𝜆) = 𝑥𝑘2 + 8𝑦𝑘2 +
𝑘 𝑘 𝑘
27𝑧𝑘2 ≥ 0 donc 𝜆𝑘 est bien 𝐴 𝑟𝑔𝑚𝑖𝑛𝑓(𝑋 𝑘 + 𝜆𝑑𝑘 ); 𝜆 ≥ 0.
1 −1 𝑡
𝑋1 = 𝑋 0 + 𝜆0 𝑑0 = ( , 0, )
2 6
2/(1) est vérifiée pour 𝑘 = 0
1 (−1)𝑘 𝑡
On suppose que 𝑋 𝑘 = 2𝑘 (1,0, 3
)
𝑥 2+4𝑦 2 +9𝑧 2 1
𝑋 𝑘+1 = 𝑋 𝑘 − 𝜆𝑘 ∇𝑓(𝑋 𝑘 ) où 𝜆𝑘 = 𝑥 2𝑘+8𝑦2𝑘+27𝑧𝑘2 = 2
𝑘 𝑘 𝑘
1 (−1)𝑘 𝑡 1 1 (−1)𝑘 𝑡 1 (−1)𝑘+1 𝑡
= 2𝑘 (1,0, 3
) − 2 (2𝑘 , 0, 2𝑘
) = 2𝑘+1 (1,0, 3
)
1 1 1
3/ 𝑓 (𝑥, 𝑦, 𝑧) = 2 (𝑥 2 + 2𝑦 2 + 3𝑧 2 ) ≥ 2 (𝑥 2 + 𝑦 2 + 𝑧 2 ) = 2 ‖(𝑥, 𝑦, 𝑧)‖22 → +∞
Lorsque‖(𝑥, 𝑦, 𝑧)‖ → ∞
f est une fonction continue et coercive sur ℝ3 donc l’algorithme converge vers un point
stationnaire et comme f est convexe ce point est le minimum de f
D’autre part on remarque que lim𝑘→∞ 𝑋 𝑘 = 0ℝ3 = 𝑋 ∗
[Tapez un texte] Page 1
Algorithme de Newton et plus forte pente
1 1 √10
4/ ‖𝑋 𝑘 − 𝑋 ∗ ‖2 ≤ 10−2 ⟺ √2𝑘 + 9∗2𝑘 ≤ 10−2 ⟺ 𝑘 ≥ 100 3
Il suffit de prendre 𝑘 = 7.
Méthode de Newton
On suppose que 𝑓 ∈ 𝐶 2 (ℝ𝑛 ). 𝑓(𝑥) est remplacée par son approximation quadratique au voisinage
de 𝑥 𝑘 :
1 𝑡
𝑓 (𝑥) ≅ 𝑞(𝑥) = 𝑓(𝑥 𝑘 ) + ∇𝑡 𝑓(𝑥 𝑘 )(𝑥 − 𝑥 𝑘 ) + 2 (𝑥 − 𝑥 𝑘 ) 𝐻𝑓 (𝑥 𝑘 )(𝑥 − 𝑥 𝑘 )
En supposant que 𝐻𝑓 (𝑥 𝑘 ) est une matrice définie positive, Prendre 𝑥 𝑘+1 = 𝐴𝑟𝑔𝑚𝑖𝑛𝑞(𝑥)
Donc 𝐴𝑟𝑔𝑚𝑖𝑛𝑞(𝑥) est le vecteur vérifiant ∇𝑞(𝑥) = ∇𝑓(𝑥 𝑘 ) + 𝐻𝑓 (𝑥 𝑘 )(𝑥 − 𝑥 𝑘 ) = 0
𝑥 𝑘+1 = 𝑥 𝑘 − (𝐻𝑓 (𝑥 𝑘 )−1 ∇𝑓(𝑥 𝑘 )
Remarque
1/On remarque que si 𝐻𝑓 (𝑥 𝑘 ) est une matrice définie positive alors la méthode de Newton est bien
une méthode de descente à pas fixe où 𝜆𝑘 = 1 et 𝑑𝑘 = −(𝐻𝑓 (𝑥 𝑘 ))−1 ∇𝑓(𝑥 𝑘 ).
2/ les applique les mêmes tests d’arrêt que ceux de la méthode de plus forte pente.
Exemple :
Soit 𝑓 (𝑥, 𝑦, 𝑧) = (𝑥 − 𝑦 + 𝑧)2 + (−𝑥 + 𝑦 + 𝑧)2 + (𝑥 + 𝑦 − 𝑧)2 + 2𝑥 − 3𝑦
1 1
Faire 2 itérations d’algorithme de Newton démarrant de 𝑋 0 = ( , 1, )𝑡
2 2
Solution
6 −2 −2 2
1
𝑓 (𝑥, 𝑦, 𝑧) = 𝑋 𝑡 𝐴𝑋 + 𝑏𝑡 𝑋 où 𝐴 = (−2 6 −2) et 𝑏 = (−3)
2
−2 −2 6 0
Itération1 :
∇𝑓 (𝑥 0 ) = (2,1,0)𝑡 ≠ 0ℝ3
𝑥 𝑘+1 = 𝑥 𝑘 − (𝐻𝑓 (𝑥 𝑘 )−1 ∇𝑓(𝑥 𝑘 ) = 𝑥 𝑘 − (𝐴)−1 ∇𝑓(𝑥 𝑘 )
1 1 1 1
1
4 8 8
−8
2 2
1 1 1 1
𝑥1 = 𝑥 0 − (𝐴)−1 ∇𝑓(𝑥 0 ) = (1) − 8 4 8
(1) = 2
1
1 1 1 0 1
2
(8 8 4) ( 8 )
∇𝑓 (𝑥1 ) = (0,0,0)𝑡
[Tapez un texte] Page 2
Algorithme de Newton et plus forte pente
Et comme A est définie positive donc f est strictement convexe sur ℝ3 alors on déduit que 𝑥1 est le
point du minimum global de f sur ℝ3 .
Remarque :
1/ inconvénients : calcul à chaque itération de ∇𝑓(𝑥 𝑘 ), 𝐻𝑓 (𝑥 𝑘 ), (𝐻𝑓 (𝑥 𝑘 ))−1
2/ Avantage :
1
Appliquée à une forme quadratique 𝑓(𝑥) = 𝑥 𝑡 𝐴𝑥 + 𝑏𝑡 𝑥 + 𝑐 strictement convexe, l’algorithme
2
converge en une seule itération.
Preuve :
La solution optimale vérifie le système 𝐴𝑥 ∗ + 𝑏 = 0 ⟺ 𝑥 ∗ = −𝐴−1 𝑏
Soit 𝑥 0 ∈ ℝ𝑛 ; ∇𝑓(𝑥 0 ) = 𝐴𝑥 0 + 𝑏
𝑥1 = 𝑥 0 − (𝐴)−1 (𝐴𝑥 0 + 𝑏) = −𝐴−1 𝑏 = 𝑥 ∗ .
[Tapez un texte] Page 3