Average block nonlinear Kaczmarz methods with adaptive momentum for nonlinear systems of equations

Probleemstelling

Het artikel richt zich op het oplossen van grote, niet-lineaire stelsels vergelijkingen van de vorm $F(x) = 0$, waarbij $F: \mathbb{R}^n \to \mathbb{R}^m$ een niet-lineaire vectorfunctie is. Dergelijke systemen komen veel voor in toepassingen zoals elektrische impedantie-tomografie, circuitontwerp en machine learning.

Bestaande methoden hebben beperkingen:

• Klassieke iteratieve methoden (zoals Newton-achtige methoden) zijn vaak te rekenintensief of memory-intensief voor grote schalen.
• Niet-lineaire Kaczmarz-methoden (zoals NK, NRK, NGRKm) zijn efficiënter maar hebben twee grote nadelen:
  1. Ze updaten de oplossing op basis van slechts één vergelijking per iteratie, wat leidt tot een verslechterende convergentiesnelheid naarmate het probleem groter wordt.
  2. De keuze van parameters (zoals stapgrootte $\alpha$ en momentum $\beta$) mist vaak theoretische onderbouwing en vereist handmatige tuning.
• Bestaande blok-methoden (zoals MRBNK) gebruiken informatie van meerdere vergelijkingen, maar vereisen de berekening van de Moore-Penrose pseudo-inversie van een submatrix van de Jacobiaan, wat de rekenkosten per iteratie te hoog maakt.

Methodologie

De auteurs introduceren een nieuwe familie van methoden, genaamd ABNKAm (Average Block Nonlinear Kaczmarz with Adaptive Momentum). De kern van de methode bestaat uit drie componenten:

1. Gemiddelde Blok-strategie (Averaging Block):
   In plaats van één vergelijking te gebruiken, selecteert de methode een subset van indices $J_k$ (op basis van een "greedy" criterium dat vergelijkingen met grote residuen prioriteert). De update wordt berekend als een gewogen gemiddelde van de projecties op deze vergelijkingen. Dit vermijdt de dure pseudo-inversie en houdt de rekenkosten laag (alleen vector-inproducten).

2. Momentum-versnelling (Heavy Ball Momentum):
   Er wordt een momentum-term $\beta_k(x_k - x_{k-1})$ toegevoegd aan de iteratieformule. Dit helpt om oscillaties te dempen en de convergentie te versnellen door gebruik te maken van de richting van vorige iteraties.

3. Adaptieve Parameterkeuze:
   Dit is de belangrijkste innovatie. In plaats van vaste of handmatig gekozen waarden voor de stapgrootte $\alpha_k$ en momentum $\beta_k$, worden deze adaptief bepaald op basis van de huidige iteratie-informatie.

   • De auteurs minimaliseren theoretisch de fout $\|x_{k+1} - x^*\|^2$ om optimale waarden voor $\alpha_k$ en $\beta_k$ af te leiden.
   • Omdat de ware oplossing $x^*$ onbekend is, wordt de niet-lineaire operator $F$ gelokaliseerd via Taylor-expansie om benaderingen te maken die alleen afhankelijk zijn van bekende grootheden ($x_k, x_{k-1}, F(x_k)$).
   • Een hybride strategie (Algorithm 2.2) zorgt voor stabiliteit: als de adaptieve berekening numeriek instabiel wordt (bijv. als de noemer te klein is), schakelt de methode over naar een veiligere, momentum-vrije update.

Belangrijkste Bijdragen

1. Nieuw Algoritme (ABNKAm): Een unificatie van blok-averaging en momentum-versnelling met een volledig adaptieve strategie voor stapgrootte en momentum. Het algoritme vereist slechts minimaal aantal inproducten per iteratie, wat de rekencomplexiteit en het geheugengebruik drastisch verlaagt.
2. Rigoureuze Convergentieanalyse: De auteurs bewijzen dat het algoritme onder milde aannames (zoals een lokale tangentiële kegelvoorwaarde) exponentieel convergeert naar de unieke oplossing die het dichtst bij het startpunt ligt. Ze tonen aan dat de convergentiesnelheid van ABNKAm strikt beter is dan die van bestaande methoden zonder momentum.
3. Theoretische Rechtvaardiging van Versnelling: Er wordt een theoretische onderbouwing gegeven voor het versnellende effect van de momentum-term in de context van niet-lineaire blok-methoden.

Resultaten (Numerieke Experimenten)

De auteurs hebben de methode getest op vijf verschillende niet-lineaire problemen (o.a. Rosenbrock, Cragg-Levy, Chandrasekhar H-equation) met schalen variërend van $10^3$ tot $10^6$ vergelijkingen. De prestaties werden vergeleken met bestaande methoden zoals ABNK2, MRBNK, RB-CNK en NGRKm.

• Iteratie-aantal en Tijd: ABNKAm overtreft alle concurrenten aanzienlijk. In veel gevallen convergeert het in een fractie van het aantal iteraties dat andere methoden nodig hebben.
• Schaalbaarheid: De "speed-up ratio" (versnelling ten opzichte van andere methoden) neemt toe naarmate het probleem groter wordt. Voor grote problemen ($10^6$) is ABNKAm tot 700 keer sneller dan sommige concurrenten.
• Robuustheid:
  • Bij problemen waar andere methoden divergeren of vastlopen (zoals het "Extended Powell badly scaled problem"), convergeert ABNKAm stabiel.
  • De methode is effectief zowel voor systemen met een dunne (sparse) Jacobiaan als voor systemen met een dichte Jacobiaan.
• Oscillaties: Hoewel de residuen soms oscilleren (het "seesaw-effect"), convergeert de oplossingreeks consistent naar de ware oplossing, wat wordt ondersteund door de momentum-term.

Betekenis en Conclusie

Dit werk vult een belangrijke lacune in de literatuur over iteratieve methoden voor niet-lineaire systemen. Het combineert de rekenefficiëntie van blok-methoden (zonder pseudo-inversie) met de versnellende kracht van momentum, terwijl het de last van handmatige parameter-tuning wegneemt door een adaptieve strategie.

De ABNKAm-methode biedt een nieuwe staat van de kunst voor het oplossen van grote, slecht gestelde en niet-lineaire systemen. De resultaten tonen aan dat het niet alleen theoretisch waardevol is, maar ook in de praktijk superieur presteert in termen van snelheid, stabiliteit en schaalbaarheid, wat het een ideale kandidaat maakt voor complexe toepassingen in wetenschap en engineering.