Algorithme de Levenberg-Marquardt

Modèle:Voir homonymes 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 repose sur les méthodes derrière 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éveloppé 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.

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 Modèle:Math, on cherche le paramètre Modèle:Math de la fonction Modèle:Math de sorte que la somme des carrés des déviations

$S(𝒂)=\sum _{i=1}^m[y_i-f(x_i|𝒂){]}^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 Modèle:Math de départ. Dans beaucoup de cas, un paramètre de départ « standard », tel que Modèle:Math 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 Modèle:Math par une nouvelle estimation Modèle:Math. Afin de déterminer Modèle:Math, les fonctions Modèle:Math sont approchées en étant linéarisées :

$f(𝐩+𝐪)\approx f(𝐩)+𝐉𝐪,$

où on a noté Modèle:Math la jacobienne de Modèle:Mvar en Modèle:Math.

À un minimum de la somme des carrés Modèle:Mvar, on a Modèle:Math. En dérivant le carré de l'expression de droite, qui s'annule donc, et en posant Modèle:Math, on obtient :

$({𝐉}^T𝐉)𝐪\approx {𝐉}^T(𝐲-f(𝐩)),$

d'où l'on tire aisément Modèle:Math en inversant Modèle:Math.

Dans l'inversion matricielle, tout va dépendre du rapport entre la valeur propre la plus grande en norme, et la valeur propre la plus petite ; ce rapport, appelé conditionnement de matrice, va concrètement refléter la robustesse de l'algorithme face au bruit.

Le point essentiel de l'algorithme de Levenberg-Marquardt est d'approcher cette équation, en l'« amortissant » un peu. On parle alors de « chargement de la diagonale » afin de contourner le mauvais conditionnement le cas échéant, problème que l'on retrouve avec l'algorithme de Capon et que l'on peut résoudre par une décomposition en valeurs singulières :

$({𝐉}^T𝐉+\lambda \text{diag}({𝐉}^T𝐉))𝐪\approx {𝐉}^T(𝐲-f(𝐩)),$

Le facteur d'amortissement positif λ est ajusté à chaque nouvelle itération. Si la diminution de Modèle:Mvar 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 Modèle:Math 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 Modèle:Math. 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 Modèle:Math et avec un facteur Modèle:Math. On pose alors au départ Modèle:Math et on calcule la somme des carrés des déviations Modèle:Math après une itération, en utilisant le facteur d'amortissement Modèle:Math, puis en utilisant Modèle:Math. Si les deux derniers renvoient un point moins bon (somme plus élevée) que le point de départ, alors on augmente Modèle:Math en le multipliant par Modèle:Mvar, jusqu'à atteindre un point meilleur avec un nouveau facteur Modèle:Math pour un certain Modèle:Mvar.

Si l'utilisation du facteur Modèle:Math donne une somme plus faible, alors il est pris comme nouvelle valeur de Modèle:Math et l'algorithme continue. Si l'utilisation de Modèle:Math donne une somme plus importante, mais que l'utilisation de Modèle:Math donne une somme plus faible, alors Modèle:Math est conservé.

Références

• Modèle:En K. Levenberg, « A Method for the Solution of Certain Problems in Least Squares », dans Quart. Appl. Math. 2, 1944, Modèle:P.
• Modèle:En D. Marquardt, « An Algorithm for Least-Squares Estimation of Nonlinear Parameters », dans SIAM J. Appl. Math. 11, 1963, Modèle:P.
• Modèle:Article

Liens externes

Descriptions de l'algorithme

• Modèle:En Numerical Recipes in C, Chapter 15.5: Nonlinear models (avec une description de l'algorithme)
• Modèle:En Levenberg-Marquart Methods and Nonlinear Estimation (histoire de cet algorithme)
• Modèle:En The Levenberg-Marquardt Algorithm (didacticiel écrit par Ananth Ranganathan)

Mises en œuvre

• Modèle:En lmdif, implémentation classique en Fortran, domaine public.
• Modèle:En lmfit, bibliothèque pour une utilisation dans des programmes en C ou C++, licence : domaine public.
• Modèle:En La GNU Scientific Library (GSL) fait partie du projet GNU, il s'agit d'une bibliothèque écrite en C, licence: GPL.
• Modèle:En levmar, implémentation GPL en C++, Perl et Python.
• Modèle:En idiom.com et users.utu.fi : mises en œuvre Java.
• Modèle:En gnuplot en possède une implémentation.
• Modèle:En ALGLIB, implémentations en C#, C++, Delphi, Visual Basic.
• FitOO, implémentation sous forme de modèle et de macros pour OpenOffice.org.
• IMSL, implémentation pour Fortran, C/C++, Java et C#.
• Modèle:En The MathWorks: LMFsolve.m/LMFnlsq.m, implémentation pour Matlab.