Méthode quasi-Newton

Une méthode quasi-Newton est une méthode numérique utilisée pour résoudre des systèmes d'équations non linéaires, reposant sur un principe similaire à la méthode de Newton. Typiquement, le problème que résout une méthode quasi-Newton est la recherche d'un zéro d'une fonction à valeurs vectorielles dont on ne connaît pas forcément l'expression analytique de la matrice jacobienne ou de la hessienne.

Principe de la méthode quasi-Newton

Le problème posé est le même que celui d'une méthode de Newton : rechercher, pour une fonction $f:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ , les solutions $x$ tels que $f (x) = 0$ . Pour de tels problèmes, il est en général possible d'utiliser la méthode de Newton-Raphson, dont les itérations sont

x_{k+1}=x_{k}-Df(x_{k})^{-1}\cdot f(x_{k})

où $Df (x)$ désigne la matrice jacobienne de $f$ en $x$ . En dimension 1, on retrouve l'expression de la méthode de Newton-Raphson classique. Celle-ci pose quelques problèmes pratiques :

si la dimension $n$ du système est grande, le calcul de la matrice jacobienne peut prendre trop de temps de calcul,
de même, la résolution du système linéaire $Df (x k) -1 • f (x k)$ est une opération coûteuse en calculs.

L'idée des méthodes quasi-Newton est de remplacer $Df (x k) -1$ par une matrice $B k$ plus facile à calculer, et à laquelle on peut imposer certaines propriétés. Le fait qu'elle soit une approximation de l'inverse du jacobien se traduit par la relation de quasi-Newton

x_{k+1}-x_{k}=B_{k+1}\cdot (f(x_{k+1})-f(x_{k}))

ce qui est manifestement la généralisation du coefficient utilisé dans la méthode de la sécante.

Les itérations des méthodes de quasi-Newton sont alors de la forme suivante :

x_{k+1}=x_{k}-\rho _{k}\,B_{k}\cdot f(x_{k})~.

Le paramètre réel $ρ k$ est un coefficient choisi pour optimiser la convergence, et $B k$ est mise à jour à chaque itération selon une formule particulière. Selon les méthodes de quasi-Newton, la formule de mise à jour varie.

Souvent on applique la méthode à la recherche d'un minimum d'une fonction $g (x)$ que l'on traduit en la recherche de $f (x) := \nabla g (x) = 0$ . Dans ce cas il est naturel d'imposer à la matrice $B k$ qu'elle soit symétrique, car elle correspond alors à la matrice hessienne de $g$ .

Méthode de Broyden

Ici la mise à jour de la matrice $B k$ s'écrit

B_{k+1}=B_{k}+{\frac {s_{k}-B_{k}y_{k}}{^{t}s_{k}\,B_{k}y_{k}}}(^{t}s_{k}B_{k})

avec $s k = x k +1 - x k$ , $y k = f (x k +1) - f (x k)$ . Cette méthode s'applique au cas général où le jacobien n'a pas de raison d'être symétrique.

Méthode de Davidon-Fletcher-Powell

C'est historiquement la première méthode quasi-Newton appliquée à l'optimisation, c'est-à-dire au calcul d'un extremum d'une fonction. Par conséquent, elle impose la symétrie des matrices $B k$ . En effet, ici ces matrices sont censées représenter une approximation de l'inverse de la matrice hessienne de la fonction à minimiser. La symétrie de ces approximations est assurée par le fait qu'on utilise une mise à jour d'une forme particulièrement simple, $B_{k+1}=B_{k}+v_{k}\cdot {}^{t}v_{k}$ .

On initialise $B 0 = I$ et $x 0$ assez proche de la solution qu'on cherche. Les itérations sont les suivantes :

On calcule d'abord la direction de déplacement $d k = - B k f (x k)$
le coefficient $ρ k$ s'en déduit, il est nécessairement strictement positif et choisi pour minimiser $f (x k + ρ k d k)$
on trouve le k+1^e terme de la suite $x k +1 = x k + ρ k d k$
$B k +1$ est calculé par la formule de Davidon-Fletcher-Powell

B_{k+1}=B_{k}+{\frac {s_{k}{}^{t}s_{k}}{^{t}s_{k}y_{k}}}-{\frac {B_{k}y_{k}y_{k}{}^{t}B_{k}}{{}^{t}y_{k}B_{k}y_{k}}}

avec, comme ci-dessus,

s k = x k +1 - x k

y k = f (x k +1) - f (x k)

La méthode DFP a des propriétés satisfaisantes, mais dans la pratique elle est aujourd'hui en général remplacée par la méthode de Broyden-Fletcher-Goldfard-Shanno (BFGS) qui est encore plus efficace.

Voir aussi

Sources

Méthodes numériques itératives, Claude Brezinski, Michela Redivo-Zaglia, Éditions Ellipses

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.