An augmented Lagrangian algorithm for constrained nonlinear least-squares

Resumo Técnico: Um Algoritmo de Lagrangiana Aumentada para Mínimos Quadrados Não Lineares Restringidos

Formulação do Problema
O artigo aborda o problema de mínimos quadrados não lineares (NLS) restrito, definido como a minimização da soma dos quadrados dos resíduos $\frac{1}{2}\|r(x)\|^2$ sujeito a uma mistura de restrições de igualdade não lineares $c(x)=0$ e restrições lineares $x \in \Omega$. O conjunto $\Omega$ abrange igualdades lineares ($Ax=b$) e restrições de limites ($l \le x \le u$). Assume-se que os resíduos $r(x)$ e as restrições $c(x)$ sejam duas vezes continuamente diferenciáveis. O principal desafio ao resolver tais problemas reside em lidar eficientemente com a estrutura de NLS — especificamente, a decomposição do Hessiano do objetivo em um termo de primeira ordem $J(x)^\top J(x)$ e um termo de segunda ordem envolvendo os Hessianos dos resíduos individuais — enquanto simultaneamente impõe restrições gerais.

Metodologia
O algoritmo proposto, implementado em Julia como TRAULLS, integra a estrutura de Lagrangiana Aumentada (AL) com aproximações de quasi-Newton estruturadas (SQN) e técnicas de projeção de gradiente.

1. Estrutura de Lagrangiana Aumentada:
   As restrições não lineares são incorporadas à função objetivo via um termo de penalidade AL, transformando o problema original em uma sequência de subproblemas linearmente restritos. Em cada iteração externa $K$, o algoritmo minimiza a função AL $\Phi(x, \lambda, \mu)$ sobre o conjunto poliédrico $\Omega$.

   • Atualização de Multiplicadores e Penalidade: Se a viabilidade não linear for suficientemente melhorada, os multiplicadores de Lagrange são atualizados via ascensão dual ($\lambda_{K+1} = \lambda_K + \mu_K c(x_K)$). Se a viabilidade não for melhorada, o parâmetro de penalidade $\mu_K$ é aumentado para impor as restrições de forma mais estrita na iteração seguinte.
   • Minimização Interna: O subproblema (minimização de $\Phi$ sobre $\Omega$) é resolvido usando um método de região de confiança. O algoritmo emprega uma estrutura aninhada onde cada iteração externa dispara uma sequência de iterações internas ($k$), que são por sua vez compostas por iterações menores ($j$).

2. Minimização Interna e Computação de Passo:
   O loop interno utiliza uma técnica de projeção de gradiente adaptada para conjuntos poliédricos.

   • Passo de Cauchy: Um passo de Cauchy é computado encontrando o primeiro minimizador local de um modelo quadrático ao longo do caminho do gradiente projetado. Isso garante convergência global.
   • Minimização de Subespaço: Para acelerar a convergência, o algoritmo realiza uma sequência de iterações menores dentro do subespaço definido pelas restrições ativas no ponto de Cauchy. Esses passos são computados usando um método de Gradiente Conjugado Projetado (PCG).
   • Região de Confiança: Uma estratégia de região de confiança controla a qualidade do passo, com a região definida por uma norma $\ell_\infty$ para manter a estrutura poliédrica das restrições.

3. Aproximação de Hessiano Estruturado:
   Uma contribuição fundamental é a aproximação do Hessiano da AL. Em vez de computar todos os termos de segunda ordem (que é computacionalmente caro), o método aproxima o Hessiano como $H_k = B^{GN}_k + B_k$, onde:

   • $B^{GN}_k = J_k^\top J_k + \mu C_k^\top C_k$ é a aproximação de Gauss-Newton.
   • $B_k$ é uma correção estruturada que aproxima os termos de segunda ordem dos resíduos e das restrições.
   • Regra de Atualização: O artigo emprega uma atualização de Rank-1 Simétrica (SR1) derivada de uma equação secante estruturada adaptada para a estrutura de NLS. Esta equação relaciona a mudança nos gradientes com a mudança nas variáveis via Jacobianos dos resíduos e das restrições.
   • Estratégia Híbrida: O algoritmo alterna dinamicamente entre o modelo Gauss-Newton puro e o modelo SQN estruturado com base na magnitude dos resíduos (usando um critério de alternância $\zeta_k$). Se os resíduos forem pequenos, o modelo GN é utilizado; caso contrário, a correção estruturada é aplicada para melhorar a precisão.

Principais Contribuições

• Integração Algorítmica: O artigo apresenta um solver que unifica a estrutura de Lagrangiana Aumentada com atualizações quasi-Newton estruturadas especificamente desenhadas para a estrutura de soma de quadrados tanto do objetivo quanto do termo de penalidade.
• Tratamento de Restrições Gerais: Diferente de muitos solvers de NLS existentes que focam em restrições de limites, este método lida diretamente com uma mistura de igualdades lineares, limites e igualdades não lineares sem converter todas as restrições em limites.
• Equação Secante Estruturada: A derivação de uma equação secante (Eq. 2.26) que respeita a estrutura de NLS permite a aproximação eficiente do Hessiano sem computar segundas derivadas completas.
• Convergência Global: Os autores fornecem uma prova rigorosa de convergência global para um ponto crítico de primeira ordem, estabelecendo que o método converge sob suposições padrão (duas vezes diferenciabilidade, independência linear das restrições ativas).

Resultados Numéricos
Os autores avaliaram o TRAULLS em 79 instâncias de problemas variando de 2 a 1000 variáveis, incluindo problemas de coleções padrão e benchmarks específicos.

• Comparação de Aproximação de Hessiano: Experimentos comparando Gauss-Newton (GN), SR1 puro, BFGS puro e suas variantes híbridas mostraram que a abordagem Híbrida SR1 ofereceu o melhor equilíbrio entre robustez e eficiência. Embora o GN tenha sido o mais rápido por iteração, a abordagem híbrida exigiu menos iterações internas e demonstrou robustez superior em problemas com resíduos maiores.
• Comparação com o Estado da Arte: O TRAULLS foi comparado ao IPOPT (um solver de ponto interior de propósito geral) e ao Percival (outro solver baseado em AL).
  • Desempenho: O TRAULLS alcançou tempos de computação comparáveis ao IPOPT, embora o IPOPT geralmente tenha exigido menos avaliações de função devido ao seu uso de Hessianos exatos.
  • Robustez: O TRAULLS superou significativamente o Percival, demonstrando que explorar a estrutura específica de mínimos quadrados produz melhor desempenho mesmo dentro do mesmo framework algorítmico (AL).
  • Limitações: O armazenamento denso exigido para a correção do Hessiano estruturado limita a escalabilidade para um número muito grande de variáveis, um ponto que os autores reconhecem.

Significância e Alegações
O artigo alega apresentar um solver especificamente desenhado para problemas de NLS restritos que equilibra efetivamente a exploração da estrutura de mínimos quadrados com a flexibilidade para lidar com restrições gerais. Os autores enfatizam que sua abordagem evita o alto custo de computar derivadas de segunda ordem completas, mantendo a robustez através de atualizações estruturadas. A significância reside em fornecer uma ferramenta especializada para problemas de ajuste de dados e estimativa de parâmetros onde a consistência física (imposta por restrições) é necessária, oferecendo uma alternativa competitiva para solvers de propósito geral como o IPOPT e métodos AL existentes como o Percival. Os autores observam modestamente que, embora a implementação atual mostre um desempenho promissor, trabalhos futuros devem abordar a escalabilidade através de variantes de memória limitada e amostragem adaptativa para grandes conjuntos de resíduos.