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

Cet article établit, pour la première fois, la convergence des algorithmes pratiques de point proximal inexact et de Tseng pour la résolution d'inclusions monotones dans les espaces de Hilbert sous des erreurs non sommables en exploitant la régularisation de Tikhonov, les propriétés de contraction et la théorie de la R-continuité.

L'essentiel

Imaginez que vous essayez de trouver le centre exact d'une pièce sombre et brumeuse (la « solution »). Vous avez une boussole (un algorithme) qui vous oriente vers le centre. Dans un monde parfait, votre boussole serait sans faille et vous marcheriez droit vers le centre.

Cependant, dans le monde réel, votre boussole est un peu instable. Parfois, elle pointe légèrement à gauche, parfois légèrement à droite. Cette « instabilité » est ce que les mathématiciens appell(ent) l'erreur.

Pendant longtemps, les mathématiciens ont cru que pour que vous finissiez par atteindre le centre exact, ces erreurs d'instabilité devaient devenir de plus en plus petites jusqu'à disparaître complètement. Ils pensaient que le montant total du « vacillement » durant tout votre voyage devait s'additionner pour former un nombre minuscule et fini. Si le vacillement continuait à un niveau constant et notable indéfiniment, ils pensaient que vous ne cesseriez jamais de errer en cercles et que vous n'arriveriez jamais à destination.

Ce document dit : « Pas nécessairement pour une solution pratique, mais attention à la nuance. »

Les auteurs, Ba Khiet Le, Boris S. Mordukhovich et Michel Théra, ont découvert une nouvelle façon de naviguer qui fonctionne même si votre boussole continue de vaciller avec une quantité d'erreur constante et non nulle. Voici comment ils ont procédé, en utilisant des métaphores simples :

1. Le Problème : La règle de la « sommabilité »

Traditionnellement, pour garantir que vous atteigniez le centre exact, la règle était : Les erreurs doivent finir par disparaître.
Considérez cela comme marcher vers une cible tout en étant poussé par le vent. Si le vent faiblit de plus en plus jusqu'à s'arrêter, vous atteindrez finalement la cible exacte. Mais si le vent continue de souffler à une vitesse constante et agaçante (erreur non sommable), les mathématiques traditionnelles disaient que vous n'y arriveriez jamais.

2. La Solution : Ajouter une « Attraction Magnétique » (Régularisation de Tikhonov)

L'arme secrète des auteurs est la régularisation de Tikhonov.
Imaginez qu'au lieu de simplement marcher sur un sol plat, vous marchez sur une pente douce et courbe qui mène directement au centre. Même si le vent (l'erreur) continue de vous pousser sur le côté, la pente (l'« attraction » mathématique) vous ramène constamment vers le chemin.

Dans leur mathématique, ils ajoutent une petite « force » artificielle (représentée par $\epsilon$) au problème. Cette force rend le paysage « plus escarpé » et mieux défini. Elle transforme le sol plat et glissant en une forme de bol. Cependant, voici la nuance cruciale : même si vous êtes poussé hors de votre trajectoire par une erreur constante, la forme du bol ne vous permet pas de vous arrêter exactement au centre. Au lieu de cela, elle garantit que vous ne vous égarerez pas indéfiniment ; vous vous installerez dans une petite zone autour du centre et vous continuerez à « osciller » légèrement autour de ce point, sans jamais toucher le centre exact.

3. Les Deux Algorithmes : Le Randonneur et le Guide

Le papier teste cette idée sur deux types spécifiques de « randonneurs » (algorithmes) :

• L'Algorithme du Point Proximal Inexact (IPPA) : C'est comme un randonneur qui fait un pas, vérifie sa carte et corrige sa trajectoire. Les auteurs montrent que même si la carte présente un léger flou constant, la « pente magnétique » garantit que le randonneur finit par rester très près de la cible, oscillant dans un périmètre sûr, même s'il n'atteint jamais le point zéro exact.
• L'Algorithme de Tseng Inexact (ITA) : Il s'agit d'un randonneur plus complexe qui doit gérer deux types de terrains différents en même temps (deux opérateurs mathématiques différents). Les auteurs montrent qu'avec cette complexité supplémentaire et des erreurs constantes, la « pente magnétique » fonctionne toujours pour maintenir le randonneur dans une zone stable et proche de l'objectif, sans convergence parfaite.

4. Le Filet de Sécurité de la « R-continuité »

Pour prouver que cela fonctionne, ils utilisent un concept appelé R-continuité.
Considérez cela comme un filet de sécurité qui dit : « Si vous êtes proche de la cible, vos pas seront prévisibles. » Cela garantit que l'« attraction magnétique » ne se comporte pas de manière erratique. Tant que la carte ne tourne pas soudainement de façon folle près du centre, le randonneur restera à une distance prévisible de l'objectif, oscillant dans une zone stable.

5. Le Résultat : « Assez bien » et stable, mais pas « Exact »

Le papier prouve qu'avec cette nouvelle méthode :

• Vous n'avez pas besoin que les erreurs disparaissent.
• Vous n'avez pas besoin que les erreurs s'additionnent pour former un nombre minuscule (la condition de « sommabilité »).
• Vous avez juste besoin que les erreurs restent dans une limite fixe et gérable (comme une boussole qui est toujours décalée de pas plus de 2 degrés).

Si vous réglez vos paramètres correctement, le randonneur cessera de s'éloigner et s'installera dans une zone stable très proche de la véritable cible. Il continuera à vaciller légèrement autour de cette zone, mais il ne s'éloignera jamais. Le papier appelle cela une « solution approximative stable ».

Note importante : Si vous voulez atteindre le centre exact (convergence parfaite), vous devez toujours utiliser l'ancienne règle où les erreurs doivent finir par disparaître (sommabilité). Mais dans la pratique, comme les ordinateurs ont toujours un peu de « bruit » ou d'« erreur d'arrondi » qui ne disparaît jamais totalement, l'approche de ce papier est plus réaliste. Elle utilise une règle simple et facile à vérifier : « Gardez chaque erreur en dessous d'une petite limite fixe ». Cela permet d'obtenir un résultat fiable et pratique, même si l'erreur ne s'annule jamais.

Pourquoi cela importe (selon le papier)

Dans les calculs informatiques du monde réel, il est souvent impossible de faire disparaître complètement les erreurs. Les ordinateurs ont des limites ; ils ont toujours un peu de « bruit » qui ne disparaît jamais totalement.

Ce papier affirme qu'en utilisant leur technique de « pente magnétique », nous pouvons faire confiance à ces algorithmes pour trouver des réponses stables et suffisamment bonnes, même lorsque les erreurs de l'ordinateur sont tenaces. Cela déplace l'attention de la « précision parfaite » (qui est impossible avec des erreurs constantes) vers des « résultats stables et pratiques » où l'on sait exactement à quelle distance on se trouve de la solution idéale.

En résumé : Le papier nous enseigne que même si vos outils sont imparfaits et que les erreurs ne s'arrêtent jamais, vous pouvez quand même trouver une position stable et très proche de la solution en changeant la forme du problème. Vous ne toucherez pas le centre exact (cela nécessiterait que les erreurs s'annulent), mais vous resterez dans une petite zone sûre autour de lui, oscillant légèrement mais sans jamais vous perdre.

Résumé technique

Résumé Technique : Algorithmes de Point Proximal Inexact et de Tseng avec Erreurs Non Sommables

Énoncé du Problème
L'article traite du problème de résolution d'inclusions monotones de la forme $0 \in Ax$ dans un espace de Hilbert réel $H$, où $A: H \rightrightarrows H$ est un opérateur maximal monotone à valeurs multiples. L'objectif principal est l'étude de la convergence de versions inexactes de deux algorithmes classiques : l'Algorithme du Point Proximal (PPA) et l'Algorithme de Tseng (pour les inclusions composées $0 \in Ax + Bx$).

Une contrainte critique de ce travail est le traitement des erreurs de calcul. Contrairement à la majeure partie de la littérature existante, qui suppose que les séquences d'erreurs sont sommables (c'est-à-dire $\sum \|y_k\| < \infty$, impliquant que les erreurs tendent vers zéro asymptotiquement), cet article étudie des algorithmes sous l'effet d'erreurs bornées et non sommables. Plus précisément, la séquence d'erreurs $(y_k)$ satisfait $\|y_k\| \le \delta$ pour une tolérance $\delta > 0$ fixée. Cette condition répond à une motivation pratique : en calcul numérique, les erreurs $y_k$ ne tendent généralement pas vers zéro. Les critères d'erreur relatifs, bien que théoriquement puissants, sont souvent difficiles à vérifier en pratique, tandis que les critères d'erreurs absolument bornés sont facilement vérifiables. Ce travail adopte cette dernière condition réaliste.

Méthodologie
Les auteurs proposent une approche novatrice qui évite de dépendre de la sommabilité des erreurs. Au lieu de cela, la méthodologie repose sur trois composantes fondamentales :

1. Régularisation de Tikhonov : Le problème d'inclusion original est régularisé par l'ajout d'un terme de forte monotonie $\epsilon I$ (où $\epsilon > 0$). Pour le PPA, l'opérateur devient $\tilde{A} = A + \epsilon I$. Pour le problème composé, l'inclusion régularisée est $0 \in \tilde{A}x + Bx$. Cette régularisation garantit que les opérateurs résolvants associés possèdent des propriétés de contraction forte.
2. Propriétés de Contraction : En utilisant la forte monotonie induite par le terme de régularisation, les auteurs démontrent que les opérateurs résolvants (et la mise en correspondance de Tseng associée) deviennent contractants. Cela permet de contrôler la propagation de l'erreur sans exiger que les erreurs tendent vers zéro.
3. Théorie de la R-continuité : L'analyse de la convergence s'appuie sur la théorie récemment développée de la R-continuité pour les applications à valeurs multiples. Plus précisément, les auteurs supposent que l'opérateur inverse (par exemple, $A^{-1}$ ou $(A+B)^{-1}$) est R-continu à l'origine. Cette propriété permet aux auteurs de borner la distance entre la solution du problème régularisé et l'ensemble des solutions du problème original.

Contributions Clés et Résultats

• Algorithme du Point Proximal Inexact (IPPA) :
  L'article établit la stabilité de l'IPPA défini par $x_{k+1} = J_{\gamma \tilde{A}}x_k + y_{k+1}$ sous l'hypothèse d'une erreur bornée $\|y_{k+1}\| \le \delta$. Il est crucial de noter que, sous des erreurs non sommables, la séquence $(x_k)$ ne converge pas vers une solution exacte de l'inclusion originale. Au lieu de cela, les itérés restent asymptotiquement dans un voisinage borné de l'ensemble des solutions $S = \text{zer}(A)$. La vraie convergence faible vers un point solution n'est garantie que sous la condition classique d'erreurs sommables ($\sum \|y_k\| < \infty$), laquelle n'est pas supposée ici.

  • Résultat : Les auteurs dérivent une borne supérieure constructive de la distance asymptotique à l'ensemble des solutions :
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + \gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
    où $\rho$ est le module de R-continuité de $A^{-1}$ en 0, et $a$ est la norme de l'élément de norme minimale dans $S$. Cette borne définit une "solution approchée" au sens d'une stabilité dans un voisinage explicite, et non d'une convergence ponctuelle.
  • Condition de Précision : En choisissant $\delta = \epsilon^2$, la borne s'annule lorsque $\epsilon \to 0$, garantissant que l'algorithme peut produire des itérés arbitrairement proches de l'ensemble des solutions, bien que la séquence elle-même ne converge pas vers un point unique sans hypothèses supplémentaires sur les erreurs.

• Algorithme de Tseng Inexact (ITA) :
  L'approche est étendue au problème composé $0 \in Ax + Bx$, où $B$ est une application à valeur unique, monotone et Lipschitzienne. L'ITA est appliqué au problème régularisé par Tikhonov.

  • Résultat : Sous l'hypothèse que $(A+B)^{-1}$ est R-continu en 0, les auteurs prouvent que la séquence de l'ITA ne converge pas vers une solution exacte, mais reste asymptotiquement bornée par la distance suivante à l'ensemble des solutions $S$ :
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + 2\gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
  • Similairement à l'IPPA, fixer $\delta = \epsilon^2$ permet d'obtenir une approximation de l'ensemble des solutions d'une précision arbitraire lorsque le paramètre de régularisation $\epsilon$ tend vers zéro, sans pour autant assurer la convergence de la suite des itérés vers un point spécifique.

Signification et Revendications
L'article affirme être le premier dans la littérature à établir la stabilité et les bornes d'erreur explicites pour des versions inexactes pratiques des algorithmes PPA et Tseng sous la seule hypothèse d'erreurs bornées et non sommables.

Les auteurs soulignent que leur analyse révèle que la forte monotonie induite par le terme de régularisation de Tikhonov, plutôt que la classique sommabilité des erreurs, est le mécanisme essentiel assurant la stabilité de ces algorithmes dans un cadre d'erreurs persistantes. Ils soutiennent que l'hypothèse standard de sommabilité est souvent difficile à garantir en pratique, alors que la condition d'erreur bornée est plus réaliste sur le plan computationnel.

Les techniques proposées sont présentées comme un cadre flexible pouvant être étendu pour analyser d'autres algorithmes inexacts pour des problèmes d'optimisation impliquant des perturbations non sommables. L'article ne propose pas de nouvelles applications ou de validations expérimentales, mais se concentre strictement sur la justification théorique de ces algorithmes sous des conditions d'erreurs relaxées, en clarifiant que la convergence vers une solution exacte n'est pas atteinte sans la condition de sommabilité des erreurs.