An augmented Lagrangian algorithm for constrained nonlinear least-squares

Sintesi Tecnica: Un Algoritmo di Lagrangiana Aumentata per il Minimo Quadrati Non Lineare Vincolato

Formulazione del Problema
Il documento affronta il problema del minimo dei quadrati non lineari (NLS) vincolato, definito come la minimizzazione della somma dei residui al quadrato $\frac{1}{2}\|r(x)\|^2$ soggetto a un mix di vincoli di uguaglianza non lineari $c(x)=0$ e vincoli lineari $x \in \Omega$. L'insieme $\Omega$ comprende uguaglianze lineari ($Ax=b$) e vincoli di intervallo ($l \le x \le u$). Si assume che i residui $r(x)$ e i vincoli $c(x)$ siano due volte continuamente differenziabili. La sfida principale nel risolvere tali problemi risiede nel gestire efficientemente la struttura NLS — specificamente, la decomposizione dell'Hessiana dell'obiettivo in un termine del primo ordine $J(x)^\top J(x)$ e un termine del secondo ordine che coinvolge le Hessiane dei singoli residui — pur imponendo contemporaneamente vincoli generali.

Metodologia
L'algoritmo proposto, implementato in Julia come TRAULLS, integra il framework della Lagrangiana Aumentata (AL) con approssimazioni quasi-Newton strutturate (SQN) e tecniche di proiezione del gradiente.

1. Framework della Lagrangiana Aumentata:
   I vincoli non lineari sono incorporati nella funzione obiettivo tramite un termine di penalità AL, trasformando il problema originale in una sequenza di sottoproblemi linearmente vincolati. Ad ogni iterazione esterna $K$, l'algoritmo minimizza la funzione AL $\Phi(x, \lambda, \mu)$ sul sottoinsieme poliedrico $\Omega$.

• Aggiornamento dei Moltiplicatori e della Penalità: Se la fattibilità non lineare è sufficientemente migliorata, i moltiplicatori di Lagrange vengono aggiornati tramite ascesa duale ($\lambda_{K+1} = \lambda_K + \mu_K c(x_K)$). Se la fattibilità non migliora, il parametro di penalità $\mu_K$ viene aumentato per imporre i vincoli più rigorosamente nell'iterazione successiva.
• Minimizzazione Interna: Il sottoproblema (minimizzazione di $\Phi$ su $\Omega$) è risolto utilizzando un metodo di regione di fiducia (trust-region). L'algoritmo impiega una struttura nidificata in cui ogni iterazione esterna innesca una sequenza di iterazioni interne ($k$), che sono ulteriormente composte da iterazioni minori ($j$).

2. Minimizzazione Interna e Calcolo del Passo:
   Il ciclo interno utilizza una tecnica di proiezione del gradiente adattata per insiemi poliedrici.

• Passo di Cauchy: Un passo di Cauchy viene calcolato trovando il primo minimizzatore locale di un modello quadratico lungo il percorso del gradiente proiettato. Ciò garantisce la convergenza globale.
• Minimizzazione nel Sottospazio: Per accelerare la convergenza, l'algoritmo esegue una sequenza di iterazioni minori all'interno del sottospazio definito dai vincoli attivi nel punto di Cauchy. Tali passi sono calcolati utilizzando un metodo di Gradiente Coniugato Proiettato (PCG).
• Regione di Fiducia: Una strategia di regione di fiducia controlla la qualità del passo, con la regione definita da una norma $\ell_\infty$ per mantenere la struttura poliedrica dei vincoli.

3. Approssimazione dell'Hessiana Strutturata:
   Un contributo chiave è l'approssimazione dell'Hessiana AL. Inveve di calcolare l'intero termine del secondo ordine (che è computazionalmente costoso), il metodo approssima l'Hessiana come $H_k = B^{GN}_k + B_k$, dove:

• $B^{GN}_k = J_k^\top J_k + \mu C_k^\top C_k$ è l'approssimazione di Gauss-Newton.
• $B_k$ è una correzione strutturata che approssima i termini del secondo ordine dei residui e dei vincoli.
• Regola di Aggiornamento: Il documento impiega un aggiornamento Symmetric Rank-1 (SR1) derivato da un'equazione secante strutturata su misura per la struttura NLS. Questa equazione mette in relazione la variazione dei gradienti con la variazione delle variabili tramite i Jacobiani dei residui e dei vincoli.
• Strategia Ibrida: L'algoritmo passa dinamicamente dal modello puro di Gauss-Newton al modello SQN strutturato in base all'entità dei residui (utilizzando un criterio di commutazione $\zeta_k$). Se i residui sono piccoli, viene utilizzato il modello GN; altrimenti, la correzione strutturata viene applicata per migliorare l'accuratezza.

Contributi Chiave

• Integrazione Algoritmica: Il documento presenta un solver che unifica il framework della Lagrangiana Aumentata con aggiornamenti quasi-Newton strutturati progettati specificamente per la struttura sum-of-squares sia dell'obiettivo che del termine di penalità.
• Gestione di Vincoli Generali: A differenza di molti solver NLS esistenti che si concentrano sui vincoli di intervallo, questo metodo gestisce direttamente un mix di uguaglianze lineari, intervalli e uguaglianze non lineari senza convertire tutti i vincoli in intervalli.
• Equazione Secante Strutturata: La derivazione di un'equazione secante (Eq. 2.26) che rispetta la struttura NLS consente l'approssimazione efficiente dell'Hessiana senza calcolare le derivate seconde complete.
• Convergenza Globale: Gli autori forniscono una prova rigorosa della convergenza globale a un punto critico del primo ordine, stabilendo che il metodo converge sotto ipotesi standard (due volte differenziabilità, indipendenza lineare dei vincoli attivi).

Risultati Numerici
Gli autori hanno valutato TRAULLS su 79 istanze di problemi che vanno da 2 a 1000 variabili, inclusi problemi da collezioni standard e benchmark specifici.

• Confronto dell'Approssimazione dell'Hessiana: Gli esperimenti che confrontano Gauss-Newton (GN), SR1 semplice, BFGS semplice e le loro varianti ibride hanno mostrato che l'approccio Hybrid SR1 offriva il miglior equilibrio tra robustezza ed efficienza. Mentre GN era il più veloce per iterazione, l'approccio ibrido richiedeva meno iterazioni interne e dimostrava una robustezza superiore su problemi con residui più grandi.
• Confronto con lo Stato dell'Arte: TRAULLS è stato confrontato con IPOPT (un solver a punto interno generico) e Percival (un altro solver basato su AL).
  • Prestazioni: TRAULLS ha ottenuto tempi di calcolo comparabili a IPOPT, sebbene IPOPT richiedesse generalmente meno valutazioni della funzione grazie all'uso di Hessiane esatte.
  • Robustezza: TRAULLS ha superato significativamente Percival, dimostrando che sfruttare la specifica struttura dei minimi quadrati produce prestazioni migliori anche all'interno dello stesso framework algoritmico (AL).
  • Limitazioni: Lo stoccaggio denso richiesto per la correzione dell'Hessiana strutturata limita la scalabilità per un numero molto elevato di variabili, un punto che gli autori riconoscono.

Significato e Rivendicazioni
Il documento sostiene di presentare un solver progettato specificamente per problemi NLS vincolati che bilancia efficacemente lo sfruttamento della struttura dei minimi quadrati con la flessibilità di gestire vincoli generali. Gli autori sottolineano che il loro approccio evita l'alto costo del calcolo delle derivate del secondo ordine complete mantenendo la robustezza attraverso aggiornamenti strutturati. La significatività risiede nel fornire uno strumento specializzato per problemi di adattamento dei dati (data-fitting) e stima dei parametri dove è richiesta la coerenza fisica (imposta dai vincoli), offendo un'alternativa competitiva ai solver generici come IPOPT e ai metodi AL esistenti come Percival. Gli autori notano con modestia che, sebbene l'attuale implementazione mostri prestazioni promettenti, il lavoro futuro dovrebbe affrontare la scalabilità attraverso varianti a memoria limitata e campionamento adattivo per set di residui di grandi dimensioni.