Algorithme de Levenberg-Marquardt
607095
31018281
2008-06-26T06:51:00Z
129.187.179.90
/* Application à la méthode des moindres carrés */
L' '''algorithme de Levenberg-Marquardt''', ou '''algorithme LM''', permet d'obtenir une solution numérique au problème de minimisation d'une [[fonction (mathématiques)|fonction]], souvent non-linéaire et dépendant de plusieurs variables.
C'est un problème qui se présente souvent en [[régression linéaire]] et non-linéaire.
Il consiste à [[interpolation|interpoler]] l'[[algorithme de Gauss-Newton]] et la méthode de [[descente de gradient]]. L'algorithme est plus stable que le premier — c’est-à-dire qu'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]].
==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 (''t''<sub>''i''</sub>, ''y''<sub>''i''</sub>), on cherche le paramètre '''a''' de la fonction ''f''(''t''|'''a''') de sorte que la somme des carrés des déviations :
:<math>S(x) = \sum_{i=1}^m [y_i - f(t_i | a) ]^2\,</math>
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 '''p'''<sup>T</sup>=(1,1,...,1) fonctionnera sans problèmes. Dans la plupart des 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 ''f''<sub>''i''</sub>('''p''' + '''q''') sont approchées en étant linéarisées :
:'''f'''('''p''' + '''q''') ≈ '''f'''('''p''') + '''Jq'''
où on a noté '''J''' le [[Jacobien]] de '''f''' en '''p'''.
À un minimum de la somme des carrés ''S'', on a <math>\nabla_{q} S=0</math>. En dérivant le carré de l'expression de droite, qui s'annule donc, on obtient :
:('''J'''<sup>T</sup>'''J''')'''q''' = '''J'''<sup>T</sup>['''y''' − '''f'''('''p''')]
d'où l'on tire aisément '''q''' en inversant '''J'''<sup>T</sup>'''J'''.
Le point essentiel de l'algorithme de Levenberg-Marquardt est d'approcher cette équation, en l' « amortissant » un peu :
:('''J'''<sup>T</sup>'''J''' + λ.'''I''')'''q''' = '''J'''<sup>T</sup>['''y''' − '''f'''('''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 de descente de 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 λ<sub>0</sub> et avec un facteur ν>1. On pose alors au départ λ=λ<sub>0</sub> et calculons la somme des carrés des déviations ''S''('''p''') après une itération, en utilisant le facteur d'amortissement λ=λ<sub>0</sub>, 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 λν<sup>k</sup> 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é.
==Voir aussi==
===Références===
<references/>
{{Traduction/Référence|en|Levenberg-Marquardt algorithm|113860862}}
* Levenberg, K. ''« A Method for the Solution of Certain Problems in Least Squares. »'' Quart. Appl. Math. 2, 164-168, 1944.
* Marquardt, D. ''« An Algorithm for Least-Squares Estimation of Nonlinear Parameters. »'' SIAM J. Appl. Math. 11, 431-441, 1963.
* Gill, P. E. and Murray, W. ''« Algorithms for the solution of the nonlinear least-squares problem »'', SIAM J. Numer. Anal. 15 [5] 977-992, 1978.
===Liens externes===
====Descriptions de l'algorithme====
* {{en}} [http://www.nrbook.com/a/bookcpdf/c15-5.pdf « Numerical Recipes in C », Chapitre 15.5 : Modèles non-linéaires], avec une description de l'algorithme ;
* {{en}} [http://www.siam.org/siamnews/mtc/mtc1093.htm Histoire de l'algorithme] ;
* {{en}} [http://citeseer.ist.psu.edu/638988.html Tutoriel écrit par Ananth Ranganathan].
====Implémentations====
* {{en}} [http://www.netlib.org/minpack/ lmdif], implémentation classique en [[Fortran]], domaine publique;
* {{en}} [https://sourceforge.net/projects/lmfit/ sourceforge::lmfit], translation de lmdif en C, enveloppe pour régression, avec exemple d'application, domaine publique;
* {{en}} [http://www.ics.forth.gr/%7elourakis/levmar/ levmar], implémentation [[Licence publique générale GNU|GPL]] en [[C++]], [[Perl (langage)|Perl]] et [[Python (langage)|Python]] ;
* {{en}} [http://www.idiom.com/~zilla/Computer/Javanumeric/index.html] et [http://users.utu.fi/jaolho] : implémentations Java ;
* {{en}} [http://www.gnuplot.info/ gnuplot] en possède une implémentation ;
* {{en}} [http://www.alglib.net/optimization/levenbergmarquardt.php ALGLIB] : implémentations en C#, C++, Delphi, Visual Basic.
* {{fr}} [http://oooconv.free.fr/fitoo/fitoo_fr.html FitOO] : implémentation sous forme de modèle et de macros pour [[OpenOffice.org]].
{{portail informatique}}
[[Catégorie:Algorithme d'optimisation]]
[[de:Levenberg-Marquardt-Algorithmus]]
[[en:Levenberg–Marquardt algorithm]]
[[fa:الگوریتم لونبرگ-مارکارد]]
[[lt:Levenbergo-Markardo algoritmas]]
[[pl:Algorytm Levenberga-Marquardta]]