# 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) := ∇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+1e 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.