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

Diese Arbeit stellt zum ersten Mal die Konvergenz praktischer ungenauer Proximal-Punkt- und Tseng-Algorithmen zur Lösung monotoner Inklusionen in Hilbert-Räumen unter nicht-summierbaren Fehlern unter Ausnutzung von Tikhonov-Regularisierung, Kontraktionseigenschaften und R-Kontinuitätstheorie fest.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, die exakte Mitte eines dunklen, nebligen Raumes (die „Lösung") zu finden. Sie haben einen Kompass (einen Algorithmus), der Sie zur Mitte führt. In einer perfekten Welt wäre Ihr Kompass makellos, und Sie würden geradewegs zur Mitte gehen.

In der realen Welt ist Ihr Kompass jedoch etwas unruhig. Manchmal zeigt er leicht nach links, manchmal leicht nach rechts. Diese „Unruhe" ist das, was Mathematiker als Fehler bezeichnen.

Lange Zeit glaubten Mathematiker, dass Sie das Zentrum nur dann erreichen können, wenn die Fehler immer kleiner werden, bis sie vollständig verschwinden. Sie dachten, die gesamte Menge des „Wackelns" auf Ihrer gesamten Reise müsste eine winzige, endliche Zahl ergeben. Wenn das Wackeln ewig mit einem stetigen, spürbaren Niveau fortbestehen würde, dachten sie, Sie würden niemals aufhören, im Kreis zu wandern.

Dieses Paper sagt: „Nicht unbedingt – aber mit einer wichtigen Einschränkung."

Die Autoren, Ba Khiet Le, Boris S. Mordukhovich und Michel Théra, haben einen neuen Weg der Navigation entdeckt. Das Wichtigste vorab: Wenn die Fehler konstant bleiben (nicht verschwinden), erreichen Sie niemals die exakte Mitte. Sie werden nicht genau im Zentrum ankommen. Stattdessen pendeln Sie sich in einem kleinen, sicheren Bereich um das Zentrum ein und wackeln dort für immer leicht hin und her. Sie erreichen eine stabile „gute genug" Position, aber nicht den perfekten Punkt.

Hier ist, wie sie es geschafft haben, unter Verwendung einfacher Metaphern:

1. Das Problem: Die „Summierbarkeit"-Regel vs. Stetige Fehler

Traditionell galt als Regel, um das Zentrum exakt zu erreichen: Die Fehler müssen schließlich verschwinden.
Stellen Sie sich das wie das Gehen auf ein Ziel zu vor, während Sie vom Wind gestoßen werden. Wenn der Wind immer schwächer wird, bis er aufhört, werden Sie das Ziel schließlich exakt erreichen.
Aber wenn der Wind ständig mit einer stetigen, nervigen Geschwindigkeit weht (nicht-verschwindende Fehler), besagte die traditionelle Mathematik, dass Sie niemals dort ankommen würden. Sie würden ewig um das Ziel herumwandern, ohne es zu berühren.

2. Die Lösung: Ein „magnetischer Zug" (Tikhonov-Regularisierung)

Das Geheimwerkzeug der Autoren ist die Tikhonow-Regularisierung.
Stellen Sie sich vor, anstatt auf einem flachen Boden zu gehen, gehen Sie auf einem sanften, gekrümmten Hang, der direkt zur Mitte führt. Selbst wenn der Wind (der Fehler) Sie ständig zur Seite stößt, zieht der Hang (der mathematische „Zug") Sie ständig zurück auf den Pfad.

In ihrer Mathematik fügen sie eine kleine, künstliche „Kraft" (dargestellt durch $\epsilon$) zum Problem hinzu. Diese Kraft macht die Landschaft „steiler" und definierter. Sie verwandelt den flachen, rutschigen Boden in eine Schalenform. Selbst wenn Sie durch einen stetigen Fehler vom Kurs abgetrieben werden, sorgt die Schalenform dafür, dass Sie nicht ewig ziellos umherwandern. Sie pendeln sich jedoch nicht exakt im Zentrum ein, sondern bleiben in einem kleinen, vorhersehbaren Radius um die Mitte herum „gefangen" und wackeln dort weiter.

3. Die zwei Algorithmen: Der Wanderer und der Führer

Das Paper testet diese Idee an zwei spezifischen Arten von „Wanderern" (Algorithmen):

• Der ungenaue Proximal-Punkt-Algorithmus (IPPA): Dies ist wie ein Wanderer, der einen Schritt macht, die Karte prüft und seinen Pfad korrigiert. Die Autoren zeigen, dass selbst wenn die Karte eine konstante, kleine Unschärfe (Fehler) aufweist, der „magnetische Hang" sicherstellt, dass der Wanderer sehr nah am Ziel landet – aber er wird dort nicht stillstehen; er wird in einem kleinen Bereich um das Ziel herum hin und her wackeln.
• Der ungenaue Tseng-Algorithmus (ITA): Dies ist ein komplexerer Wanderer, der mit zwei verschiedenen Arten von Gelände gleichzeitig fertig werden muss. Auch hier zeigt sich: Selbst mit konstanten Fehlern hält der „magnetische Hang" den Wanderer in einem stabilen, kleinen Bereich um das Ziel, ohne dass er jemals exakt das Zentrum berührt.

4. Das Sicherheitsnetz der „R-Kontinuität"

Um zu beweisen, dass dies funktioniert, verwenden sie ein Konzept namens R-Kontinuität.
Betrachten Sie dies als ein Sicherheitsnetz, das besagt: „Wenn du nah am Ziel bist, sind deine Schritte vorhersehbar." Es garantiert, dass der „magnetische Zug" nicht erratisch reagiert. Solange die Karte in der Nähe der Mitte nicht plötzlich auf eine verrückte Weise verdreht wird, bleibt der Wanderer innerhalb einer berechenbaren Distanz zum Ziel. Er wird nicht davongetragen, aber er wird auch nicht exakt anhalten.

5. Das Ergebnis: „Gut genug" ist gut genug (aber nicht perfekt)

Das Paper beweist, dass mit dieser neuen Methode:

• Die Fehler nicht verschwinden müssen.
• Die Fehler nicht zu einer winzigen Zahl zusammengefasst werden müssen.
• Sie lediglich eine feste, handhabbare Grenze einhalten müssen (wie ein Kompass, der immer um maximal 2 Grad daneben liegt).

Wenn Sie Ihre Parameter korrekt setzen, wird der Wanderer aufhören, sich weit vom Ziel zu entfernen, und sich innerhalb eines kleinen, vorhersehbaren Abstands zum wahren Zentrum einpendeln. Aber er wird dort nicht stillstehen. Er wird für immer leicht um dieses Zentrum herum wackeln. Das Paper nennt dies eine „approximative Lösung".

Warum das wichtig ist (laut dem Paper)
In realen Computerberechnungen ist es oft unmöglich, Fehler vollständig verschwinden zu lassen. Computer haben Grenzen; sie haben immer ein wenig „Rauschen" oder „Rundungsfehler", die niemals ganz verschwinden.

Früher dachte man, man brauche eine komplizierte Regel, bei der die Fehler im Laufe der Zeit immer kleiner werden müssen (summierbar), um eine Lösung zu finden. Dieses Paper zeigt jedoch, dass eine viel einfachere Regel ausreicht: Halten Sie jeden einzelnen Fehler einfach unter einer festen, kleinen Obergrenze. Das ist leicht zu überprüfen.

Da reale Fehler nie ganz verschwinden, brauchen wir praktische Regeln. Dieses Paper beweist, dass wir durch den Einsatz ihrer „magnetischen Hang"-Technik darauf vertrauen können, dass diese Algorithmen selbst dann stabile, „gute genug" Antworten finden, wenn die Fehler hartnäckig sind. Wir erreichen zwar nicht die mathematisch exakte Mitte (dafür bräuchten wir die alten, verschwindenden Fehler), aber wir landen sicher in einem kleinen, kontrollierbaren Bereich direkt daneben.

Zusammenfassend: Das Paper lehrt uns, dass man selbst dann eine stabile Lösung finden kann, wenn die Werkzeuge unvollkommen sind und die Fehler niemals aufhören. Indem man die Form des Problems so verändert, dass die Fehler einen nicht zu weit vom Kurs abbringen, bleibt man in einem sicheren, kleinen Radius um das Ziel – auch wenn man das Ziel nie exakt berührt.

Technische Zusammenfassung

Technisches Resümee: Ungenaue Proximal-Punkt- und Tseng-Algorithmen mit nicht-summierbaren Fehlern

Problemstellung
Die vorliegende Arbeit befasst sich mit der Lösung von monotonen Inklusionen der Form $0 \in Ax$ in einem reellen Hilbertraum $H$, wobei $A: H \rightrightarrows H$ ein mehrwertiger maximal monotoner Operator ist. Der primäre Fokus liegt auf der Analyse praktischer, ungenauer Versionen zweier klassischer Algorithmen: des Proximal-Punkt-Algorithmus (PPA) und des Tseng-Algorithmus (für zusammengesetzte Inklusionen $0 \in Ax + Bx$).

Eine entscheidende Einschränkung dieser Arbeit ist die Behandlung von Rechenfehlern. Im Gegensatz zur bestehenden Literatur, welche davon ausgeht, dass Fehlerserien summierbar sind (d. h. $\sum \|y_k\| < \infty$, was impliziert, dass Fehler asymptotisch verschwinden), untersucht dieses Papier Algorithmen unter beschränkten, nicht-summierbaren Fehlern. In der Praxis tendieren Rechenfehler $y_k$ aufgrund endlicher Präzision oft nicht gegen Null, sondern bleiben beschränkt. Während relative Fehlerkriterien in der Praxis schwer zu verifizieren sind, bietet die Bedingung absoluter Fehlerbeschränkung ($\|y_k\| \le \delta$ für eine feste Toleranz $\delta > 0$) ein leicht überprüfbares und realistisches Modell. Speziell erfüllt die Fehlerserie $(y_k)$ diese Bedingung, was bedeutet, dass die Fehler fortbestehen können, solange sie innerhalb einer festen Schranke bleiben.

Methodik
Die Autoren schlagen einen neuartigen Ansatz vor, der nicht auf der Summierbarkeit von Fehlern beruht. Stattdessen stützt sich die Methodik auf drei Kernkomponenten:

1. Tikhonov-Regularisierung: Das ursprüngliche Inklusionsproblem wird durch das Hinzufügen eines streng monotonen Terms $\epsilon I$ (wobei $\epsilon > 0$) regularisiert. Für den PPA lautet der Operator $\tilde{A} = A + \epsilon I$. Für das zusammengesetzte Problem ist die regularisierte Inklusion $0 \in \tilde{A}x + Bx$. Diese Regularisierung stellt sicher, dass die zugehörigen Resolventenoperatoren starke Kontraktions-Eigenschaften besitzen.
2. Kontraktionseigenschaften: Durch die Nutzung der durch den Regularisierungsterm induzierten strengen Monotonie zeigen die Autoren, dass die Resolventenoperatoren (und die zugehörige Tseng-Abbildung) kontraktiv werden. Dies ermöglicht die Kontrolle der Fehlerfortpflanzung, ohne dass die Fehler gegen Null deklinieren müssen.
3. R-Kontinuitätstheorie: Die Konvergenzanalyse nutzt die kürzlich entwickelte Theorie der R-Kontinuität für mehrwertige Abbildungen. Konkret nehmen die Autoren an, dass der Inversoperator (z. B. $A^{-1}$ oder $(A+B)^{-1}$) R-stetig am Ursprung ist. Diese Eigenschaft erlaubt es den Autoren, den Abstand zwischen der Lösung des regularisierten Problems und der Lösungsmenge des ursprünglichen Problems zu beschränken.

Wesentliche Beiträge und Ergebnisse

• Ungenauer Proximal-Punkt-Algorithmus (IPPA):
  Das Papier etabliert die Stabilität des IPPA, definiert durch $x_{k+1} = J_{\gamma \tilde{A}}x_k + y_{k+1}$ unter der Annahme beschränkter Fehler $\|y_{k+1}\| \le \delta$. Hier stellt $y_{k+1}$ den per-Iterationen-Rechenfehler dar, der durch endliche Präzision entsteht und strikt von der Toleranz $\delta$ beschränkt ist, ohne gegen Null zu konvergieren.

  • Ergebnis: Unter der Annahme beschränkter, nicht-summierbarer Fehler konvergieren die Iterierten $(x_k)$ nicht notwendigerweise zu einem exakten Lösungspunkt der ursprünglichen Inklusion. Stattdessen bleibt die Folge asymptotisch innerhalb eines explizit berechenbaren Abstands zur Lösungsmenge $S = \text{zer}(A)$. Die Autoren leiten eine konstruktive obere Schranke für diesen asymptotischen Abstand her:
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + \gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
    wobei $\rho$ das Modul der R-Kontinuität von $A^{-1}$ bei 0 ist und $a$ die Norm des Elements mit minimaler Norm in $S$ darstellt. Dies repräsentiert eine stabile "approximative Lösung" im Sinne einer beschränkten Nachbarschaft, nicht jedoch die Konvergenz zu einem spezifischen Punkt.
  • Hinweis zur Konvergenz: Eine echte (schwache) Konvergenz der Folge $(x_k)$ zu einem exakten Lösungspunkt der Inklusion ist unter den hier getroffenen Annahmen nicht gewährleistet. Solch eine stärkere Konvergenzaussage ist nur unter der klassischen Annahme summierbarer Fehler ($\sum \|y_k\| < \infty$) möglich, was in diesem Papier explizit nicht vorausgesetzt wird.
  • Approximationsgüte: Durch die Wahl von $\delta = \epsilon^2$ lässt sich zeigen, dass die obere Schranke für $\epsilon \to 0$ verschwindet. Dies sichert, dass der Algorithmus beliebig genaue approximative Lösungen liefern kann, wenn der Regularisierungsparameter und die Fehlerschranke entsprechend gewählt werden.

• Ungenauer Tseng-Algorithmus (ITA):
  Der Ansatz wird auf das zusammengesetzte Problem $0 \in Ax + Bx$ erweitert, wobei $B$ eindwertig, monoton und Lipschitz-stetig ist. Der ITA wird auf das Tikhonov-regularisierte Problem angewendet.

  • Ergebnis: Unter der Annahme, dass $(A+B)^{-1}$ R-stetig bei 0 ist, beweisen die Autoren, dass die ITA-Folge nicht zu einem exakten Punkt konvergiert, sondern asymptotisch in einer beschränkten Umgebung der Lösungsmenge verbleibt. Die abgeleitete Fehlerschranke lautet:
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + 2\gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
  • Ähnlich wie beim IPPA führt die Einstellung von $\delta = \epsilon^2$ dazu, dass der asymptotische Abstand zur Lösungsmenge gegen Null geht, wenn $\epsilon \to 0$, wobei jedoch auch hier keine Konvergenz der Iterierten selbst zu einem festen Punkt ohne summierbare Fehler garantiert ist.

Bedeutung und Ansprüche
Das Paper beansprucht für sich, das erste in der Literatur zu sein, das die Stabilität praktischer ungenauer PPA- und Tseng-Algorithmen unter der alleinigen Annahme beschränkter, nicht-summierbarer Fehler etabliert.

Die Autoren betonen, dass ihre Analyse zeigt, dass die durch die Tikhonov-Regularisierung induzierte strenge Monotonie und nicht die klassische Summierbarkeit der Fehler der wesentliche Mechanismus ist, der die Stabilität und Wohldefiniertheit dieser Algorithmen gewährleistet. Sie argumentieren, dass die Standardannahme der Summierbarkeit in der Praxis oft schwer zu garantieren ist, während die Bedingung beschränkter Fehler rechnerisch realistisch ist.

Die vorgeschlagenen Techniken werden als flexibler Rahmen präsentiert, der zur Analyse anderer ungenauer Algorithmen für Optimierungsprobleme mit nicht-summierbaren Störungen erweitert werden kann. Das Papier schlägt keine neuen Anwendungen oder experimentellen Validierungen vor, sondern konzentriert sich strikt auf die theoretische Rechtfertigung dieser Algorithmen unter relaxierten Fehlerbedingungen, wobei explizit vermieden wird, eine Konvergenz zu exakten Lösungen zu behaupten, wo diese unter den gegebenen Fehlerannahmen nicht existiert.