Algoritmo de Levenberg-Marquardt
En matemáticas y computación, el algoritmo de Levenberg-Marquardt (LMA o simplemente LM), también conocido como el método de mínimos cuadrados amortiguados (DLS), se utiliza para resolver problemas de mínimos cuadrados no lineales.
Sin embargo, como ocurre con muchos algoritmos de ajuste, el LMA solo encuentra un mínimo local, que no es necesariamente el mínimo global.
Para funciones de buen comportamiento y parámetros de inicio razonables, el LMA tiende a ser un poco más lento que el GNA.
El algoritmo fue publicado por primera vez en 1944 por Kenneth Levenberg,[1] mientras trabajaba en el Arsenal del Ejército de Frankford.
Fue redescubierto en 1963 por Donald Marquardt,[2] quien trabajó como estadístico en DuPont, e independientemente por Girard[3] Wynne[4] y Morrison.
Para iniciar una minimización, el usuario debe proporcionar una estimación inicial del vector de parámetros β.
En los casos con solo un mínimo, una conjetura estándar no informada como β T = (1, 1, ..., 1) funcionará bien; en los casos con múltiples mínimos, el algoritmo converge al mínimo global solo si la estimación inicial ya es algo cercana a la solución final.
se aproxima por su linealización: donde es el gradiente (fila-vector en este caso) de f con respecto a β .
da o en notación vectorial, Tomando la derivada de
es la matriz jacobiana, cuya fila i es igual a
Este es un conjunto de ecuaciones lineales, que se pueden resolver para δ .
El factor de amortiguamiento (no negativo) λ se ajusta en cada iteración.
Si la reducción de S es rápida, se puede usar un valor más pequeño, acercando el algoritmo al algoritmo de Gauss-Newton, mientras que si una iteración produce una reducción insuficiente del residual, λ puede aumentarse, dando un paso más cerca del descenso del gradiente dirección.
Por lo tanto, para valores grandes de λ, el paso se tomará aproximadamente en la dirección del gradiente.
Si el valor del factor de amortiguamiento λ es grande en relación con la norma de JTJ, no es necesario resolver el sistema con matriz JTJ + λI , dado que esta matriz se puede aproximar mediante λI.
En este caso el algoritmo realiza una actualización en la dirección del gradiente, con un paso pequeño:
R. Fletcher proporcionó la idea de que podemos escalar cada componente del gradiente según la curvatura, de modo que haya un movimiento más grande a lo largo de las direcciones donde el gradiente es más pequeño.
Esto evita la convergencia lenta en la dirección del gradiente pequeño.
Se han presentado varios argumentos más o menos heurísticos para la mejor opción para el parámetro de amortiguación λ.
Existen argumentos teóricos que muestran por qué algunas de estas opciones garantizan la convergencia local del algoritmo; sin embargo, estas elecciones pueden hacer que la convergencia global del algoritmo sufra de las propiedades indeseables del descenso más pronunciado, en particular, una convergencia muy lenta cerca del óptimo.
Marquardt recomendó comenzar con un valor λ 0 y un factor ν>1.
Si ambos de estos son peores que el punto inicial, entonces la amortiguación se incrementa por multiplicación sucesiva por ν hasta que se encuentra un punto mejor con un nuevo factor de amortiguación de λ0νk para algunos k .
Si el uso del factor de amortiguación λ / ν da como resultado una reducción en el residuo al cuadrado, esto se toma como el nuevo valor de λ (y la nueva ubicación óptima se toma como la obtenida con este factor de amortiguación) y el proceso continúa; si el uso de λ/ν resultó en un peor residuo, pero el uso de λ resultó en un mejor residual, entonces λ se mantiene sin cambios y el nuevo óptimo se toma como el valor obtenido con λ como factor de amortiguamiento.
utilizando el algoritmo de Levenberg-Marquardt implementado en Octave GNU como la función leasqr.
Las gráficas muestran una mejor adaptación progresiva para los parámetros a = 100, b = 102 utilizados en la curva inicial.
Solo cuando los parámetros en el último gráfico son elegidos más cercanos al original, las curvas se ajustan exactamente.
Levenberg-Marquardt es un algoritmo incorporado en entornos de computación numérica SciPy, Octave GNU, Scilab, Mathematica, Matlab, NeuroSolutions, Origin, Fityk, IGOR Pro, LabVIEW y SAS.
También existen numerosas bibliotecas de software que permiten utilizar el algoritmo LM en aplicaciones independientes.
