Inexact Proximal Point and Tseng Algorithms with Nonsummable Errors to Solve Monotone Inclusions

Dit artikel stelt voor de eerste keer de convergentie vast van praktische onnauwkeurige Proximal Point- en Tseng-algoritmen voor het oplossen van monotone inclusies in Hilbertruimten onder niet-sommeerbare fouten door gebruik te maken van Tikhonov-regularisatie, contractie-eigenschappen en R-continuïteitstheorie.

De kern

Stel je voor dat je probeert het exacte middelpunt te vinden van een donkere, mistige kamer (de "oplossing"). Je hebt een kompas (een algoritme) dat naar het midden wijst. In een perfecte wereld zou je kompas foutloos zijn en zou je recht naar het midden lopen.

Echter, in de echte wereld is je kompas een beetje onrustig. Soms wijst het iets naar links, soms iets naar rechts. Deze "onrustigheid" is wat wiskundigen fout noemen.

Lange tijd geloofden wiskundigen dat om uiteindelijk het midden te bereiken, deze onrustige fouten steeds kleiner moesten worden totdat ze volledig verdwenen. Ze dachten dat de totale hoeveelheid "gezwabber" tijdens je hele reis moest optellen tot een klein, eindig getal. Als de zwabber zich voor altijd op een constant, merkbaar niveau zou voortzetten, dachten ze dat je nooit zou ophouden met rondjes dwalen en je dus nooit bij het doel zou komen.

Dit artikel zegt: "Niet noodzakelijkerwijs, maar je komt ook niet exact aan."

De auteurs, Ba Khiet Le, Boris S. Mordukhovich en Michel Théra, hebben een nieuwe manier van navigeren ontdekt die werkt, zelfs als je kompas blijft trillen met een constante, niet-verdwijnende hoeveelheid fout. Het cruciale punt is echter: je bereikt niet het exacte middelpunt. Je eindigt wel in een stabiele, veilige zone die heel dicht bij het midden ligt, maar je blijft daar een beetje omheen wiebelen. Je komt nooit tot stilstand op het exacte punt, maar je blijft wel binnen een voorspelbare afstand ervan.

Hier is hoe ze dit deden, met behulp van eenvoudige metaforen:

1. Het Probleem: De "Sommeerbare" Regel

Traditioneel was de regel om te garanderen dat je het exacte midden vindt: De fouten moeten uiteindelijk verdwijnen.
Denk hierbij aan het lopen naar een doel terwijl je door de wind wordt geduwd. Als de wind steeds zwakker wordt totdat hij stopt, zul je het doel uiteindelijk precies bereiken. Maar als de wind op een constante, irritante snelheid blijft waaien (niet-sommeerbare fout), zeiden traditionele wiskundigen dat je er nooit zou komen.

2. De Oplossing: Een "Magnetische Trek" Toevoegen (Tikhonov-regularisatie)

Het geheime wapen van de auteurs is Tikhonov-regularisatie.
Stel je voor dat je, in plaats van alleen op een vlakke vloer te lopen, op een flauwe, gebogen helling loopt die rechtstreeks naar het midden leidt. Zelfs als de wind (de fout) je zijwaarts blijft duwen, trekt de helling (de wiskundige "trek") je constant terug naar het pad.

In hun wiskunde voegen ze een kleine, kunstmatige "kracht" (vertegenwoordigd door $\epsilon$) toe aan het probleem. Deze kracht maakt het landschap "steiler" en meer gedefinieerd. Het verandert de vlakke, gladde grond in een komvorm. Zelfs als je door een constante fout uit je koers wordt geduwd, zorgt de komvorm ervoor dat je niet eeuwig blijft dwalen; je nestelt je in een klein gebiedje heel dicht bij het midden. Je blijft daar wel een beetje trillen, maar je zakt nooit verder weg.

3. De Twee Algoritmen: De Wandelaar en de Gids

Het artikel test dit idee op twee specifieke soorten "wandelaars" (algoritmen):

• Het Inexact Proximal Point Algorithm (IPPA): Dit is als een wandelaar die een stap zet, de kaart controleert en zijn pad corrigeert. De auteurs laten zien dat zelfs als de kaart een constante, kleine onscherpte heeft (fout), de "magnetische helling" ervoor zorgt dat de wandelaar niet wegwaait, maar binnen een kleine, vaste afstand van het doel blijft hangen.
• Het Inexact Tseng Algorithm (ITA): Dit is een complexere wandelaar die met twee verschillende soorten terrein tegelijkertijd te maken krijgt. De auteurs laten zien dat zelfs met deze extra complexiteit en constante fouten, de "magnetische helling" nog steeds werkt om de wandelaar binnen een veilige grens te houden.

4. Het "R-continuïteit" Veiligheidsnet

Om te bewijzen dat dit werkt, gebruiken ze een concept genaamd R-continuïteit.
Beschouw dit als een veiligheidsnet dat zegt: "Als je dicht bij het doel bent, zijn je stappen voorspelbaar." Het garandeert dat de "magnetische trek" niet grillig gaat gedragen. Zolang de kaart niet plotseling in de buurt van het midden op een gekke manier draait, zal de wandelaar binnen een voorspelbare afstand van het doel blijven, ook al blijft hij daar een beetje heen en weer wiebelen.

5. Het Resultaat: "Goed Genoeg" is Echt "Goed Genoeg"

Het artikel bewijst dat met deze nieuwe methode:

• Je de fouten niet hoeft te laten verdwijnen.
• Je niet het exacte middelpunt bereikt (dat vereist dat de fouten volledig stoppen).
• Je wel een stabiele, "goed genoeg" positie bereikt die binnen een vaste, beheersbare limiet van het midden blijft liggen (zoals een kompas dat altijd maximaal 2 graden afwijkt, waardoor je nooit verder dan 2 graden van het doel komt).

Als je je parameters correct instelt, stopt de wandelaar met weg te dwalen en vestigt hij zich in een kleine, voorspelbare buurt van het ware middelpunt. Hij blijft daar wel een beetje trillen, maar hij raakt niet kwijt.

Waarom dit ertoe doet (volgens het artikel)

In de werkelijke computerberekeningen is het vaak onmogelijk om fouten volledig te laten verdwijnen of om ze te laten optellen tot een minuscuul getal. Computers hebben grenzen; ze hebben altijd een klein beetje "ruis" of "afrondingsfout" die nooit volledig verdwijnt.

Dit artikel leert ons dat we een praktischere regel kunnen gebruiken: "Houd elke fout onder een vaste, kleine limiet." Dit is veel makkelijker te controleren dan te eisen dat fouten uiteindelijk verdwijnen. Door hun "magnetische helling"-techniek te gebruiken, kunnen we deze algoritmen vertrouwen om stabiele resultaten te geven, zelfs wanneer de fouten koppig blijven bestaan. Het verlegt de focus van "perfecte precisie" (exacte oplossing) naar "stabiele, praktische resultaten" (een oplossing die dichtbij genoeg is en daar blijft).

Samenvattend: Het artikel leert ons dat zelfs als je instrumenten imperfect zijn en de fouten nooit stoppen, je de oplossing nog steeds kunt vinden door de vorm van het probleem te veranderen. Je komt niet exact op het middelpunt (dat zou vereisen dat de fouten stoppen), maar je blijft wel veilig en stabiel binnen een heel klein stukje ervan, wat in de praktijk vaak precies is wat je nodig hebt.

Technische samenvatting

Technische Samenvatting: Inexact Proximal Point en Tseng Algoritmen met Niet-sommeerbare Fouten

Probleemstelling
Het artikel behandelt het probleem van het oplossen van monotone inclusies van de vorm $0 \in Ax$ in een reële Hilbertruimte $H$, waarbij $A: H \rightrightarrows H$ een meerwaardige maximaal monotone operator is. De primaire focus ligt op de convergentie van praktische, inexacte versies van twee klassieke algoritmen: het Proximal Point Algoritme (PPA) en het Tseng Algoritme (voor samengestelde inclusies $0 \in Ax + Bx$).

Een cruciale beperking van dit werk is de behandeling van computationele fouten. In tegenstelling van de meeste bestaande literatuur, die ervan uitgaat dat foutensequenties sommeerbaar zijn (d.w.z. $\sum \|y_k\| < \infty$, wat impliceert dat fouten asymptotisch verdwijnen), onderzoekt dit artikel algoritmen onder begrensde, niet-sommeerbare fouten. Specifiek voldoet de foutensequentie $(y_k)$ aan $\|y_k\| \le \delta$ voor een vaste tolerantie $\delta > 0$. Deze conditie is realistischer voor berekeningen met eindige precisie, waar fouten kunnen aanhouden maar wel begrensd blijven. In de praktijk tendert de fout $y_k$ namelijk zelden naar nul; daarom zijn geschikte foutcriteria noodzakelijk. Waar relatieve foutcriteria (die vaak moeilijk te verifiëren zijn) in de literatuur voorkomen, kiest dit werk voor de absoluut begrensde foutconditie, die eenvoudig te verifiëren is en beter aansluit bij de realiteit van numerieke implementaties.

Methodologie
De auteurs stellen een innovatieve aanpak voor die de afhankelijkheid van de sommeerbaarheid van fouten vermijdt. In plaats daarvan steunt de methodologie op drie kerncomponenten:

1. Tikhonov-regularisatie: Het oorspronkelijke inclusieprobleem wordt geregulariseerd door een sterk monotone term $\epsilon I$ toe te voegen (waarbij $\epsilon > 0$). Voor het PPA wordt de operator $\tilde{A} = A + \epsilon I$. Voor het samengestelde probleem is de geregulariseerde inclusie $0 \in \tilde{A}x + Bx$. Deze regularisatie zorgt ervoor dat de geassocieerde resolvent-operatoren sterke contractie-eigenschappen bezitten.
2. Contractie-eigenschappen: Door gebruik te maken van de sterke monotoniciteit die door de regularisatieterm wordt geïnduceerd, tonen de auteurs aan dat de resolvent-operatoren (en de geassocieerde Tseng-mapping) contractief zijn. Dit maakt controle over foutpropagatie mogelijk zonder dat de fouten naar nul hoeven te dalen.
3. R-continuïteitstheorie: De convergentieanalyse maakt gebruik van de recent ontwikkelde theorie van R-continuïteit voor meerwaardige afbeeldingen. Specifiek nemen de auteurs aan dat de inverse operator (bijv. $A^{-1}$ of $(A+B)^{-1}$) R-continu is in de oorsprong. Deze eigenschap stelt de auteurs in staat om de afstand tussen de oplossing van het geregulariseerde probleem en de oplossingsverzameling van het oorspronkelijke probleem te begrenzen.

Belangrijkste Bijdragen en Resultaten

• Inexact Proximal Point Algoritme (IPPA):
  Het artikel vestigt de stabiliteit van de IPPA gedefinieerd door $x_{k+1} = J_{\gamma \tilde{A}}x_k + y_{k+1}$ onder de begrensde fout-aanname $\|y_{k+1}\| \le \delta$, waarbij $y_{k+1}$ de per-iteration computatiefout voorstelt die optreedt bij het evalueren van de resolvent-operator.

  • Resultaat: Onder de aanname van niet-sommeerbare fouten convergeert de sequentie $(x_k)$ niet noodzakelijk naar een exacte oplossing van de oorspronkelijke inclusie. In plaats daarvan blijft de sequentie asymptotisch binnen een expliciet afgebakende afstand van de oplossingsverzameling $S = \text{zer}(A)$. De auteurs leiden een constructieve bovengrens af voor deze asymptotische afstand:
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + \gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
    waarbij $\rho$ de modulus van R-continuïteit is van $A^{-1}$ bij 0, en $a$ de norm is van het element met de minimale norm in $S$.
  • Convergentievoorwaarde: Het verkrijgen van ware (zwakke) convergentie van $x_k$ naar een exacte oplossing vereist de klassieke sommeerbare foutconditie ($\sum \|y_k\| < \infty$); deze sterkere conclusie is in het huidige kader van niet-sommeerbare fouten niet beschikbaar. Echter, door $\delta = \epsilon^2$ te kiezen, verdwijnt de bovengrens wanneer $\epsilon \to 0$, wat garandeert dat het algoritme willekeurig nauwkeurige benaderde oplossingen (in de zin van een begrensd buur) produceert.

• Inexact Tseng Algoritme (ITA):
  De aanpak wordt uitgebreid naar het samengestelde probleem $0 \in Ax + Bx$, waarbij $B$ enkelwaardig, monotoon en Lipschitz-continu is. De ITA wordt toegepast op het Tikhonov-geregulariseerde probleem.

  • Resultaat: Onder de aanname dat $(A+B)^{-1}$ R-continu is in 0, bewijzen de auteurs dat de ITA-sequentie eveneens niet convergeert naar een exacte oplossing, maar asymptotisch binnen een begrensde afstand van $S$ blijft. De afgeleide foutenbovengrens is:
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + 2\gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
  • Net als bij de IPPA levert het instellen van $\delta = \epsilon^2$ convergentie naar een willekeurig nauwkeurige benadering van de oplossingsverzameling naarmate de regularisatieparameter $\epsilon$ naar nul nadert, maar geen convergentie naar een exacte oplossing onder de gegeven foutcondities.

Betekenis en Claims
Het artikel claimt de eerste in de literatuur te zijn die de stabiliteit van praktische inexacte PPA en Tseng algoritmen vaststelt onder de enige aanname van begrensde, niet-sommeerbare fouten.

De auteurs benadrukken dat hun analyse aantoont dat de sterke monotoniciteit geïnduceerd door de Tikhonov-regularisatieterm, in plaats van de klassieke sommeerbaarheid van fouten, het essentiële mechanisme is dat de stabiliteit en welbepaaldheid van deze algoritmen waarborgt. Zij argumenteren dat de standaard aanname van sommeerbaarheid in de praktijk vaak moeilijk te garanderen is, terwijl de conditie van begrensde fouten computationeel realistischer is.

De voorgestelde technieken worden gepresenteerd als een flexibel kader dat kan worden uitgebreid voor het analyseren van andere inexacte algoritmen voor optimalisatiegerelateerde problemen die betrokken zijn bij niet-sommeerbare perturbaties. Het artikel stelt geen nieuwe toepassingen of experimentele validaties voor, maar richt zich strikt op de theoretische rechtvaardiging van deze algoritmen onder versoepelde foutcondities, waarbij expliciet wordt vermeden om convergentie naar een exacte oplossing te claimen wanneer fouten niet-sommeerbaar zijn.