A finitely convergent circumcenter method for the Convex Feasibility Problem

Abstract

In this paper, we present a variant of the circumcenter method for the Convex Feasibility Problem (CFP), ensuring finite convergence under a Slater assumption. The method replaces exact projections onto the convex sets with projections onto separating halfspaces, perturbed by positive exogenous parameters that decrease to zero along the iterations. If the perturbation parameters decrease slowly enough, such as the terms of a diverging series, finite convergence is achieved. To the best of our knowledge, this is the first circumcenter method for CFP that guarantees finite convergence.

References in corpus (10)

• Set Regularities and Feasibility Problems
• Circumcentering the Douglas--Rachford method
• On the linear convergence of the circumcentered-reflection method
• On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
• On the Circumcentered-Reflection Method for the Convex Feasibility Problem
• The Block-wise Circumcentered-Reflection Method
• The circumcentered-reflection method achieves better rates than alternating projections
• Infeasibility and error bound imply finite convergence of alternating projections
• On the centralization of the circumcentered-reflection method
• Generalized Alternating Projections on Manifolds and Convex Sets