Generalized Composed Alternating Relaxed Projection Algorithm for Two-Set Feasibility Problem

Resumo Técnico: Algoritmo Generalizado de Projeção Alternada Relaxada Composta (gCARPA)

1. O Problema

O artigo aborda o problema de viabilidade de dois conjuntos, que consiste em encontrar um ponto na interseção de dois conjuntos convexos fechados não vazios, $X$ e $Y$, em um espaço de Hilbert real $\mathcal{H}$:
$$\text{encontrar } x \in \mathcal{H} \text{ tal que } x \in X \cap Y.$$
Este problema é fundamental em diversas aplicações, incluindo processamento de sinais e imagens, sensoriamento comprimido e processamento de dados sísmicos. Métodos baseados em projeção são amplamente utilizados devido à sua simplicidade e fortes garantias de convergência.

2. Metodologia: O Algoritmo gCARPA

Os autores propõem o Algoritmo Generalizado de Projeção Alternada Relaxada Composta (gCARPA). Este método generaliza o algoritmo CARPA (proposto recentemente por Shen et al.) e unifica várias técnicas clássicas (como Projeções Alternadas - MAP, Douglas-Rachford - DR, e reflexões relaxadas) em um único quadro teórico.

Mecanismo do Algoritmo:
O gCARPA combina dinâmicas do tipo Douglas-Rachford com correções do tipo projeção-reflexão através de:

1. Reflexões Relaxadas: Introduz parâmetros de relaxação $\theta$ e $\eta$ para os operadores de reflexão em $X$ e $Y$, respectivamente:
   $$R_X^\theta = (1-\theta)I + \theta(2P_X - I)$$
   $$R_Y^\eta = (1-\eta)I + \eta(2P_Y - I)$$
   Quando $\theta = \eta = 1$, recupera-se as reflexões padrão.
2. Combinação Convexa: O algoritmo utiliza um parâmetro $\gamma \in [0, 1)$ para interpolar entre um termo de média do tipo Douglas-Rachford e um termo de projeção pura.
3. Passo Externo de Média: Um parâmetro $\mu$ controla a iteração de ponto fixo externa.

A iteração é definida como:
$$z_{k+1} = (1-\mu)z_k + \mu \left[ (1-\gamma)A_{\theta,\eta}(z_k) + \gamma B_\theta(z_k) \right]$$
Onde $A_{\theta,\eta}$ e $B_\theta$ são operadores compostos envolvendo projeções e reflexões relaxadas.

Variação Não Estacionária (ns-gCARPA):
O artigo também introduz uma variante onde os parâmetros $(\gamma_k, \theta_k, \eta_k)$ variam a cada iteração, permitindo que o algoritmo se adapte à geometria local do problema, desde que as variações sejam suficientemente pequenas (somáveis).

3. Principais Contribuições Teóricas

• Convergência Global: Estabelecem a convergência global (fraca em espaços de dimensão infinita, forte em dimensão finita) do gCARPA para um ponto na interseção $X \cap Y$, sob condições adequadas nos parâmetros ($\gamma \in (0,1)$ e $\mu$ dentro de um intervalo específico).
• Caracterização Espectral para Subespaços: Para o caso onde $X$ e $Y$ são subespaços lineares, os autores derivam uma caracterização espectral explícita baseada nos ângulos principais entre os subespaços.
  • Demonstram que a taxa de convergência linear é governada pelo raio espectral de blocos $2 \times 2$ associados a cada ângulo principal.
  • Derivam uma receita minimax para a seleção ótima do parâmetro $\gamma$ em um regime simétrico, visando o "amortecimento crítico" nos planos dos ângulos principais.
• Unificação de Métodos: O gCARPA recupera como casos especiais:
  • O método de Douglas-Rachford (quando $\gamma=0, \theta=\eta=1$).
  • O método de Projeções Alternadas (MAP) (quando $\theta=1/2, \gamma=1, \mu=1$).
  • O algoritmo CARPA original (quando $\theta=\eta=1$).

4. Resultados Numéricos

Os experimentos foram realizados em três cenários principais:

1. Viabilidade de Subespaços:

   • Os resultados validam a teoria espectral, mostrando que a taxa de convergência empírica coincide com o módulo do autovalor subdominante previsto.
   • O gCARPA, com parâmetros $(\theta, \eta)$ ajustados, demonstra taxas de convergência superiores ao CARPA padrão e ao DR, especialmente em ângulos maiores (regimes onde o DR sofre de trajetórias espirais pronunciadas).
   • A visualização de trajetórias confirma que os parâmetros relaxados reduzem a componente rotacional (espiral) típica do DR.

2. Viabilidade Não Linear (Círculo Tangente a uma Linha):

   • Neste problema desafiador (ângulo zero na interseção), métodos estacionários sofrem com caudas de convergência lentas.
   • A versão não estacionária (ns-gCARPA) mostrou-se superior, adaptando-se dinamicamente para mitigar o desaceleramento próximo ao ponto de tangência, superando métodos fixos e até mesmo o ns-CARPA em tolerâncias rigorosas.

3. Problemas Inversos Lineares Esparsos (Sensoriamento Comprimido):

   • Testes em modelos realistas de recuperação de sinais esparsos mostraram que o desempenho é dependente da instância.
   • O gCARPA (estacionário) frequentemente iguala ou supera o CARPA e o DR em diversos cenários.
   • A versão não estacionária (ns-gCARPA) oferece robustez, embora em alguns casos a variação agressiva de parâmetros possa introduzir efeitos transitórios indesejados em problemas com projeções em bolas $\ell_1$.

5. Significado e Conclusão

O trabalho apresenta uma generalização significativa dos métodos de projeção para problemas de viabilidade convexa.

• Flexibilidade: A introdução dos parâmetros de relaxação $(\theta, \eta)$ oferece graus de liberdade adicionais para controlar o equilíbrio entre a "rotação" (comum no DR) e o "amortecimento" (comum no MAP).
• Otimização Teórica: A derivada fórmula para seleção de parâmetros baseada em ângulos principais fornece uma base teórica sólida para ajustar algoritmos em problemas de subespaços.
• Adaptabilidade: A variante não estacionária demonstra que a adaptação dinâmica de parâmetros pode melhorar a robustez em geometrias complexas e não lineares, onde escolhas fixas de parâmetros falham.

Em suma, o gCARPA oferece um quadro unificado que não apenas engloba métodos clássicos, mas também permite melhorias de desempenho significativas através de uma sintonização paramétrica inteligente, tanto estática quanto dinâmica.