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

Este artigo estabelece, pela primeira vez, a convergência de algoritmos práticos de Ponto Proximal Inexato e de Tseng para resolver inclusões monotônicas em espaços de Hilbert sob erros não somáveis, ao alavancar regularização de Tikhonov, propriedades de contração e a teoria de continuidade-R.

O essencial

Imagine que você está tentando encontrar o centro exato de uma sala escura e com neblina (a "solução"). Você tem uma bússola (um algoritmo) que aponta para o centro. Em um mundo perfeito, sua bússola seria impecável e você caminharia diretamente para o centro.

No entanto, no mundo real, sua bússola é um pouco instável. Às vezes ela aponta levemente para a esquerda, às vezes levemente para a direita. Essa "instabilidade" é o que os matemáticos chamam de erro.

Por muito tempo, os matemáticos acreditaram que, para você eventualmente alcançar o centro exato, esses erros de instabilidade teriam que diminuir cada vez mais até desaparecerem completamente. Eles pensavam que a quantidade total de "oscilação" em toda a sua jornada teria que somar um número minúsculo e finito. Se a oscilação continuasse acontecendo em um nível constante e perceptível para sempre, eles pensavam que você nunca pararia de vagar em círculos e, portanto, nunca chegaria ao ponto exato.

Este artigo diz: "Não necessariamente, mas há um limite."

Os autores, Ba Khiet Le, Boris S. Mordukhovich e Michel Théra, descobriram uma nova maneira de navegar que funciona mesmo se sua bússola continuar oscilando com uma quantidade de erro constante e não nula. Veja como eles fizeram isso, usando metáforas simples:

1. O Problema: A Regra da "Somabilidade"

Tradicionalmente, para garantir que você chegasse ao centro exato, a regra era: Os erros devem eventualmente desaparecer.
Pense nisso como caminhar em direção a um alvo enquanto é empurrado pelo vento. Se o vento ficar cada vez mais fraco até parar (erros somáveis), você eventualmente alcançará o alvo com precisão. Mas se o vento continuar soprando em uma velocidade constante e irritante (erro não somável), a matemática tradicional dizia que você nunca chegaria lá com exatidão.

2. A Solução: Adicionando uma "Atração Magnética" (Regularização de Tikhonov)

A arma secreta dos autores é a regularização de Tikhonov.
Imagine que, em vez de apenas caminhar em um chão plano, você está caminhando em uma encosta suave e curva que leva diretamente ao centro. Mesmo que o vento (o erro) continue te empurrando para o lado, a encosta (a "atração" matemática) te puxa constantemente de volta para o caminho.

Em sua matemática, eles adicionam uma pequena "força" artificial (representada por $\epsilon$) ao problema. Essa força torna o cenário "mais íngreme" e definido. Ela transforma o chão plano e escorregadio em um formato de tigela. Mesmo que você seja empurrado para fora do curso por um erro constante, o formato de tigela garante que você não vagueie para sempre. No entanto, é crucial entender: você não vai parar exatamente no centro. Em vez disso, você se estabilizará em um ponto muito próximo, dentro de uma pequena "zona de segurança" ao redor do centro, e continuará a oscilar levemente dentro dessa zona para sempre.

3. Os Dois Algoritmos: O Excursionista e o Guia

O artigo testa essa ideia em dois tipos específicos de "excursionistas" (algoritmos):

• O Algoritmo de Ponto Proximal Inexato (IPPA): Este é como um excursionista que dá um passo, verifica o mapa e corrige seu caminho. Os autores mostram que, mesmo que o mapa tenha um pequeno borrão constante (erro), a "inclinação magnética" garante que o excursionista termine e permaneça muito próximo do alvo, dentro de uma distância segura, sem nunca precisar atingir o ponto exato.
• O Algoritmo de Tseng Inexato (ITA): Este é um excursionista mais complexo que tem que lidar com dois tipos diferentes de terreno ao mesmo tempo (dois operadores matemáticos diferentes). Os autores mostram que, mesmo com essa complexidade extra e erros constantes, a "inclinação magnética" ainda funciona para manter o excursionista dentro dessa zona de segurança ao redor do objetivo.

4. A Rede de Segurança da "R-Continuidade"

Para provar que isso funciona, eles usam um conceito chamado R-continuidade.
Pense nisso como uma rede de segurança que diz: "Se você estiver perto do alvo, seus passos serão previsíveis." Isso garante que a "atração magnética" não se comporte de forma errática. Desde que o mapa não mude subitamente de uma forma louca perto do centro, o excursionista permanecerá dentro de uma distância previsível e fixa do objetivo, mesmo que nunca o toque exatamente.

5. O Resultado: "Bom o Suficiente" é o Melhor que se Pode Esperar

O artigo prova que, com este novo método:

• Você não precisa que os erros desapareçam.
• Você não precisa que os erros somem um número minúsculo.
• Você só precisa que os erros permaneçam dentro de um limite fixo e gerenciável (como uma bússola que está sempre errada por no máximo 2 graus).

Se você configurar seus parâmetros corretamente, o excursionista parará de vagar para longe e se estabilizará dentro de uma distância pequena e previsível do verdadeiro centro. O artigo chama isso de uma "solução aproximada".

Importante: Se você realmente precisasse chegar ao centro exato, ainda precisaria da regra antiga onde os erros somam um número minúsculo e desaparecem. Mas, com erros constantes, o melhor resultado possível é ficar "preso" em uma pequena área ao redor do centro, sem nunca sair dessa área.

Por que Isso Importa (Segundo o Artigo)

Em cálculos computacionais do mundo real, muitas vezes é impossível fazer com que os erros desapareçam completamente ou fazer com que eles somem um número minúsculo. Os computadores têm limites; eles sempre têm um pouco de "ruído" ou "erro de arredondamento" que nunca desaparece totalmente.

Este artigo afirma que, ao usar sua técnica de "inclinação magnética", podemos confiar que esses algoritmos encontrarão respostas boas o suficiente e estáveis, mesmo quando os erros do computador são persistentes. Isso é prático porque, em vez de tentar garantir que o erro some infinitamente (o que é difícil de verificar), basta garantir uma regra simples: "Mantenha cada erro individual abaixo de um limite pequeno e fixo". Essa regra é fácil de verificar e controlar.

Em resumo: O artigo nos ensina que, mesmo que suas ferramentas sejam imperfeitas e os erros nunca parem, você ainda pode encontrar uma solução útil. Você não chegará ao centro exato, mas ficará preso em uma pequena área segura ao redor dele, garantindo que o resultado seja estável e confiável para aplicações práticas.

Resumo técnico

Resumo Técnico: Algoritmos de Ponto Proximal Inexato e de Tseng com Erros Não Somáveis

Definição do Problema
O artigo aborda o problema de resolver inclusões monotônicas da forma $0 \in Ax$ em um espaço de Hilbert real $H$, onde $A: H \rightrightarrows H$ é um operador maximalmente monotônico multivalorado. O foco principal é a análise de estabilidade de versões inexatas práticas de dois algoritmos clássicos: o Algoritmo de Ponto Proximal (PPA) e o Algoritmo de Tseng (para inclusões compostas $0 \in Ax + Bx$).

Uma restrição crítica deste trabalho é o tratamento de erros computacionais. Diferente da maior parte da literatura existente, que assume que sequências de erro são somáveis (ou seja, $\sum \|y_k\| < \infty$, implicando que os erros desaparecem assintoticamente), este artigo investiga algoritmos sob erros limitados e não somáveis. Especificamente, a sequência de erro $(y_k)$ satisfaz $\|y_k\| \le \delta$ para uma tolerância fixa $\delta > 0$. Esta condição é motivada pela realidade prática de computações de precisão finita, onde os erros de implementação ou arredondamento nunca tendem a zero ($y_k \not\to 0$). Enquanto critérios de erro relativo são frequentemente difíceis de verificar na prática, a condição de erro absolutamente limitado é computacionalmente realista e verificável.

Metodologia
Os autores propõem uma abordagem inovadora que evita a dependência da somabilidade dos erros. Em vez disso, a metodologia baseia-se em três componentes principais:

1. Regularização de Tikhonov: O problema de inclusão original é regularizado pela adição de um termo fortemente monotônico $\epsilon I$ (onde $\epsilon > 0$). Para o PPA, o operador torna-se $\tilde{A} = A + \epsilon I$. Para o problema composto, a inclusão regularizada é $0 \in \tilde{A}x + Bx$. Esta regularização garante que os operadores de resolvente possuam propriedades de contração forte.
2. Propriedades de Contração: Ao utilizar a monotonia forte induzida pelo termo de regularização, os autores demonstram que os operadores de resolvente (e o mapeamento de Tseng associado) tornam-se contrativos. Isso permite o controle da propagação do erro sem exigir que os erros decaiam para zero.
3. Teoria de R-continuidade: A análise de convergência utiliza a teoria recentemente desenvolvida de R-continuidade para mapeamentos multivalorados. Especificamente, os autores assumem que o operador inverso (por exemplo, $A^{-1}$ ou $(A+B)^{-1}$) é R-contínuo na origem. Esta propriedade permite que os autores limitem a distância entre a solução do problema regularizado e o conjunto de soluções do problema original.

Principais Contribuições e Resultados

• Algoritmo de Ponto Proximal Inexato (IPPA):
  O artigo estabelece a estabilidade do IPPA definido por $x_{k+1} = J_{\gamma \tilde{A}}x_k + y_{k+1}$ sob a suposição de erro limitado $\|y_{k+1}\| \le \delta$. Aqui, $y_{k+1}$ representa explicitamente o erro computacional (inexatidão) na avaliação do operador de resolvente no passo $k+1$; diferentemente da distância assintótica $d(x_{k+1}, S)$, que é a grandeza que se deseja limitar, o termo $y_{k+1}$ é um erro por iteração que permanece limitado por $\delta$ e não tende a zero.

  • Resultado de Estabilidade: Sob erros não somáveis, a sequência $(x_k)$ não converge para um ponto específico da solução. Em vez disso, os autores provam que a sequência permanece assintoticamente dentro de uma vizinhança limitada do conjunto de soluções $S = \text{zer}(A)$. O limite superior construtivo para a distância assintótica é:
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + \gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
    onde $\rho$ é o módulo de R-continuidade de $A^{-1}$ em 0, e $a$ é a norma do elemento de norma mínima em $S$.
  • Convergência vs. Estabilidade: É crucial notar que a convergência (fraca) de $x_k$ para uma solução exata só é garantida sob a condição clássica de erros somáveis ($\sum \|y_k\| < \infty$), hipótese que não se aplica neste trabalho. O resultado aqui é a garantia de que o algoritmo produz uma "solução aproximada" estável, onde o erro final é controlado explicitamente.
  • Aproximação Arbitrária: Ao escolher $\delta = \epsilon^2$, o limite desaparece quando $\epsilon \to 0$, garantindo que o algoritmo possa produzir soluções aproximadas arbitrariamente precisas, ajustando-se o parâmetro de regularização.

• Algoritmo de Tseng Inexato (ITA):
  A abordagem é estendida para o problema composto $0 \in Ax + Bx$, onde $B$ é univalente, monotônico e Lipschitz contínuo. O ITA é aplicado ao problema regularizado por Tikhonov.

  • Resultado: Sob a suposição de que $(A+B)^{-1}$ é R-contínuo em 0, os autores provam que a sequência do ITA não converge para um ponto exato, mas permanece assintoticamente dentro de um limite de erro explícito:
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + 2\gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
  • Semelhante ao IPPA, definir $\delta = \epsilon^2$ permite que o limite de erro seja reduzido arbitrariamente conforme o parâmetro de regularização $\epsilon$ se aproxima de zero, sem exigir que os erros de iteração individual desapareçam.

Significância e Alegações
O artigo afirma ser o primeiro na literatura a estabelecer a estabilidade de algoritmos práticos de PPA e Tseng inexatos sob a única suposição de erros limitados e não somáveis.

Os autores enfatizam que sua análise revela que a monotonia forte induzida pelo termo de regularização de Tikhonov, em vez da clássica somabilidade de erros, é o mecanismo essencial que garante a estabilidade e a boa definição desses algoritmos em cenários de erro persistente. Eles argumentam que a suposição padrão de somabilidade é frequentemente difícil de garantir na prática, enquanto a condição de erro limitado é computacionalmente realista.

As técnicas propostas são apresentadas como um framework flexível que pode ser estendido para analisar outros algoritmos inexatos para problemas de otimização envolvendo perturbações não somáveis. O artigo não propõe novas aplicações ou validações experimentais, mas foca estritamente na justificação teórica de que, na ausência de erros somáveis, a convergência para uma solução exata não ocorre, mas sim a convergência para uma vizinhança controlada da solução.