Algorisme de Levenberg-Marquardt

En matemàtiques i informàtica, l'algorisme de Levenberg-Marquardt (LMA o simplement LM), també conegut com a mètode de mínims quadrats amortits (DLS), s'utilitza per resoldre problemes de mínims quadrats no lineals. Aquests problemes de minimització sorgeixen especialment en l'ajustament de corbes de mínims quadrats. El LMA interpola entre l'algorisme de Gauss-Newton (GNA) i el mètode de descens del gradient. El LMA és més robust que el GNA, la qual cosa vol dir que en molts casos troba una solució encara que comenci molt lluny del mínim final. Per a funcions ben educades i paràmetres inicials raonables, el LMA tendeix a ser més lent que el GNA. LMA també es pot veure com Gauss-Newton mitjançant un enfocament de regió de confiança.

L'algoritme va ser publicat per primera vegada el 1944 per Kenneth Levenberg, mentre treballava a l'Arsenal de l'exèrcit de Frankford. Va ser redescoberta el 1963 per Donald Marquardt, que va treballar com a estadístic a DuPont, i independentment per Girard, Wynne i Morrison.

El LMA s'utilitza en moltes aplicacions de programari per resoldre problemes genèrics d'ajust de corbes. Mitjançant l'ús de l'algorisme de Gauss-Newton, sovint convergeix més ràpidament que els mètodes de primer ordre. No obstant això, com altres algorismes d'optimització iterativa, el LMA només troba un mínim local, que no és necessàriament el mínim global.

El problema

L'aplicació principal de l'algorisme de Levenberg-Marquardt és en el problema d'ajustament de corbes de mínims quadrats: donat un conjunt de $m$ parelles empíriques $\left(x_{i},y_{i}\right)$ de variables independents i dependents, troba els paràmetres β de la corba del model $f\left(x,{\boldsymbol {\beta }}\right)$ de manera que la suma dels quadrats de les desviacions $S\left({\boldsymbol {\beta }}\right)$ es minimitza:

${\hat {\boldsymbol {\beta }}}\in \operatorname {argmin} \limits _{\boldsymbol {\beta }}S\left({\boldsymbol {\beta }}\right)\equiv \operatorname {argmin} \limits _{\boldsymbol {\beta }}\sum _{i=1}^{m}\left[y_{i}-f\left(x_{i},{\boldsymbol {\beta }}\right)\right]^{2},$ que se suposa que no és buit.

La solució

Com altres algorismes de minimització numèrica, l'algoritme de Levenberg-Marquardt és un procediment iteratiu. Per iniciar una minimització, l'usuari ha de proporcionar una estimació inicial del vector de paràmetre β. En casos amb només un mínim, un estàndard no informat endevina com ${\boldsymbol {\beta }}^{\text{T}}={\begin{pmatrix}1,\ 1,\ \dots ,\ 1\end{pmatrix}}$ funcionarà bé; en els casos amb mínims múltiples, l'algoritme convergeix al mínim global només si la conjectura inicial ja és una mica propera a la solució final.

Poor fit

Encaix millor

Exemple

En aquest exemple intentem ajustar la funció $y=a\cos \left(bX\right)+b\sin \left(aX\right)$ utilitzant l'algoritme Levenberg-Marquardt implementat a GNU Octave com a funció leasqr. Els gràfics mostren progressivament un millor ajust dels paràmetres $a=100$, $b=102$ utilitzat en la corba inicial. Només quan es trien els paràmetres de l'últim gràfic més propers a l'original, les corbes s'ajusten exactament. Aquesta equació és un exemple de condicions inicials molt sensibles per a l'algorisme de Levenberg-Marquardt. Una de les raons d'aquesta sensibilitat és l'existència de múltiples mínims: la funció $\cos \left(\beta x\right)$ té mínims al valor del paràmetre ${\hat {\beta }}$ i ${\hat {\beta }}+2n\pi$.

El millor ajust