Análise teórica do método de reflexão circuncentrada no problema de viabilidade convexa convexo-afim

Resumo

O Problema de Viabilidade Convexa (\textit{Convex Feasibility Problem} -- CFP) consiste em determinar um ponto pertencente à interseção de conjuntos convexos e fechados em $\mathbb{R}^n$. Trata-se de um problema fundamental em matemática aplicada, com aplicações em otimização convexa, processamento de sinais, reconstrução de imagens e métodos iterativos para sistemas restritos. Métodos baseados em projeções ortogonais, como o Método das Projeções Alternadas (MAP), constituem ferramentas clássicas para sua resolução, apresentando robustez e garantias gerais de convergência. Contudo, suas taxas assintóticas podem deteriorar-se significativamente quando a interseção dos conjuntos apresenta geometria desfavorável. Nesta dissertação, analisamos o Método de Reflexão Circuncentrada, denominado CRM (\textit{Circumcentered- Reflection Method}), no contexto convexo--afim, no qual se busca um ponto na interseção entre um conjunto convexo fechado $K$ e uma variedade afim $U$, assumindo-se $K \cap U \neq \varnothing$. O CRM combina projeções e reflexões ortogonais, definindo cada iteração como o circuncentro de três pontos geometricamente associados ao problema, incorporando assim informação adicional da estrutura geométrica das restrições. Inicialmente, demonstramos que a sequência gerada pelo CRM é Fejér-monótona em relação ao conjunto solução, o que implica limitação e convergência global para um ponto de $K \cap U$. Em seguida, sob uma hipótese geométrica do tipo \emph{error bound}, estabelecemos convergência $Q$-linear das distâncias ao conjunto solução e convergência $R$-linear dos iterados. O principal resultado do trabalho consiste na obtenção de uma constante assintótica estritamente melhor para o CRM quando comparado ao MAP. Mostramos que, sob a hipótese de regularidade geométrica, a taxa de contração do CRM é dada por \[ \sqrt{\frac{1-\gamma^2}{1+\gamma^2}}, \] enquanto o MAP admite constante $\sqrt{1-\gamma^2}$. Tal melhoria decorre de uma desigualdade de energia reforçada, obtida a partir da caracterização do CRM como projeção sobre um semiespaço intermediário que contém o conjunto convexo. Os resultados obtidos fornecem uma fundamentação teórica rigorosa para o desempenho superior do CRM no regime convexo-- afim, esclarecendo os mecanismos geométricos responsáveis por sua aceleração e contribuindo para o desenvolvimento e a compreensão de métodos circuncentrados em problemas de viabilidade convexa.

Ficha do documento

Tipo

Dissertação

Ano

2026

Instituição

Fundação Getulio Vargas

Fonte

Repositório da FGV

Idioma

Português

Acesso

Acesso aberto

Identificador

oai:repositorio.fgv.br:10438/38858

Temas

Infraestrutura

Palavras-chave

Viabilidade convexaMétodo de Reflexão CircuncentradaProjeções ortogonaisMétodos iterativosConvergência linearConvex feasibilityCircumcentered Reflection methodOrthogonal projectionsIterative methodsLinear convergenceMatemáticaConjuntos convexosGeometria convexaMetodos iterativos (Matemática)Projeções métricasMatemática aplicada