Circumcentering the Douglas--Rachford method
arXiv:1704.06737 · doi:10.1007/s11075-017-0399-5
Abstract
We introduce and study a geometric modification of the Douglas-Rach\-ford method called the Circumcentered-Douglas-Rachford method. This method iterates by taking the intersection of bisectors of reflection steps for solving certain classes of feasibility problems. The convergence analysis is established for best approximation problems involving two (affine) subspaces and both our theoretical and numerical results compare favorably to the original Douglas-Rachford method. Under suitable conditions, it is shown that the linear rate of convergence of the Circumcentered-Douglas-Rachford method is at least the cosine of the Friedrichs angle between the (affine) subspaces, which is known to be the sharp rate for the Douglas-Rachford method. We also present a preliminary discussion on the Circumcentered-Douglas-Rachford method applied to the many set case and to examples featuring non-affine convex sets.
References in corpus (2)
Cited by in corpus (14)
- On the linear convergence of the circumcentered-reflection method
- 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
- On circumcenters of finite sets in Hilbert spaces
- Circumcentering approximate reflections for solving the convex feasibility problem
- On the centralization of the circumcentered-reflection method
- Circumcentric directions of cones
- A successive centralized circumcenter reflection method for the convex feasibility problem
- A finitely convergent circumcenter method for the Convex Feasibility Problem
- On the linear convergence of circumcentered isometry methods
- Circumcentered methods induced by isometries
- Coordinate-Update Algorithms can Efficiently Detect Infeasible Optimization Problems
- Best approximation mappings in Hilbert spaces