Abstract
We introduce and study a geometric modification of the Douglas–Rachford 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aragón Artacho, F.J., Borwein, J.M., Tam, M.K.: Recent results on Douglas–Rachford methods for combinatorial optimization problems. J. Optim. Theory Appl. 163(1), 1–30 (2014)
Aragón Artacho, F.J., Borwein, J.M., Tam, M.K.: Global behavior of the Douglas–Rachford method for a nonconvex feasibility problem. J. Glob. Optim. 65(2), 309–327 (2016)
Aragón Artacho, F.J., Borwein, J.M.: Global convergence of a non-convex Douglas–Rachford iteration. J. Glob. Optim. 57(3), 753–769 (2013)
Bauschke, H.H., Bello Cruz, J.Y., Nghia, T.T.A., Phan, H.M., Wang, X.: The rate of linear convergence of the Douglas–Rachford algorithm for subspaces is the cosine of the Friedrichs angle. J. Approx. Theory 185, 63–79 (2014)
Bauschke, H.H., Bello Cruz, J.Y., Nghia, T.T.A., Phan, H.M., Wang, X.: Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces. Numer. Algor. 73(1), 33–76 (2016)
Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. Siam Rev. 38(3), 367–426 (2006)
Bauschke, H.H., Combettes, P. L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 1 edn. CMS Books in Mathematics. Springer International Publishing, Cham (2017)
Bauschke, H.H., Moursi, W.M.: On the Douglas–Rachford algorithm. Math. Program. 164(1-2), 263–284 (2016)
Bauschke, H.H., Noll, D.: On the local convergence of the Douglas–Rachford algorithm. Arch. Math. 102(6), 589–600 (2014)
Bauschke, H.H., Noll, D., Phan, H.M.: Linear and strong convergence of algorithms involving averaged nonexpansive operators. J. Math. Anal. Appl. 421(1), 1–20 (2015)
Benoist, J.: The Douglas–Rachford algorithm for the case of the sphere and the line. J. Glob. Optim. 63(2), 363–380 (2015)
Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: A fresh approach to numerical computing. Siam Rev. 59(1), 65–98 (2017)
Borwein, J.M., Sims, B.: The Douglas–Rachford algorithm in the absence of convexity. In: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 93–109. Springer, New York (2011)
Borwein, J.M., Tam, M.K.: A cyclic Douglas–Rachford iteration scheme. J. Optim. Theory Appl. 160(1), 1–29 (2014)
Censor, Y., Cegielski, A.: Projection methods: an annotated bibliography of books and reviews. Optimization 64(11), 2343–2358 (2014)
Cimmino, G.: Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. Ric. Sci. 9(II), 326–333 (1938)
Combettes, P.L.: The foundations of set theoretic estimation. Proc. IEEE 81 (2), 182–208 (1993)
Deutsch, F.R.: Rate of convergence of the method of alternating projections. In: Brosowski, B., Deutsch, F. R. (eds.) Parametric Optimization and Approximation: Conference Held at the Mathematisches Forschungsinstitut, Oberwolfach, October 16–22, 1983, pp. 96–107. Basel, Birkhäuser (1985)
Deutsch, F.R.: The angle between subspaces of a hilbert space. In: Approximation Theory, Wavelets and Applications, pp. 107–130. Springer, Dordrecht (1995)
Deutsch, F.R.: Best Approximation in Inner Product Spaces. CMS Books in Mathematics. Springer, New York (2001)
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)
Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82(2), 421–421 (1956)
Feuersänger, C.: PGFPlots Package, 1.13 edn (2016)
Hesse, R., Luke, D.R.: Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems. SIAM J. Optim. 23(4), 2397–2419 (2013)
Hesse, R., Luke, D.R., Neumann, P.: Alternating projections and Douglas-Rachford for sparse affine feasibility. IEEE Trans. Signal Process. 62(18), 4868–4881 (2014)
Kayalar, S., Weinert, H.L.: Error bounds for the method of alternating projections. Math. Control Signals Syst. 1(1), 43–59 (1988)
Lions, P., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)
Phan, H.M.: Linear convergence of the Douglas–Rachford method for two closed sets. Optimization 65(2), 369–385 (2016)
Siqueira, A.S., da Silva, R.C., Santos, L.R.: Perprof-py: A python package for performance profile of mathematical optimization software. J Open Res Softw 4(e12), 5 (2016)
Svaiter, B.F.: On weak convergence of the Douglas–Rachford method. SIAM J. Control. Optim. 49(1), 280–287 (2011)
Acknowledgements
We thank the anonymous referees for their valuable suggestions.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Behling, R., Bello Cruz, J. & Santos, LR. Circumcentering the Douglas–Rachford method. Numer Algor 78, 759–776 (2018). https://doi.org/10.1007/s11075-017-0399-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-017-0399-5
Keywords
- Douglas–Rachford method
- Best approximation problem
- Projection and reflection operators
- Friedrichs angle
- Linear convergence
- Subspaces