An augmented Lagrangian algorithm for constrained nonlinear least-squares

Resumen Técnico: Un Algoritmo de Lagrangiano Aumentado para Mínimos Cuadrados No Lineales Restringidos

Formulación del Problema
El artículo aborda el problema de mínimos cuadrados no lineales (NLS, por sus siglas en inglés) restringido, definido como la minimización de la suma de los residuos al cuadrado $\frac{1}{2}\|r(x)\|^2$ sujeto a una mezcla de restricciones de igualdad no lineales $c(x)=0$ y restricciones lineales $x \in \Omega$. El conjunto $\Omega$ abarca igualdades lineales ($Ax=b$) y restricciones de límites ($l \le x \le u$). Se asume que los residuos $r(x)$ y las restricciones $c(x)$ son dos veces continuamente diferenciables. El desafío principal para resolver tales problemas radica en manejar eficientemente la estructura de NLS —específicamente, la descomposición del Hessiano del objetivo en un término de primer orden $J(x)^\top J(x)$ y un término de segundo orden que involucra los Hessianos de los residuos individuales— mientras se imponen simultáneamente las restricciones generales.

Metodología
El algoritmo propuesto, implementado en Julia como TRAULLS, integra el marco de Lagrangiano Aumentado (AL) con aproximaciones de quasi-Newton estructuradas (SQN) y técnicas de proyección de gradiente.

1. Marco de Lagrangiano Aumentado:
   Los términos de las restricciones no lineales se incorporan a la función objetivo mediante un término de penalización AL, transformando el problema original en una secuencia de subproblemas linealmente restringidos. En cada iteración externa $K$, el algoritmo minimiza la función AL $\Phi(x, \lambda, \mu)$ sobre el conjunto poliédrico $\Omega$.

• Actualización de Multiplicadores y Penalización: Si la factibilidad no lineal mejora suficientemente, los multiplicadores de Lagrange se actualizan mediante ascenso dual ($\lambda_{K+1} = \lambda_K + \mu_K c(x_K)$). Si la factibilidad no mejora, se incrementa el parámetro de penalización $\mu_K$ para imponer las restricciones de manera más estricta en la siguiente iteración.
• Minimización Interna: El subproblema (minimizar $\Phi$ sobre $\Omega$) se resuelve utilizando un método de región de confianza. El algoritmo emplea una estructura anidada donde cada iteración externa dispara una secuencia de iteraciones internas ($k$), las cuales están compuestas a su vez por iteraciones menores ($j$).

2. Minimización Interna y Computación de Pasos:
   El bucle interno utiliza una técnica de proyección de gradiente adaptada para conjuntos poliédricos.

• Paso de Cauchy: Se computa un paso de Cauchy encontrando el primer minimizador local de un modelo cuadrático a lo largo de la trayectoria del gradiente proyectado. Esto asegura la convergencia global.
• Minimización de Subespacio: Para acelerar la convergencia, el algoritmo realiza una secuencia de iteraciones menores dentro del subespacio definido por las restricciones activas en el punto de Cauchy. Estos pasos se computan utilizando un método de Gradiente Conjugado Proyectado (PCG).
• Región de Confianza: Una estrategia de región de confianza controla la calidad del paso, con la región definida por una norma $\ell_\infty$ para mantener la estructura poliédrica de las restricciones.

3. Aproximación del Hessiano Estructurado:
   Una contribución clave es la aproximación del Hessiano de AL. En lugar de computar los términos de segundo orden completos (lo cual es computacionalmente costoso), el método aproxima el Hessiano como $H_k = B^{GN}_k + B_k$, donde:

• $B^{GN}_k = J_k^\top J_k + \mu C_k^\top C_k$ es la aproximación de Gauss-Newton.
• $B_k$ es una corrección estructurada que aproxima los términos de segundo orden de los residuos y las restricciones.
• Regla de Actualización: El artículo emplea una actualización de Rango-1 Simétrica (SR1) derivada de una ecuación secante estructurada diseñada para la estructura de NLS. Esta ecuación relaciona el cambio en los gradientes con el cambio en las variables a través de los Jacobianos de los residuos y las restricciones.
• Estrategia Híbrida: El algoritmo cambia dinámicamente entre el modelo puro de Gauss-Newton y el modelo SQN estructurado basándose en la magnitud de los residuos (usando un criterio de cambio $\zeta_k$). Si los residuos son pequeños, se utiliza el modelo GN; de lo contrario, se aplica la corrección estructurada para mejorar la precisión.

Contribuciones Clave

• Integración Algorítmica: El artículo presenta un resolvedor que unifica el marco de Lagrangiano Aumentado con actualizaciones de quasi-Newton estructuradas diseñadas específicamente para la estructura de suma de cuadrados tanto del objetivo como del término de penalización.
• Manejo de Restricciones Generales: A diferencia de muchos resolvedores de NLS existentes que se centran en restricciones de límites, este método maneja directamente una mezcla de igualdades lineales, límites y desigualdades no lineales sin convertir todas las restricciones en límites.
• Ecuación Secante Estructurada: La derivación de una ecuación secante (Eq. 2.26) que respeta la estructura de NLS permite la aproximación eficiente del Hessiano sin computar segundas derivadas completas.
• Convergencia Global: Los autores proporcionan una prueba rigurosa de convergencia global a un punto crítico de primer orden, estableciendo que el método converge bajo supuestos estándar (diferenciabilidad dos veces continua, independencia lineal de las restricciones activas).

Resultados Numéricos
Los autores evaluaron TRAULLS en 79 instancias de problemas que van desde 2 hasta 1000 variables, incluyendo problemas de colecciones estándar y benchmarks específicos.

• Comparación de Aproximación del Hessiano: Los experimentos comparando Gauss-Newton (GN), SR1 puro, BFGS puro y sus variantes híbridas mostraron que el enfoque Híbrido SR1 ofrecía el mejor equilibrio entre robustez y eficiencia. Mientras que GN fue el más rápido por iteración, el enfoque híbrido requirió menos iteraciones internas y demostró una robustez superior en problemas con residuos más grandes.
• Comparación con el Estado del Arte: TRAULLS se comparó contra IPOPT (un resolvedor de punto interior de propósito general) y Percival (otro resolvedor basado en AL).
  • Desempeño: TRAULLS logró tiempos de computación comparables a IPOPT, aunque IPOPT generalmente requirió menos evaluaciones de función debido a su uso de Hessianos exactos.
  • Robustez: TRAULLS superó significativamente a Percival, demostrando que explotar la estructura específica de mínimos cuadrados produce un mejor desempeño incluso dentro del mismo marco algorítmico (AL).
  • Limitaciones: El almacenamiento denso requerido para la corrección del Hessiano estructurado limita la escalabilidad para un número muy grande de variables, un punto que los autores reconocen.

Significancia y Reivindicaciones
El artículo afirma presentar un resolvedor diseñado específicamente para problemas de NLS restringidos que equilibra eficazmente la explotación de la estructura de mínimos cuadrados con la flexibilidad para manejar restricciones generales. Los autores enfatizan que su enfoque evita el alto costo de computar derivadas de segundo orden completas mientras mantiene la robustez mediante actualizaciones estructuradas. La significancia reside en proporcionar una herramienta especializada para problemas de ajuste de datos y estimación de parámetros donde se requiere consistencia física (impuesta por las restricciones), ofreciendo una alternativa competitiva a los resolvedores de propósito general como IPOPT y a los métodos AL existentes como Percival. Los autores señalan modestamente que, si bien la implementación actual muestra un desempeño prometedor, el trabajo futuro debería abordar la escalabilidad mediante variantes de memoria limitada y muestreo adaptativo para conjuntos de residuos grandes.