6.3 Optimisation de géométrie
169
6.3.1.5 Méthode de quasi-Newton
Le principe des méthodes de quasi-Newton est d’accélérer la méthode de Newton en court-circuitant les étapes les plus coûteuses du calcul, à savoir l’assemblage de la hessienne f
(x k ) et/ou la résolution du système linéaire (6.32).
Pour cela on remplace le système (6.32)
– par le système
H k d k + g k = 0.
H k désignant une approximation de f
(x k ) facile à assembler (ce qui
évite le calcul du hessien),
– ou mieux par le système
d k+1 = −B k g k
où B k désigne une approximation de f
(x k )
−1 facile à assembler (ce qui
évite à la fois le calcul du hessien et la résolution du système linéaire).
La question qui se pose alors est de savoir comment construire à peu de
frais une approximation B k de f
(x k )
−1 . En pratique on démarre souvent
l’algorithme avec B 0 = I (mais on peut faire mieux en étudiant la spécificité
du problème étudié) et on met à jour la matrice B à chaque itération de façon
à satisfaire les deux critères suivants :
1. B k+1 est définie positive
2. B k+1 vérifie l’équation de Newton B k+1 (g k+1 − g k ) = x k+1 − x k .
Ces deux conditions laissent une vaste gamme de choix. La solution généralement retenue consiste à poser
B k+1 = B k −
s k y
T
k B k + B k y k s
T
k
(y k , s k )
+
1 +
(y k , B k · y k )
(y k , s k )
s k s
T
k
(y k , s k )
(6.33)
où s k = x k+1 − x k et y k = g k+1 − g k . La méthode ainsi obtenue est désignée
par l’acronyme BFGS (pour Broyden, Fletcher, Goldfarb, Shanno).
L’algorithme de quasi-Newton BFGS se résume donc ainsi :
1. Initialisation : choix de x 0 ∈ IR
n et de > 0 ; k = 0, B 0 = I (par exemple).
Calcul de g 0 = ∇f (x 0 )
2. Test d’arrêt : arrêt de l’algorithme si |g k | ≤ .
3. Calcul de la direction de descente : d k = −B k g k
4. Recherche linéaire le long de d k pour obtenir t k .
5. Poser x k+1 = x k + t k d k et calculer g k+1 = ∇f (x k+1 ).
6. Mise à jour de la matrice B par la formule BFGS (6.33).
7. Remplacer k par k + 1 et aller en 2.
169
6.3.1.5 Méthode de quasi-Newton
Le principe des méthodes de quasi-Newton est d’accélérer la méthode de Newton en court-circuitant les étapes les plus coûteuses du calcul, à savoir l’assemblage de la hessienne f
(x k ) et/ou la résolution du système linéaire (6.32).
Pour cela on remplace le système (6.32)
– par le système
H k d k + g k = 0.
H k désignant une approximation de f
(x k ) facile à assembler (ce qui
évite le calcul du hessien),
– ou mieux par le système
d k+1 = −B k g k
où B k désigne une approximation de f
(x k )
−1 facile à assembler (ce qui
évite à la fois le calcul du hessien et la résolution du système linéaire).
La question qui se pose alors est de savoir comment construire à peu de
frais une approximation B k de f
(x k )
−1 . En pratique on démarre souvent
l’algorithme avec B 0 = I (mais on peut faire mieux en étudiant la spécificité
du problème étudié) et on met à jour la matrice B à chaque itération de façon
à satisfaire les deux critères suivants :
1. B k+1 est définie positive
2. B k+1 vérifie l’équation de Newton B k+1 (g k+1 − g k ) = x k+1 − x k .
Ces deux conditions laissent une vaste gamme de choix. La solution généralement retenue consiste à poser
B k+1 = B k −
s k y
T
k B k + B k y k s
T
k
(y k , s k )
+
1 +
(y k , B k · y k )
(y k , s k )
s k s
T
k
(y k , s k )
(6.33)
où s k = x k+1 − x k et y k = g k+1 − g k . La méthode ainsi obtenue est désignée
par l’acronyme BFGS (pour Broyden, Fletcher, Goldfarb, Shanno).
L’algorithme de quasi-Newton BFGS se résume donc ainsi :
1. Initialisation : choix de x 0 ∈ IR
n et de > 0 ; k = 0, B 0 = I (par exemple).
Calcul de g 0 = ∇f (x 0 )
2. Test d’arrêt : arrêt de l’algorithme si |g k | ≤ .
3. Calcul de la direction de descente : d k = −B k g k
4. Recherche linéaire le long de d k pour obtenir t k .
5. Poser x k+1 = x k + t k d k et calculer g k+1 = ∇f (x k+1 ).
6. Mise à jour de la matrice B par la formule BFGS (6.33).
7. Remplacer k par k + 1 et aller en 2.