On the centralization of the circumcentered-reflection method

Abstract

This paper is devoted to deriving the first circumcenter iteration scheme that does not employ a product space reformulation for finding a point in the intersection of two closed convex sets. We introduce a so-called centralized version of the circumcentered-reflection method (CRM). Developed with the aim of accelerating classical projection algorithms, CRM is successful for tracking a common point of a finite number of affine sets. In the case of general convex sets, CRM was shown to possibly diverge if Pierra's product space reformulation is not used. In this work, we prove that there exists an easily reachable region consisting of what we refer to as centralized points, where pure circumcenter steps possess properties yielding convergence. The resulting algorithm is called centralized CRM (cCRM). In addition to having global convergence, cCRM converges linearly under an error bound condition, and superlinearly if the two target sets are so that their intersection have nonempty interior and their boundaries are locally differentiable manifolds. We also run numerical experiments with successful results.

arXiv comment30 pages with 7 figures

References in corpus (13)

• Transversality and alternating projections for nonconvex sets
• Circumcentering the Douglas--Rachford method
• On the linear convergence of the circumcentered-reflection method
• On the Circumcentered-Reflection Method for the Convex Feasibility Problem
• About intrinsic transversality of pairs of sets
• The Block-wise Circumcentered-Reflection Method
• The circumcentered-reflection method achieves better rates than alternating projections
• On circumcenters of finite sets in Hilbert spaces
• Infeasibility and error bound imply finite convergence of alternating projections
• On circumcenter mappings induced by nonexpansive operators
• Circumcentering approximate reflections for solving the convex feasibility problem
• Circumcentric directions of cones
• Finite convergence of locally proper circumcentered methods

Cited by in corpus (2)

• A successive centralized circumcenter reflection method for the convex feasibility problem
• A finitely convergent circumcenter method for the Convex Feasibility Problem