An augmented Lagrangian algorithm for constrained nonlinear least-squares

Technische Samenvatting: Een Augmented Lagrangian Algoritme voor Constrained Nonlinear Least-Squares

Probleemformulering
Het artikel behandelt het probleem van de geconstraineerde niet-lineaire kleinste kwadraten (nonlinear least-squares, NLS), gedefinieerd als het minimaliseren van de som van de gekwadrateerde residuen $\frac{1}{2}\|r(x)\|^2$ onderworpen aan een mix van niet-lineaire gelijkheidsrestricties $c(x)=0$ en lineaire restricties $x \in \Omega$. De verzameling $\Omega$ omvat lineaire gelijkheden ($Ax=b$) en grenswaarden (bounds) ($l \le x \le u$). De residuen $r(x)$ en restricties $c(x)$ worden verondersteld tweemaal continu differentieerbaar te zijn. De primaire uitdaging bij het oplossen van dergelijke problemen ligt in het efficiënt afhandelen van de NLS-structuur—specifiek de decompositie van de Hessiaan van de doelfunctie in een eerste-orde term $J(x)^\top J(x)$ en een tweede-orde term met betrekking tot de Hessiaanse matrices van individuele residuen—terwijl tegelijkertijd algemene restricties worden afgedwongen.

Methodologie
Het voorgestelde algoritme, geïmplementeerd in Julia als TRAULLS, integreert het Augmented Lagrangian (AL) raamwerk met gestructureerde quasi-Newton (SQN) benaderingen en gradiëntprojectietechnieken.

1. Augmented Lagrangian Raamwerk:
   De niet-lineaire restricties worden in de doelfunctie opgenomen via een AL-strafterm, waardoor het oorspronkelijke probleem wordt getransformeerd naar een sequentie van lineair geconstraineerde subproblemen. In elke buitenste iteratie $K$ minimaliseert het algoritme de AL-functie $\Phi(x, \lambda, \mu)$ over de polyedrische verzameling $\Omega$.

   • Multiplier en Strafparameter Updates: Als de niet-lineaire haalbaarheid voldoende is verbeterd, worden de Lagrange-multipliers bijgewerkt via duale ascensie ($\lambda_{K+1} = \lambda_K + \mu_K c(x_K)$). Als de haalbaarheid niet is verbeterd, wordt de strafparameter $\mu_K$ verhoogd om de restricties in de volgende iteratie strikter af te dwingen.
   • Innerlijke Minimalisatie: Het subprobleem (het minimaliseren van $\Phi$ over $\Omega$) wordt opgelost met behulp van een trust-region methode. Het algoritme maakt gebruik van een geneste structuur waarbij elke buitenste iteratie een sequentie van binnenste iteraties ($k$) triggert, die op hun beurt weer zijn samengesteld uit minor-iteraties ($j$).

2. Innerlijke Minimalisatie en Stapberekening:
   De binnenste lus maakt gebruik van een gradiëntprojectietechniek die is aangepast voor polyedrische verzamelingen.

   • Cauchy-stap: Een Cauchy-stap wordt berekend door de eerste lokale minimizer van een kwadratisch model langs het geprojecteerde gradiëntpad te vinden. Dit garandeert globale convergentie.
   • Subruimte Minimalisatie: Om de convergentie te versnellen, voert het algoritme een sequentie van minor-iteraties uit binnen de subruimte gedefinieerd door de actieve restricties bij het Cauchy-punt. Deze stappen worden berekend met behulp van een Projected Conjugate Gradient (PCG) methode.
   • Trust Region: Een trust-region strategie controleert de kwaliteit van de stap, waarbij de regio wordt gedefinieerd door een $\ell_\infty$ norm om de polyedrische structuur van de restricties te behouden.

3. Gestructureerde Hessiaan Benadering:
   Een belangrijke bijdrage is de benadering van de AL-Hessiaan. In plaats van de volledige tweede-orde termen te berekenen (wat computationeel duur is), benadert de methode de Hessiaan als $H_k = B^{GN}_k + B_k$, waarbij:

   • $B^{GN}_k = J_k^\top J_k + \mu C_k^\top C_k$ de Gauss-Newton benadering is.
   • $B_k$ een gestructureerde correctie is die de tweede-orde termen van de residuen en restricties benadert.
   • Update Regel: Het artikel gebruikt een Symmetric Rank-1 (SR1) update die is afgeleid van een gestructureerde secant-vergelijking die is afgestemd op de NLS-structuur. Deze vergelijking relateert de verandering in gradiënten aan de verandering in variabelen via de Jacobiaan van de residuen en restricties.
   • Hybride Strategie: Het algoritme schakelt dynamisch tussen het pure Gauss-Newton model en het gestructureerde SQN model op basis van de grootte van de residuen (met behulp van een schakelcriterium $\zeta_k$). Als de residuen klein zijn, wordt het GN-model gebruikt; anders wordt de gestructureerde correctie toegepast om de nauwkeurigheid te verbeteren.

Belangrijkste Bijdragen

• Algoritmische Integratie: Het artikel presenteert een solver die het Augmented Lagrangian raamwerk verenigt met gestructureerde quasi-Newton updates die specifiek zijn ontworpen voor de sum-of-squares structuur van zowel de doelfunctie als de strafterm.
• Afhandeling van Algemene Restricties: In tegenstelling tot veel bestaande NLS-solvers die zich richten op bound-restricties, handelt deze methode direct een mix van lineaire gelijkheden, bounds en niet-lineaire gelijkheden af zonder alle restricties naar bounds te converteren.
• Gestructureerde Secant Vergelijking: De afleiding van een secant-vergelijking (Eq. 2.26) die de NLS-structuur respecteert, maakt een efficiënte benadering van de Hessiaan mogelijk zonder de volledige tweede afgeleiden te hoeven berekenen.
• Globale Convergentie: De auteurs leveren een rigoureus bewijs voor globale convergentie naar een eerste-orde kritiek punt, waarbij zij vaststellen dat de methode convergeert onder standaardveronderstellingen (tweemaal differentieerbaar, lineaire onafhankelijkheid van actieve restricties).

Numerieke Resultaten
De auteurs hebben TRAULLS geëvalueerd op 79 probleeminstanties variërend van 2 tot 1000 variabelen, inclusief problemen uit standaard collecties en specifieke benchmarks.

• Vergelijking van Hessiaan Benadering: Experimenten die Gauss-Newton (GN), plain SR1, plain BFGS en hun hybride varianten vergeleken, lieten zien dat de Hybrid SR1 aanpak de beste balans bood tussen robuustheid en efficiëntie. Hoewel GN de snelste tijd per iteratie had, vereiste de hybride aanpak minder binnenste iteraties en vertoonde het een superieure robuustheid bij problemen met grotere residuen.
• Vergelijking met State-of-the-Art: TRAULLS werd vergeleken met IPOPT (een algemene interior-point solver) en Percival (een andere AL-gebaseerde solver).
  • Prestaties: TRAULLS behaalde computationele tijden die vergelijkbaar waren met IPOPT, hoewel IPOPT over het algemeen minder functie-evaluaties vereiste vanwege het gebruik van exacte Hessiaanse matrices.
  • Robuustheid: TRAULLS presteerde significant beter dan Percival, wat aantoont dat het exploiteren van de specifieke least-squares structuur betere prestaties oplevert, zelfs binnen hetzelfde algoritmische raamwerk (AL).
  • Beperkingen: De dichte opslag die vereist is voor de gestructureerde Hessiaan-correctie beperkt de schaalbaarheid voor een zeer groot aantal variabelen, een punt dat de auteurs zelf erkennen.

Betekenis en Claims
Het artikel claimt een solver te presenteren die specifiek is ontworig voor geconstraineerde NLS-problemen en die effectief een balans vindt tussen het exploiteren van de least-squares structuur en de flexibiliteit om algemene restricties af te handelen. De auteurs benadrukken dat hun aanpak de hoge kosten van het berekenen van volledige tweede-orde afgeleiden vermijdt terwijl de robuustheid behouden blijft door gestructureerde updates. De betekenis ligt in het bieden van een gespecialiseerde tool voor data-fitting en parameterschattingsproblemen waarbij fysieke consistentie (afgedwongen door restricties) vereist is, en biedt een competitief alternatief voor algemene solvers zoals IPOPT en bestaande AL-methoden zoals Percival. De auteurs merken bescheiden op dat hoewel de huidige implementatie veelbelovende prestaties laat zien, toekomstig werk de schaalbaarheid moet aanpakken via limited-memory varianten en adaptieve sampling voor grote residu-sets.