En matemáticas e informática, el algoritmo de Levenberg-Marquardt ( LMA o simplemente LM ), también conocido como método de mínimos cuadrados amortiguados ( DLS ), se utiliza para resolver problemas de mínimos cuadrados no lineales . Estos problemas de minimización surgen especialmente en el ajuste de curvas de mínimos cuadrados .
El LMA se utiliza en muchas aplicaciones de software para resolver problemas genéricos de ajuste de curvas. 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 . El LMA interpola entre el algoritmo de Gauss-Newton (GNA) y el método de descenso de gradiente . El LMA es más robusto que el GNA, lo que significa que en muchos casos encuentra una solución incluso si comienza muy lejos del mínimo final. Para funciones de buen comportamiento y parámetros de inicio razonables, el LMA tiende a ser más lento que el GNA. LMA también puede verse como Gauss-Newton utilizando un enfoque de región de confianza .
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] que trabajó como estadístico en DuPont , e independientemente por Girard, [3] Wynne [4] y Morrison. [5]
El problema
La aplicación principal del algoritmo de Levenberg-Marquardt se encuentra en el problema de ajuste de curvas de mínimos cuadrados: dado un conjunto de pares empíricos de variables independientes y dependientes, encuentre los parámetros de la curva del modelo de modo que la suma de los cuadrados de las desviaciones se minimiza:
- que se supone que no está vacío.
La solución
Como otros algoritmos de minimización numérica, el algoritmo de Levenberg-Marquardt es un procedimiento iterativo . Para iniciar una minimización, el usuario debe proporcionar una estimación inicial del vector de parámetros. En casos con solo un mínimo, una suposición estándar desinformada comofuncionará bien; en casos con múltiples mínimos , el algoritmo converge al mínimo global solo si la estimación inicial ya está algo cerca de la solución final.
En cada paso de la iteración, el vector de parámetros se reemplaza por una nueva estimación . Para determinar, la función se aproxima por su linealización :
dónde
es el gradiente (fila-vector en este caso) de con respecto a .
La suma de desviaciones cuadradas tiene su mínimo en un gradiente cero con respecto a. La aproximación de primer orden anterior de da
o en notación vectorial,
Tomando la derivada de con respecto a y establecer el resultado en cero da
dónde es la matriz jacobiana , cuya-th fila es igual a , y donde y son vectores con -th componente y respectivamente. La expresión anterior obtenida paraviene bajo el método de Gauss-Newton. La matriz jacobiana como se define arriba no es (en general) una matriz cuadrada, sino una matriz rectangular de tamaño, dónde es el número de parámetros (tamaño del vector ). La multiplicación de matrices produce el requerido matriz cuadrada y el producto matriz-vector en el lado derecho produce un vector de tamaño . El resultado es un conjunto de ecuaciones lineales, que se pueden resolver para .
La contribución de Levenberg es reemplazar esta ecuación por una "versión amortiguada":
dónde es la matriz de identidad, dando como incremento al vector de parámetro estimado .
El factor de amortiguación (no negativo) se ajusta en cada iteración. Si la reducción dees rápido, se puede usar un valor menor, acercando el algoritmo al algoritmo de Gauss-Newton , mientras que si una iteración da una reducción insuficiente en el residual,se puede aumentar, dando un paso más hacia la dirección de descenso del gradiente. Tenga en cuenta que el gradiente de con respecto a es igual a . Por lo tanto, para valores grandes de, el paso se dará aproximadamente en la dirección opuesta a la pendiente. Si la longitud del paso calculado o la reducción de la suma de cuadrados del último vector de parámetros caer por debajo de los límites predefinidos, paradas de iteración y el último vector de parámetro se considera la solución.
El algoritmo de Levenberg tiene la desventaja de que si el valor del factor de amortiguación es grande, invertido no se utiliza en absoluto. [ aclaración necesaria ] Fletcher proporcionó la idea de que podemos escalar cada componente del gradiente de acuerdo con la curvatura, de modo que haya un mayor movimiento a lo largo de las direcciones donde el gradiente es más pequeño. Esto evita la convergencia lenta en la dirección de un pequeño gradiente. Por lo tanto, Fletcher en su artículo de 1971 Una subrutina de Marquardt modificada para mínimos cuadrados no lineales reemplazó la matriz de identidad con la matriz diagonal que consta de los elementos diagonales de , lo que hace que la escala de la solución sea invariante:
Un factor de amortiguamiento similar aparece en la regularización de Tikhonov , que se utiliza para resolver problemas lineales mal planteados , así como en la regresión de crestas , una técnica de estimación en estadística .
Elección del parámetro de amortiguación
Se han presentado varios argumentos más o menos heurísticos para la mejor elección del 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 adolezca de las propiedades indeseables del descenso más pronunciado , en particular, una convergencia muy lenta cercana al óptimo.
Los valores absolutos de cualquier elección dependen de qué tan bien escalado esté el problema inicial. Marquardt recomendó comenzar con un valor y un factor . Configuración inicial y calcular la suma residual de cuadrados después de un paso desde el punto de partida con el factor de amortiguación de y en segundo lugar con . Si ambos son peores que el punto inicial, entonces el amortiguamiento aumenta mediante multiplicaciones sucesivas por hasta que se encuentre un mejor punto con un nuevo factor de amortiguación de para algunos .
Si el uso del factor de amortiguación da como resultado una reducción en el residuo al cuadrado, entonces esto se toma como el nuevo valor de (y se toma la nueva ubicación óptima como la obtenida con este factor de amortiguación) y el proceso continúa; si usa resultó en un residuo peor, pero usando resultó en un mejor residual, entonces se deja sin cambios y el nuevo óptimo se toma como el valor obtenido con como factor de amortiguación.
Una estrategia eficaz para el control del parámetro de amortiguación, denominada gratificación retrasada , consiste en aumentar el parámetro en una pequeña cantidad para cada paso cuesta arriba y disminuir en una gran cantidad para cada paso cuesta abajo. La idea detrás de esta estrategia es evitar moverse cuesta abajo demasiado rápido al comienzo de la optimización, restringiendo así los pasos disponibles en iteraciones futuras y, por lo tanto, ralentizando la convergencia. [6] Se ha demostrado que un aumento en un factor de 2 y una disminución en un factor de 3 son efectivos en la mayoría de los casos, mientras que para problemas grandes los valores más extremos pueden funcionar mejor, con un aumento en un factor de 1.5 y una disminución. por un factor de 5. [7]
Aceleración geodésica
Al interpretar el paso de Levenberg-Marquardt como la velocidad a lo largo de una ruta geodésica en el espacio de parámetros, es posible mejorar el método agregando un término de segundo orden que tenga en cuenta la aceleración a lo largo de la geodésica
dónde es la solución de
Dado que este término de aceleración geodésica depende solo de la derivada direccional a lo largo de la dirección de la velocidad , no requiere calcular la matriz derivada de segundo orden completa, lo que requiere solo una pequeña sobrecarga en términos de costo de cómputo. [8] Dado que la derivada de segundo orden puede ser una expresión bastante compleja, puede ser conveniente reemplazarla con una aproximación en diferencias finitas
dónde y ya han sido calculados por el algoritmo, por lo que solo se requiere una evaluación de función adicional para calcular . La elección del paso de diferencia finitapuede afectar la estabilidad del algoritmo, y un valor de alrededor de 0,1 suele ser razonable en general. [7]
Dado que la aceleración puede apuntar en dirección opuesta a la velocidad, para evitar que se detenga el método en caso de que el amortiguamiento sea demasiado pequeño, se agrega un criterio adicional sobre la aceleración para aceptar un paso, requiriendo que
dónde generalmente se fija a un valor menor que 1, con valores más pequeños para problemas más difíciles. [7]
La adición de un término de aceleración geodésica puede permitir un aumento significativo en la velocidad de convergencia y es especialmente útil cuando el algoritmo se mueve a través de cañones estrechos en el paisaje de la función objetivo, donde los pasos permitidos son más pequeños y la mayor precisión se debe al segundo orden. término da mejoras significativas. [7]
Ejemplo
En este ejemplo intentamos ajustar la función utilizando el algoritmo Levenberg-Marquardt implementado en GNU Octave como función leasqr . Los gráficos muestran un ajuste progresivamente mejor para los parámetros, utilizado en la curva inicial. Solo cuando los parámetros en el último gráfico se eligen más cercano al original, las curvas se ajustan exactamente. Esta ecuación es un ejemplo de condiciones iniciales muy sensibles para el algoritmo de Levenberg-Marquardt. Una razón de esta sensibilidad es la existencia de múltiples mínimos: la función tiene mínimos en el valor del parámetro y .
Ver también
- Región de confianza
- Método de Nelder-Mead
- También se han utilizado variantes del algoritmo de Levenberg-Marquardt para resolver sistemas de ecuaciones no lineales. [9]
Referencias
- ^ Levenberg, Kenneth (1944). "Un método para la solución de ciertos problemas no lineales en mínimos cuadrados" . Trimestral de Matemática Aplicada . 2 (2): 164–168. doi : 10.1090 / qam / 10666 .
- ^ Marquardt, Donald (1963). "Un algoritmo para la estimación de mínimos cuadrados de parámetros no lineales". Revista SIAM de Matemática Aplicada . 11 (2): 431–441. doi : 10.1137 / 0111030 . hdl : 10338.dmlcz / 104299 .
- ^ Girard, André (1958). "Extracto de Revue d'optique théorique et instrumentale ". Rev. Opt . 37 : 225–241, 397–424.
- ^ Wynne, CG (1959). "Diseño de lentes por computadora digital electrónica: I". Proc. Phys. Soc. Lond . 73 (5): 777–787. Código Bibliográfico : 1959PPS .... 73..777W . doi : 10.1088 / 0370-1328 / 73/5/310 .
- ^ Morrison, David D. (1960). "Métodos para problemas de mínimos cuadrados no lineales y pruebas de convergencia". Actas del Seminario del Laboratorio de Propulsión a Chorro sobre Programas de Seguimiento y Determinación de Órbitas: 1–9.
- ^ Transtrum, Mark K; Machta, Benjamín B; Sethna, James P (2011). "Geometría de mínimos cuadrados no lineales con aplicaciones a modelos descuidados y optimización". Revisión E física . APS. 83 (3): 036701.
- ^ a b c d Transtrum, Mark K; Sethna, James P (2012). "Mejoras en el algoritmo de Levenberg-Marquardt para la minimización de mínimos cuadrados no lineales". arXiv : 1201.5885 .
- ^ "Ajuste de mínimos cuadrados no lineales" . Biblioteca científica GNU. Archivado desde el original el 14 de abril de 2020.
- ^ Kanzow, Christian; Yamashita, Nobuo; Fukushima, Masao (2004). "Métodos de Levenberg-Marquardt con fuertes propiedades de convergencia local para resolver ecuaciones no lineales con restricciones convexas" . Revista de Matemática Computacional y Aplicada . 172 (2): 375–397. doi : 10.1016 / j.cam.2004.02.013 .
Otras lecturas
- Moré, Jorge J .; Sorensen, Daniel C. (1983). "Cálculo de un paso de región de confianza" (PDF) . SIAM J. Sci. Stat. Computación . 4 (3): 553–572. doi : 10.1137 / 0904038 .
- Gill, Philip E .; Murray, Walter (1978). "Algoritmos para la solución del problema de mínimos cuadrados no lineales". Revista SIAM de Análisis Numérico . 15 (5): 977–992. Código bibliográfico : 1978SJNA ... 15..977G . doi : 10.1137 / 0715063 .
- Pujol, José (2007). "La solución de problemas inversos no lineales y el método de Levenberg-Marquardt" . Geofísica . SEG. 72 (4): W1 – W16. Código Bibliográfico : 2007Geop ... 72W ... 1P . doi : 10.1190 / 1.2732552 .[ enlace muerto permanente ]
- Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2ª ed.). Saltador. ISBN 978-0-387-30303-1.
enlaces externos
- Se puede encontrar una descripción detallada del algoritmo en Recetas numéricas en C, Capítulo 15.5: Modelos no lineales
- CT Kelley, Métodos iterativos para la optimización , SIAM Frontiers in Applied Mathematics, no 18, 1999, ISBN 0-89871-433-8 . Copia en línea
- Historia del algoritmo en SIAM news
- Un tutorial de Ananth Ranganathan
- K. Madsen, HB Nielsen, O. Tingleff, Métodos para problemas de mínimos cuadrados no lineales (tutorial de mínimos cuadrados no lineales; código LM: secante jacobiana analítica )
- T. Strutz: Ajuste de datos e incertidumbre (una introducción práctica a los mínimos cuadrados ponderados y más). 2a edición, Springer Vieweg, 2016, ISBN 978-3-658-11455-8 .
- HP Gavin, el método Levenberg-Marquardt para problemas de ajuste de curvas de mínimos cuadrados no lineales ( implementación de MATLAB incluida)