A Limited-memory Levenberg-Marquardt algorithm for solving large-scale nonlinear least-square problems

Abstract

En esta tesis se propone un solver para sistemas de ecuaciones no-lineales sobredeterminados de gran escala, basado en Levenberg-Marquardt. Tradicionalmente, el método de Levenberg-Marquardt requiere la solución de un sistema de ecuaciones lineales que involucra la matriz Jacobiana y su transpuesta. Este sistema de ecuaciones lineales es equivalente a las ecuaciones normales de un problema de m´ınimos cuadrados lineales. Desafortunadamente, Levenberg-Marquardt no es un método adecuado para problemas de gran escala debido al requerimiento de la matriz Jacobiana. Cuando la dimensión del problema es grande, el cálculo y almacenamiento explicito de la matriz no es posible, debido al alto uso de memoria. La gran mayoría de los algoritmos para problemas de gran escala están diseñados para problemas de optimización sin restricciones, y estos requieren del gradiente de la función objetivo, el cual involucra a la Matriz Jacobiana transpuesta. Si bien existen algoritmos matrix free de bajo costo computacional que aproximan el producto de la matriz Jacobiana por un vector, aproximar el producto de la transpuesta de la matriz Jacobiana por un vector requiere un mayor costo de computo. En esta tesis se propone el uso de Levenberg-Marquardt en conjunto con un nuevo algoritmo, basado en LSQR, llamado nsLSQR. El método nsLSQR resuelve un problema de mínimos cuadrados lineal utilizando una aproximación con diferencias finitas y una aproximación, de cualquier índole, de la matriz Jacobiana transpuesta. Para aproximar el producto de la matriz Jacobiana transpuesta por un vector, se propone un algoritmo, basado en cubanización, para aproximar la matriz Jacobiana. Mediante el uso de cubanización, el uso de memoria es reducido significativamente, respecto a una matriz explícitamente almacenada. Combinando la aproximación cuantizada y nsLSQR, se propone un algoritmo, el cual denominamos lm-nsLSQR (Levenberg-Marquardt nsLSQR), que permite minimizar el residuo de un sistema de ecuaciones no-lineales sobre determinado de gran escala.