Algorithme de Levenberg-Marquardt

L’algorithme de Levenberg-Marquardt, ou algorithme LM, permet d'obtenir une solution numérique au problème de minimisation d'une fonction, souvent non linéaire et dépendant de plusieurs variables. L'algorithme interpole l'algorithme de Gauss-Newton et l'algorithme du gradient. Plus stable que celui de Gauss-Newton, il trouve une solution même s'il est démarré très loin d'un minimum. Cependant, pour certaines fonctions très régulières, il peut converger légèrement moins vite. L'algorithme fut découvert par Kenneth Levenberg, puis publié par Donald Marquardt.

C'est un problème qui se présente souvent en régression linéaire et non linéaire.

Sommaire

Application à la méthode des moindres carrés

Énoncé

Son application principale est la régression au travers de la méthode des moindres carrés : étant donné un certain nombre de paires de données (ti, yi), on cherche le paramètre a de la fonction f(t|a) de sorte que la somme des carrés des déviations :

S(\boldsymbol a) = \sum_{i=1}^m [y_i - f(t_i | \boldsymbol a) ]^2\,

soit minimale.

Solution

La procédure de l'algorithme est itérative. On part d'un paramètre initial, que l'on suppose « assez proche » d'un minimum, et qui constituera le vecteur p de départ. Dans beaucoup de cas, un paramètre de départ « standard », tel que pT=(1,1,…,1) fonctionnera sans problème. Dans certains cas, il n'y a convergence que si le vecteur de départ n'est pas trop éloigné de la solution.

À chaque itération, on remplace p par une nouvelle estimation p + q. Afin de déterminer q, les fonctions fi(p + q) sont approchées en étant linéarisées :

f(p + q) ≈ f(p) + Jq

où on a noté J la jacobienne de f en p.

À un minimum de la somme des carrés S, on a \nabla_{q} S=0. En dérivant le carré de l'expression de droite, qui s'annule donc, on obtient :

(JTJ)q = JT[yf(p)]

d'où l'on tire aisément q en inversant JTJ. Le point essentiel de l'algorithme de Levenberg-Marquardt est d'approcher cette équation, en l' « amortissant » un peu :

(JTJ + λ.diag(JTJ))q = JT[yf(p)].

Le facteur d'amortissement positif λ est ajusté à chaque nouvelle itération. Si la diminution de S est rapide, on peut utiliser une valeur plus faible - ce qui rapproche l'algorithme de celui de Gauss-Newton. Si en revanche une itération est peu efficace, on peut augmenter λ - ce qui rapproche cette fois l'algorithme de celui du gradient. Un tel facteur d'amortissement est utilisé par exemple dans la régularisation de Tikhonov, utilisée pour résoudre certains problèmes linéaires.

Si on a effectué plus d'un certain nombre d'itérations, ou bien que l'on s'est approché suffisamment d'un minimum, la procédure se termine et renvoie le paramètre p comme estimation de la solution.

Choix du paramètre d'amortissement

De nombreux arguments, plus ou moins heuristiques ont été proposés afin de déterminer le meilleur facteur d'amortissement λ. Des démonstrations théoriques montrent que certains choix garantissent une convergence locale - mais peuvent afficher une convergence faible près de l'optimum.

La valeur absolue de tout choix dépend de l'échelle du problème. Marquardt recommandait de commencer à partir de λ0 et avec un facteur ν>1. On pose alors au départ λ=λ0 et calculons la somme des carrés des déviations S(p) après une itération, en utilisant le facteur d'amortissement λ=λ0, puis en utilisant λ/ν. Si les deux derniers renvoient un point moins bon que le point de départ, on augmente λ en le multipliant par ν, jusqu'à atteindre un point meilleur avec un nouveau facteur λνk pour un certain k.

Si l'utilisation du facteur λ/ν donne une somme plus faible, alors il est pris comme nouvelle valeur de λ et l'algorithme continue. Si l'utilisation de λ/ν donne une somme plus importante, mais que l'utilisation de λ donne une somme plus faible, alors λ est conservé.

Références

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Levenberg-Marquardt algorithm » (voir la liste des auteurs)
  • (en) K. Levenberg, « A Method for the Solution of Certain Problems in Least Squares », dans Quart. Appl. Math. 2, 1944, p. 164-168
  • (en) D. Marquardt, « An Algorithm for Least-Squares Estimation of Nonlinear Parameters », dans SIAM J. Appl. Math. 11, p. 1963, 431-441
  • (en) P. E. Gill et W. Murray, « Algorithms for the solution of the nonlinear least-squares problem », dans SIAM J. Numer. Anal., vol. 15, no 5, 1978, p. 977-992 

Liens externes

Descriptions de l'algorithme

Mises en œuvre


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Levenberg-Marquardt de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme De Levenberg-Marquardt — L’algorithme de Levenberg Marquardt, ou algorithme LM, permet d obtenir une solution numérique au problème de minimisation d une fonction, souvent non linéaire et dépendant de plusieurs variables. L algorithme interpole l algorithme de Gauss… …   Wikipédia en Français

  • Algorithme de levenberg-marquardt — L’algorithme de Levenberg Marquardt, ou algorithme LM, permet d obtenir une solution numérique au problème de minimisation d une fonction, souvent non linéaire et dépendant de plusieurs variables. L algorithme interpole l algorithme de Gauss… …   Wikipédia en Français

  • Levenberg-Marquardt — Algorithme de Levenberg Marquardt L’algorithme de Levenberg Marquardt, ou algorithme LM, permet d obtenir une solution numérique au problème de minimisation d une fonction, souvent non linéaire et dépendant de plusieurs variables. L algorithme… …   Wikipédia en Français

  • Algorithme de Gauss-Newton — En mathématiques, l algorithme de Gauss Newton est une méthode de résolution des problèmes de moindres carrés non linéaires. Elle peut être vue comme une modification de la méthode de Newton dans le cas multidimensionnel afin de trouver le… …   Wikipédia en Français

  • Marquardt-Levenberg — Algorithme de Levenberg Marquardt L’algorithme de Levenberg Marquardt, ou algorithme LM, permet d obtenir une solution numérique au problème de minimisation d une fonction, souvent non linéaire et dépendant de plusieurs variables. L algorithme… …   Wikipédia en Français

  • Donald Marquardt — Donald W. Marquardt (13 mars 1929 5 juillet 1997[1]) est un statisticien américain qui a publié l algorithme d ajustement aux moindres carrés d équations non linéaires, développé par Kenneth Levenberg et connu sous le nom d algorithme de… …   Wikipédia en Français

  • Matrice de Tikhonov — Régularisation Tychonoff La régularisation Tychonoff est la méthode de régularisation la plus utilisée pour la résolution de problèmes qui ne sont pas bien posés ainsi que pour les problèmes inverses. Elle a été imaginée par le mathématicien… …   Wikipédia en Français

  • Régularisation de Tikhonov — Régularisation Tychonoff La régularisation Tychonoff est la méthode de régularisation la plus utilisée pour la résolution de problèmes qui ne sont pas bien posés ainsi que pour les problèmes inverses. Elle a été imaginée par le mathématicien… …   Wikipédia en Français

  • Gauss-Newton — Algorithme de Gauss Newton L algorithme de Gauss Newton est une méthode de résolution des problèmes de moindres carrés non linéaires. Elle peut être vue comme une modification de la méthode de Newton dans le cas multidimensionnel afin de trouver… …   Wikipédia en Français

  • Determination des constantes d'equilibre — Détermination des constantes d équilibre Les constantes d équilibre sont évaluées pour quantifier les équilibres chimiques à partir de mesures de concentrations, directes ou indirectes, et mettant en œuvre des techniques numériques. Cet article… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”