Métodos circuncentrados com aleatoriedade para resolução de sistemas lineares: análise e aplicações

Abstract

Este estudo investiga métodos baseados em projeções aplicados à resolução de sistemas de equações lineares. Tais métodos exploram a simplicidade computacional da projeção em subespaços afins lineares para encontrar a solução de um sistema linear, a qual é representada pela intersecção de conjuntos convexos. Este problema é conhecido como Problema de Viabilidade Convexa (CFP). Apesar da simplicidade, os métodos clássicos de projeção podem apresentar convergência lenta para resolver CFPs. Diversas técnicas de aceleração têm sido desenvolvidas, destacando-se por um lado aquelas que incorporam aleatoriedade na escolha das restrições utilizadas a cada iteração, e por outro métodos baseados em circuncentros. Nesse contexto, este trabalho propõe duas contribuições principais: a generalização do Método das Reflexões Circuncentradas (CRM) com inclusão de aleatoriedade, denominado RrCRM, o qual, calcula o circuncentro a partir de $r$ de linhas arbitrariamente escolhidas ? sendo também interpretado como uma forma de acelerar do método Douglas-Rachford com aleatoriedade para $r$ conjuntos (RrDRM); e a introdução de uma variante por blocos, chamada RBwCRM, que explora a reordenação das linhas do sistema de forma aleatória. A teoria de convergência dos métodos propostos é apresentada. Uma série de experimentos numéricos com dados sintéticos e problemas reais é reportada, o que permite verificar o comportamento favorável de nossas abordagens em diferentes cenários e verificar sua consistência com a teoria desenvolvida.

Abstract: This study investigates projection-based methods for solving systems of linear equations. These methods take advantage of the computational simplicity of projections onto affine subspaces to find solutions represented as intersections of convex sets?a problem known as the Convex Feasibility Problem (CFP). Although classical projection methods are straightforward, they may exhibit slow convergence when solving CFPs. To address this limitation, various acceleration techniques have been proposed, including randomized constraint selection and circumcenter-based approaches. In this work, we present two main contributions. First, a generalization of the Circumcentered-Reflection Method (CRM) that incorporates randomness by computing the circumcenter from $r$ randomly selected rows. This method can also be interpreted as an acceleration of the randomized Douglas-Rachford method (RrDRM) for $r$ sets. Second, it introduces a block variant called RBwCRM, which explores the random reordering of the system's rows. We provide a convergence analysis for both methods and conduct extensive numerical experiments using synthetic and real-world data. The results demonstrate the superior performance of our approaches in various scenarios, confirming their theoretical consistency.