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

Questo articolo stabilisce, per la prima volta, la convergenza di algoritmi pratici di tipo Inexact Proximal Point e di Tseng per la risoluzione di inclusioni monotone in spazi di Hilbert sotto errori non sommabili, sfruttando la regolarizzazione di Tikhonov, le proprietà di contrazione e la teoria della R-continuità.

L'essenziale

Immagina di cercare di trovare il centro esatto di una stanza buia e nebbiosa (la "soluzione"). Hai una bussola (un algoritmo) che ti indica la direzione del centro. In un mondo perfetto, la tua bussola sarebbe impeccabile e cammineresti dritto verso il centro, fermandoti esattamente su di esso.

Tuttavia, nel mondo reale, la tua bussola è un po' instabile. A volte punta leggermente a sinistra, a volte leggermente a destra. Questa "instabilità" è ciò che i matematici chiamano errore.

Per molto tempo, i matematici hanno creduto che, per raggiungere infine il centro esatto, questi errori di instabilità dovessero diventare sempre più piccoli fino a scomparire completamente. Pensavano che l'entità totale dell'oscillazione durante l'intero percorso dovesse sommare un numero minuscolo e finito. Credevano che se l'oscillazione fosse continuata con un livello costante e percepibile per sempre, non saresti mai riuscito a smettere di vagare in cerchio e, soprattutto, non saresti mai arrivato al punto esatto.

Questo articolo dice: "Non necessariamente, ma con una precisazione importante".

Gli autori, Ba Khiet Le, Boris S. Mordukhovich e Michel Théra, hanno scoperto un nuovo modo di navigare che funziona anche se la tua bussola continua a oscillare con una quantità di errore costante e non nulla. Tuttavia, c'è una differenza fondamentale: con errori costanti, non raggiungerai mai il centro esatto. Invece, il metodo garantisce che tu rimanga intrappolato in una piccola zona sicura intorno al centro, oscillando leggermente lì per sempre senza allontanarti troppo.

Ecco come ci sono riusciti, usando metafore semplici:

1. Il Problema: La regola della "Sommabilità"

Tradizionalmente, per garantire di arrivare esattamente al centro, la regola era: Gli errori devono alla fine svanire.
Pensa a questo come al camminare verso un bersaglio mentre vieni spinto dal vento. Se il vento diventa sempre più debole fino a fermarsi, raggiungerai infine il bersaglio esatto e ti fermerai lì. Ma se il vento continua a soffiare a una velocità costante e fastidiosa (errore non sommabile), la matematica tradizionale diceva che non ci arriveresti mai.

2. La Soluzione: Aggiungere una "Attrazione Magnetica" (Regolarizzazione di Tikhonov)

L'arma segreta degli autori è la regolarizzazione di Tikhonov.
Immagina che, invece di camminare su un pavimento piatto, tu stia camminando su una dolce pendenza curva che conduce direttamente al centro. Anche se il vento (l'errore) continua a spingerti lateralmente, la pendenza (l'attrazione matematica) ti trascina costantemente verso il percorso.

Nella loro matematica, aggiungono una piccola "forza" artificiale (rappresentata da $\epsilon$) al problema. Questa forza rende il paesaggio "più ripido" e definito. Trasforma il terreno piatto e scivoloso in una forma a ciotola. Anche se vieni spinto fuori rotta da un errore costante, la forma a ciotola assicura che tu non vaghi all'infinito. Non ti fermerai mai esattamente al centro esatto (perché il vento ti spinge via), ma ti stabilizzerai in un punto molto vicino, oscillando leggermente dentro una piccola area sicura intorno al centro.

3. I Due Algoritmi: L'Escursionista e la Guida

L'articolo testa questa idea su due tipi specifici di "escursionisti" (algoritmi):

• L'Algoritmo del Punto Prossimale Impreciso (IPPA): Questo è come un escursionista che fa un passo, controlla la mappa e corregge il proprio percorso. Gli autori dimostrano che anche se la mappa ha una piccola sfocatura costante (errore), la "pendenza magnetica" assicura che l'escursionista finisca e rimanga molto vicino all'obiettivo, anche se non ci arriva mai perfettamente.
• L'Algoritmo di Tseng Impreciso (ITA): Questo è un escursionista più complesso che deve gestire due tipi diversi di terreno contemporaneamente. Gli autori dimostrano che anche con questa ulteriore complessità e con errori costanti, la "pendenza magnetica" funziona ancora per mantenere l'escursionista nella zona sicura vicino alla destinazione.

4. La Rete di Sicurezza della "R-Continuità"

Per dimostrare che questo funziona, utilizzano un concetto chiamato R-continuità.
Consideralo come una rete di sicurezza che dice: "Se sei vicino al bersaglio, i tuoi passi saranno prevedibili." Garantisce che la "attrazione magnetica" non si comporti in modo erratico. Assicura che, finché la mappa non subisce improvvisamente una torsione folle vicino al centro, l'escursionista rimarrà entro una distanza prevedibile dall'obiettivo, anche se non lo toccherà mai esattamente.

5. Il Risultato: "Abbastanza Vicino" è Abbastanza Bene

L'articolo dimostra che con questo nuovo metodo:

• Non hai bisogno che gli errori svaniscano.
• Non hai bisogno che gli errori si sommino in un numero minuscolo.
• Hai solo bisogno che gli errori rimangano entro un limite fisso e gestibile (come una bussola che è sempre sfasata di non più di 2 gradi).

Se imposti correttamente i tuoi parametri, l'escursionista smetterà di vagare lontano e si stabilizzerà entro una piccola e prevedibile distanza dal vero centro. Non si fermerà mai esattamente sul punto esatto, ma oscillerà in modo stabile e controllato intorno ad esso. L'articolo chiama questo una "soluzione approssimata stabile".

Perché questo è importante (secondo l'articolo)

Nelle calcoli informatici del mondo reale, è spesso impossibile far scomparire completamente gli errori o fare in modo che si sommino in un numero minuscolo. I computer hanno dei limiti; hanno sempre un po' di "rumore" o "errore di arrotondamento" che non scompare mai del tutto.

Se volessimo la precisione perfetta (arrivare esattamente al centro), dovremmo usare regole molto rigide che richiedono che gli errori diventino infinitesimi col tempo, il che è difficile da garantire nella pratica.

Questo articolo sostiene che, utilizzando la loro tecnica della "pendenza magnetica", possiamo fidarci di questi algoritmi per trovare risposte abbastanza buone e stabili anche quando gli errori del computer sono ostinati e non scompaiono mai. Sposta l'attenzione dalla "precisione perfetta" ai "risultati pratici e controllati".

Inoltre, la regola che usano è molto semplice da verificare: basta assicurarsi che ogni singolo errore rimanga al di sotto di un certo limite piccolo e fisso. È molto più facile controllare che un errore non superi mai, ad esempio, 0,001, piuttosto che controllare che la somma di tutti gli errori futuri sia minuscola.

In sintesi: L'articolo ci insegna che anche se i tuoi strumenti sono imperfetti e gli errori non si fermano mai, puoi comunque trovare una soluzione stabile e affidabile cambiando la forma del problema. Non raggiungerai mai il centro esatto se l'errore è costante, ma rimarrai intrappolato in una piccola zona sicura intorno ad esso, evitando di vagare all'infinito.

Sommario tecnico

Sintesi Tecnica: Algoritmi del Punto Prossimale Inesatto e di Tseng con Errori Non Sommabili

Enunciato del Problema
Il saggio affronta il problema della risoluzione di inclusioni monotone della forma $0 \in Ax$ in uno spazio di Hilbert reale $H$, dove $A: H \rightrightarrows H$ è un operatore massimamente monotono a valori multipli. Il focus primario è sulla stabilità asintotica di versioni inesatte e pratiche di due algoritmi classici: l'Algoritmo del Punto Prossimale (PPA) e l'Algoritmo di Tseng (per inclusioni composte $0 \in Ax + Bx$).

Un vincolo critico di questo lavoro è il trattamento degli errori computazionali. A differenza della maggior parte della letteratura esistente, che assume che le sequenze di errore siano sommabili (ovvero $\sum \|y_k\| < \infty$, condizione che implica che gli errori svaniscano asintoticamente e garantisce la convergenza debole delle iterazioni a una soluzione esatta), questo saggio investiga algoritmi sotto l'influenza di errori limitati e non sommabili. Nello specifico, la sequenza di errore $(y_k)$ soddisfa $\|y_k\| \le \delta$ per una tolleranza fissata $\delta > 0$. Questa condizione è motivata dal fatto che, nella pratica computazionale, gli errori di precisione finita non tendono mai a zero; pertanto, sono necessari criteri di errore verificabili. Mentre i criteri di errore relativo sono spesso difficili da verificare in pratica, i criteri di errore assolutamente limitato sono facilmente verificabili e rappresentano un modello realistico per calcoli a precisione finita. È fondamentale chiarire che $y_k$ rappresenta l'errore (inesattezza) nell'evalutazione dell'operatore risolvente/prossimale al passo $k$ e che, per assunzione, questo errore rimane limitato dalla piccola tolleranza positiva $\delta$ senza tendere a zero. Tale errore per passo $y_k$ è distinto dalla distanza $d(x_k, S)$ tra l'iterata $x_k$ e l'insieme delle soluzioni $S$.

Metodologia
Gli autori propongono un approccio innovativo che evita il ricorso alla sommabilità degli errori. Invece, la metodologia si basa su tre componenti fondamentali:

1. Regolarizzazione di Tikhonov: L'originale problema di inclusione viene regolarizzato aggiungendo un termine fortemente monotono $\epsilon I$ (dove $\epsilon > 0$). Per il PPA, l'operatore diventa $\tilde{A} = A + \epsilon I$. Per il problema composto, l'inclusione regolarizzata è $0 \in \tilde{A}x + Bx$. Questa regolarizzazione assicura che gli operatori risolventi possiedano proprietà di contrazione forte.
2. Proprietà di Contrazione: Utilizzando la monotonia forte indotta dal termine di regolarizzazione, gli autori dimostrano che gli operatori risolventi (e la mappatura associata di Tseng) diventano contrattivi. Ciò consente di controllare la propagazione dell'errore senza richiedere che gli errori decadano a zero.
3. Teoria della R-continuità: L'analisi della convergenza sfrutta la recentemente sviluppata teoria della R-continuità per le mappature a valori multipli. Nello specifico, gli autori assumono che l'operatore inverso (ad esempio, $A^{-1}$ o $(A+B)^{-1}$) sia R-continuo nell'origine. Questa proprietà permette agli autori di limitare la distanza tra la soluzione del problema regolarizzato e l'insieme delle soluzioni del problema originale.

Contributi Chiave e Risultati

• Algoritmo del Punto Prossimale Inesatto (IPPA):
  Il saggio stabilisce la stabilità asintotica dell'IPPA definito da $x_{k+1} = J_{\gamma \tilde{A}}x_k + y_{k+1}$ sotto l'assunzione di errore limitato $\|y_{k+1}\| \le \delta$.

  • Risultato: Non si verifica la convergenza delle iterazioni $(x_k)$ a un punto soluzione esatto. Invece, la sequenza $(x_k)$ rimane asintoticamente all'interno di un intorno esplicitamente limitato dell'insieme delle soluzioni $S = \text{zer}(A)$. Gli autori derivano un limite superiore costruttivo per la distanza asintotica:
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + \gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
    dove $\rho$ è il modulo di R-continuità di $A^{-1}$, e $a$ è la norma dell'elemento a norma minima in $S$.
  • Condizione di Convergenza: Scegliendo $\delta = \epsilon^2$, il limite svanisce quando $\epsilon \to 0$, garantendo che l'algoritmo produca soluzioni approssimate arbitrariamente accurate (in termini di vicinanza all'insieme delle soluzioni). Tuttavia, è cruciale notare che la convergenza debole di $x_k$ a una soluzione esatta richiederebbe la classica condizione di errori sommabili ($\sum \|y_k\| < \infty$), ipotesi che non è soddisfatta in questo lavoro.

• Algoritmo di Tseng Inesatto (ITA):
  L'approccio è esteso al problema composto $0 \in Ax + Bx$, dove $B$ è a valore singolo, monotono e Lipschitz continuo. L'ITA viene applicato al problema regolarizzato di Tikhonov.

  • Risultato: Sotto l'assunzione che $(A+B)^{-1}$ sia R-continuo nell'origine, gli autori dimostrano che la sequenza ITA non converge a un punto soluzione, ma rimane asintoticamente confinata in un intorno della soluzione. Il limite di errore derivato è:
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + 2\gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
  • Similmente all'IPPA, impostare $\delta = \epsilon^2$ garantisce che la distanza asintotica dall'insieme delle soluzioni possa essere resa arbitrariamente piccola al tendere di $\epsilon$ a zero, senza però garantire la convergenza puntuale delle iterazioni.

Significatività e Rivendicazioni
Il saggio sostiene di essere il primo nella letteratura ad aver stabilito la stabilità asintotica (in termini di limitazione della distanza dall'insieme delle soluzioni) di algoritmi pratici inesatti di PPA e Tseng sotto la sola assunzione di errori limitati e non sommabili.

Gli autori sottolineano che la loro analisi rivela come la monotonia forte indotta dal termine di regolarizzazione di Tikhonov, piuttosto che la classica sommabilità degli errori, sia il meccanismo essenziale che garantisce la stabilità e la ben-posta dei problemi di questi algoritmi in presenza di errori persistenti. Essi sostengono che l'assunzione standard di sommabilità sia spesso difficile da garantire in pratica, mentre la condizione di errore limitato è computazionalmente realistica.

Le tecniche proposte sono presentate come un quadro flessibile che può essere esteso per analizzare altri algoritmi inesatti per problemi di ottimizzazione che coinvolgono perturbazioni non sommabili. Il saggio non propone nuove applicazioni o validazioni sperimentali, ma si concentra strettamente sulla giustificazione teorica di tali algoritmi sotto condizioni di errore rese più blande, evitando di affermare la convergenza a soluzioni esatte in assenza di errori sommabili.