Méthode de Quasi-Newton

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 le système est assez grand, le calcul de la matrice jacobienne est très long,
• 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, ρ_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₀ = I et x₀ 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_kf(x_k)
• le coefficient ρ_k s'en déduit, il est nécessairement strictement positif et choisi pour minimiser f(x_k + ρ_kd_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