Publication: A Limited-memory Levenberg-Marquardt algorithm for solving large-scale nonlinear least-square problems
Date
2021-05
Authors
Sanhueza Román, Ariel Omar
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
LARGE-SCALE PROBLEMS , OVERDETERMINED SYSTEM OF EQUATIONS , LEVENBERG-MARQUARDT , KRYLOV SUBSPACE