6.3 Optimisation de géométrie
167
x k+1 = x k + t k d k
(6.28)
d k = −g k + c k−1 d k−1
c k−1 =
|g k |
2
|g k−1 | 2
t k = −
(g k , d k )
(d k , Ad k )
.
Pour calculer x k+1 , il suffit donc de connaître le point x k , le gradient
g k et la dernière direction de descente d k−1 , ce qui représente un coût
de stockage très faible. Par ailleurs, le calcul de x k+1 ne requiert que
l’évaluation de produits matrice-vecteur et de produits scalaires.
2. Les gradients g k sont deux à deux orthogonaux et les directions de descente d k sont A-conjuguées, c’est-à-dire telles que (Ad i , d j ) = 0, pour tout
couple i = j. Il en résulte que les vecteurs (g 0 , · · · , g k ) forment une famille
libre jusqu’à l’itération k pour laquelle g k = 0 (condition de convergence
de l’algorithme). Comme une famille libre dans un espace de dimension n
ne peut pas contenir plus de n éléments, cela signifie que l’algorithme du
gradient conjugué converge en au plus n itérations (fort heureusement, la
convergence à près a lieu en beaucoup moins de n itérations pour un
problème bien conditionné).
La généralisation à une fonctionnelle non quadratique de l’algorithme du gradient conjugué porte le nom de gradient conjugué non linéaire. En s’inspirant
de (6.29) la direction de descente est prise de la forme
d k = −g k + c k−1 d k−1 .
(6.29)
Contrairement au cas quadratique où l’on pouvait déterminer analytiquement
la valeur optimale du coefficient c k−1 , il faut ici se donner un critère de choix
de ce coefficient. On peut par exemple choisir comme ci-dessus
c k−1 =
|g k |
2
|g k−1 | 2 ,
(6.30)
ce qui donne la méthode de Fletcher-Reeves. Un autre choix possible consiste
à prendre
c k−1 =
((g k − g k−1 ), g k )
|g k−1 | 2
.
(6.31)
C’est la méthode de Polak-Ribière. Notons que les formules (6.30) et (6.31)
sont équivalentes dans le cas quadratique (car g k−1 et g k sont alors orthogonaux), mais pas dans le cas général.
On dispose d’une preuve de convergence de l’algorithme de Fletcher-Reeves
mais personne ne l’utilise plus car il est trop lent. La situation est inverse pour
Polak-Ribière : on sait que cet algorithme ne converge pas à tous les coups,
mais on l’utilise beaucoup car c’est une méthode performante la plupart du
temps.
167
x k+1 = x k + t k d k
(6.28)
d k = −g k + c k−1 d k−1
c k−1 =
|g k |
2
|g k−1 | 2
t k = −
(g k , d k )
(d k , Ad k )
.
Pour calculer x k+1 , il suffit donc de connaître le point x k , le gradient
g k et la dernière direction de descente d k−1 , ce qui représente un coût
de stockage très faible. Par ailleurs, le calcul de x k+1 ne requiert que
l’évaluation de produits matrice-vecteur et de produits scalaires.
2. Les gradients g k sont deux à deux orthogonaux et les directions de descente d k sont A-conjuguées, c’est-à-dire telles que (Ad i , d j ) = 0, pour tout
couple i = j. Il en résulte que les vecteurs (g 0 , · · · , g k ) forment une famille
libre jusqu’à l’itération k pour laquelle g k = 0 (condition de convergence
de l’algorithme). Comme une famille libre dans un espace de dimension n
ne peut pas contenir plus de n éléments, cela signifie que l’algorithme du
gradient conjugué converge en au plus n itérations (fort heureusement, la
convergence à près a lieu en beaucoup moins de n itérations pour un
problème bien conditionné).
La généralisation à une fonctionnelle non quadratique de l’algorithme du gradient conjugué porte le nom de gradient conjugué non linéaire. En s’inspirant
de (6.29) la direction de descente est prise de la forme
d k = −g k + c k−1 d k−1 .
(6.29)
Contrairement au cas quadratique où l’on pouvait déterminer analytiquement
la valeur optimale du coefficient c k−1 , il faut ici se donner un critère de choix
de ce coefficient. On peut par exemple choisir comme ci-dessus
c k−1 =
|g k |
2
|g k−1 | 2 ,
(6.30)
ce qui donne la méthode de Fletcher-Reeves. Un autre choix possible consiste
à prendre
c k−1 =
((g k − g k−1 ), g k )
|g k−1 | 2
.
(6.31)
C’est la méthode de Polak-Ribière. Notons que les formules (6.30) et (6.31)
sont équivalentes dans le cas quadratique (car g k−1 et g k sont alors orthogonaux), mais pas dans le cas général.
On dispose d’une preuve de convergence de l’algorithme de Fletcher-Reeves
mais personne ne l’utilise plus car il est trop lent. La situation est inverse pour
Polak-Ribière : on sait que cet algorithme ne converge pas à tous les coups,
mais on l’utilise beaucoup car c’est une méthode performante la plupart du
temps.