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:{ℝ}^n\to {ℝ}^n$, les solutions Modèle:Mvar tels que Modèle:Math. 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ù Modèle:Math désigne la matrice jacobienne de Modèle:Mvar en Modèle:Mvar. 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 Modèle:Mvar 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 Modèle:Math est une opération coûteuse en calculs.

L'idée des méthodes quasi-Newton est de remplacer Modèle:Math par une matrice Modèle:Mvar 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 Modèle:Mvar est un coefficient choisi pour optimiser la convergence, et Modèle:Mvar 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 Modèle:Math que l'on traduit en la recherche de Modèle:Math. Dans ce cas il est naturel d'imposer à la matrice Modèle:Mvar qu'elle soit symétrique, car elle correspond alors à la matrice hessienne de Modèle:Mvar.

Méthode de Broyden

Ici la mise à jour de la matrice Modèle:Mvar 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 Modèle:Math, Modèle:Math. 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 Modèle:Mvar. 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 Modèle:Math et Modèle:Math assez proche de la solution qu'on cherche. Les itérations sont les suivantes :

• On calcule d'abord la direction de déplacement Modèle:Math
• le coefficient Modèle:Mvar s'en déduit, il est nécessairement strictement positif et choisi pour minimiser Modèle:Math
• on trouve le k+1Modèle:Exp terme de la suite Modèle:Math
• Modèle:Math 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, Modèle:Math, Modèle:Math.

Voir aussi

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

Sources

• Modèle:Ouvrage