Méthode de Quasi-Newton


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(xk) − 1 par une matrice Bk 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 Bk 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 Bk qu'elle soit symétrique, car elle correspond alors à la matrice hessienne de g.


Sommaire

Méthode de Broyden

Ici la mise à jour de la matrice Bk 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 sk = xk + 1xk, yk = f(xk + 1) − f(xk). 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 Bk. 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 B0 = I et x0 assez proche de la solution qu'on cherche. Les itérations sont les suivantes:

  • On calcule d'abord la direction de déplacement: dk = − Bkf(xk)
  • le coefficient ρk s'en déduit, il est nécessairement strictement positif et choisi pour minimiser f(xk + ρkdk)
  • on trouve le k + 1e terme de la suite x_{k+1} = x_k + \rho_k \cdot d_k
  • Bk + 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, yk = f(xk + 1) − f(xk) et sk = xk + 1xk.

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

Sources


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode de Quasi-Newton de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Methode de Newton — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro …   Wikipédia en Français

  • Methode de la corde — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro …   Wikipédia en Français

  • Méthode De Newton — Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro …   Wikipédia en Français

  • Méthode de Newton-Raphson — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro …   Wikipédia en Français

  • Méthode de la corde — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro …   Wikipédia en Français

  • Méthode de newton — Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro …   Wikipédia en Français

  • Methode de Heron — Méthode de Héron En mathématiques, la méthode de Héron ou méthode babylonienne est une méthode efficace d extraction de racine carrée. Elle porte le nom du mathématicien Héron d Alexandrie mais certains calculs antérieurs semblent prouver que la… …   Wikipédia en Français

  • Methode de Laguerre — Méthode de Laguerre En analyse numérique, la méthode de Laguerre est un algorithme de recherche d un zéro d une fonction polynomiale. En d autres termes, la méthode de Laguerre peut être utilisée pour trouver une valeur approchée d un solution d… …   Wikipédia en Français

  • Méthode De Héron — En mathématiques, la méthode de Héron ou méthode babylonienne est une méthode efficace d extraction de racine carrée. Elle porte le nom du mathématicien Héron d Alexandrie mais certains calculs antérieurs semblent prouver que la méthode est plus… …   Wikipédia en Français

  • Méthode De Laguerre — En analyse numérique, la méthode de Laguerre est un algorithme de recherche d un zéro d une fonction polynomiale. En d autres termes, la méthode de Laguerre peut être utilisée pour trouver une valeur approchée d un solution d une équation de la… …   Wikipédia en Français