Circumcentering outer-approximate projections and reflections for the convex feasibility problem

Abstract

Recentemente, algoritmos baseados em circuncentros foram aplicados para resolver problemas gerais de viabilidade convexa. Para superar computações custosas de projeções e reflexões em conjuntos convexos, nós apresentamos uma variante do método de reflexões circuncentradas (circumcentered-reflection method) que emprega projeções externamente-aproximadas, inspirados por Fukushima. Com um apelo bastante prático, esta noção se baseia em hiperplanos separadores e é considerada no nosso método híbrido para encontrar um ponto na interseção de finitamente muitos conjuntos convexos. Derivamos convergência em geral, convergência linear sob uma condição de "error bound" e apresentamos experimentos numéricos bem-sucedidos.

Recently, circumcenter schemes were applied to solving general convex feasibility problems. In order to overcome costly computations of projections and reflections onto convex sets, we present a variant of the circumcentered-reflection method which employs outer-approximate projections, inspired by Fukushima. With a very practical appeal, this notion relies on separating hyperplanes and is considered in our hybrid method for finding a point in the intersection of finitely many convex sets. We derive convergence in general, linear convergence under an error bound condition, and present successful numerical experiments.