Méthode de Quasi-Newton

Cet article est une ébauche concernant les mathématiques. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

La méthode de Quasi-Newton est une méthode numérique utilisée pour résoudre des systèmes d'équations non linéaires. Typiquement, le problème que résout une méthode de Quasi-Newton est $f(x) = 0$ avec $f:\mathbb{R}^n \to\mathbb{R}^n$ dont on ne connaît pas forcément l'expression analytique.

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)$, mais 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}\cdot 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\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) ~.$

Dans cette formule, $\rho_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}{^ts_k\, B_{k}y_k} (^ts_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$ (voir ci-dessous).

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 $\rho_k$ s'en déduit, il est nécessairement strictement positif et choisi pour minimiser $f(x_k + \rho_k d_k)$
• on trouve le $k+1^{e}$ terme de la suite $x_{k+1} = x_k + \rho_k \cdot 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 {}^t y_k B_k}{{}^t y_k B_k y_k}$

avec, comme ci-dessus, $y_k=f(x_{k+1})-f(x_k)$ et $s_k=x_{k+1} -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-Goldfarb-Shanno (BFGS) qui est encore plus efficace.

Voir aussi

• Méthode de Newton
• Méthode de la sécante
• Critères de Wolfe

Sources

• Un cours d'optimisation traitant des méthodes de Quasi-Newton
• Méthodes numériques itératives, Claude Brezinski, Michela Redivo-Zaglia, Éditions Ellipses