Top

Numerical Algorithms

Published in:

01-08-2020 | Original Paper

On the circumcentered-reflection method for the convex feasibility problem

Authors: Roger Behling, Yunier Bello-Cruz, Luiz-Rafael Santos

Published in: Numerical Algorithms | Issue 4/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The ancient concept of circumcenter has recently given birth to the circumcentered-reflection method (CRM). CRM was first employed to solve best approximation problems involving affine subspaces. In this setting, it was shown to outperform the most prestigious projection-based schemes, namely, the Douglas-Rachford method (DRM) and the method of alternating projections (MAP). We now prove convergence of CRM for finding a point in the intersection of a finite number of closed convex sets. This striking result is derived under a suitable product space reformulation in which a point in the intersection of a closed convex set with an affine subspace is sought. It turns out that CRM skillfully tackles the reformulated problem. We also show that for a point in the affine set the CRM iteration is always closer to the solution set than both the MAP and DRM iterations. Our theoretical results and numerical experiments, showing outstanding performance, establish CRM as a powerful tool for solving general convex feasibility problems.

previous article A novel alternating-direction implicit spectral Galerkin method for a multi-term time-space fractional diffusion equation in three dimensions

next article Unconditional optimal error estimates of linearized backward Euler Galerkin FEMs for nonlinear Schrödinger-Helmholtz equations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. Ser. B 95(1), 3–51 (2003). https://doi.org/10.1007/s10107-002-0339-5MathSciNetCrossRef

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). https://doi.org/10.1007/s10898-012-9958-4MathSciNetCrossRef

Aragón Artacho, F. J., Campoy, R., Tam, M. K.: The Douglas–Rachford algorithm for convex and nonconvex feasibility problems. Math Meth Oper Res. https://doi.org/10.1007/s00186-019-00691-9 (2019)

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). https://doi.org/10.1016/j.jat.2014.06.002MathSciNetCrossRef

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. Algorithms 73 (1), 33–76 (2016). https://doi.org/10.1007/s11075-015-0085-4MathSciNetCrossRef

Bauschke, H. H., Borwein, J. M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38(3), 367–426 (2006). https://doi.org/10.1137/S0036144593251710MathSciNetCrossRef

Bauschke, H. H., Combettes, P. L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2 edn. CMS Books in Mathematics. Springer International Publishing, Cham (2017). https://doi.org/10.1007/978-3-319-48311-5CrossRef

Bauschke, H. H., Dao, M. N., Noll, D., Phan, H. M.: Proximal point algorithm, Douglas-Rachford algorithm and alternating projections: a case study. J. Convex Anal. 23(1), 237–261 (2016)MathSciNetMATH

Bauschke, H. H., Moursi, W. M.: The Douglas–Rachford algorithm for two (not necessarily intersecting) affine subspaces. SIAM J. Optim. 26(2), 968–985 (2016). https://doi.org/10.1137/15M1016989MathSciNetCrossRef

10.

Bauschke, H. H., Moursi, W. M.: On the Douglas–Rachford algorithm. Math. Program. 164(1), 263–284 (2017). https://doi.org/10.1007/s10107-016-1086-3MathSciNetCrossRef

11.

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). https://doi.org/10.1016/j.jmaa.2014.06.075MathSciNetCrossRef

12.

Bauschke, H. H., Ouyang, H., Wang, X.: On circumcenters of finite sets in Hilbert spaces. Linear Nonlinear Anal. 4(2), 271–295 (2018)MathSciNetMATH

13.

Bauschke, H. H., Ouyang, H., Wang, X.: Circumcentered methods induced by isometries. arXiv:1908.11576 (2019)

14.

Bauschke, H. H., Ouyang, H., Wang, X.: On circumcenter mappings induced by nonexpansive operators. Pure and Applied Functional Analysis (in press) (2020)

15.

Bauschke, H. H., Ouyang, H., Wang, X.: On the linear convergence of circumcentered isometry methods. arXiv:1912.01063 (2019)

16.

Behling, R., Bello-Cruz, J.Y., Santos, L.R.: Circumcentering the Douglas–Rachford method. Numer. Algorithms 78(3), 759–776 (2018). https://doi.org/10.1007/s11075-017-0399-5MathSciNetCrossRef

17.

Behling, R., Bello-Cruz, J.Y., Santos, L.R.: On the linear convergence of the circumcentered-reflection method. Oper. Res. Lett. 46(2), 159–162 (2018). https://doi.org/10.1016/j.orl.2017.11.018MathSciNetCrossRef

18.

Behling, R., Bello-Cruz, J-Y, Santos, L-R: The block-wise circumcentered–reflection method. Comput. Optim. Appl. 76, 675–699 (2020). https://doi.org/10.1007/s10589-019-00155-0MathSciNetCrossRef

19.

Benoist, J.: The Douglas–Rachford algorithm for the case of the sphere and the line. J. Glob. Optim. 63(2), 363–380 (2015). https://doi.org/10.1007/s10898-015-0296-1MathSciNetCrossRef

20.

Borwein, J.M., Sims, B.: The Douglas–Rachford algorithm in the absence of convexity. In: Bauschke, H.H., Burachik, R.S., Combettes, P.L., Elser, V., Luke, D.R., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering. https://doi.org/10.1007/978-1-4419-9569-8_6. Series Title: Springer Optimization and Its Applications, vol. 49, pp 93–109. Springer, New York (2011)

21.

Borwein, J. M., Tam, M. K.: A cyclic Douglas–Rachford iteration scheme. J. Optim. Theory Appl. 160(1), 1–29 (2014). https://doi.org/10.1007/s10957-013-0381-xMathSciNetCrossRef

22.

Borwein, J. M., Tam, M. K.: The cyclic Douglas-Rachford method for inconsistent feasibility problems. J. Nonlinear Convex Anal. Int. J. 16 (4), 573–584 (2015)MathSciNetMATH

23.

Cucker, F., Peña, J., Roshchina, V.: Solving second-order conic systems with variable precision. Math. Program. 150(2), 217–250 (2015). https://doi.org/10.1007/s10107-014-0767-zMathSciNetCrossRef

24.

Dizon, N., Hogan, J., Lindstrom, S.B.: Circumcentering reflection methods for nonconvex feasibility problems. arXiv:1910.04384 (2019)

25.

Dolan, E. D., Moré, J. J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002). https://doi.org/10.1007/s101070100263MathSciNetCrossRef

26.

Douglas, J., Rachford Jr., 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). https://doi.org/10.1090/S0002-9947-1956-0084194-4MathSciNetCrossRef

27.

Euclid, H.T.L.: The Thirteen Books of Euclid’s Elements, 2nd edn., vol. II. Dover Publications, Inc., New York (1956)

28.

Lindstrom, S. B., Sims, B.: Survey: Sixty years of Douglas–Rachford. arXiv:1809.07181 (2018)

29.

Lobo, M. S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284(1-3), 193–228 (1998). https://doi.org/10.1016/S0024-3795(98)10032-0MathSciNetCrossRef

30.

Ouyang, H.: Circumcenter operators in Hilbert spaces. Master Thesis, University of British Columbia, Okanagan CA. https://doi.org/10.14288/1.0371095 (2018)

31.

Phan, H. M.: Linear convergence of the Douglas–Rachford method for two closed sets. Optimization 65(2), 369–385 (2016). https://doi.org/10.1080/02331934.2015.1051532MathSciNetCrossRef

32.

Pierra, G.: Decomposition through formalization in a product space. Math. Program. 28 (1), 96–115 (1984). https://doi.org/10.1007/BF02612715MathSciNetCrossRef

33.

Svaiter, B. F.: On weak convergence of the Douglas–Rachford method. SIAM J. Control Optim. 49(1), 280–287 (2011). https://doi.org/10.1137/100788100MathSciNetCrossRef

Title: On the circumcentered-reflection method for the convex feasibility problem
Authors: Roger Behling
Yunier Bello-Cruz
Luiz-Rafael Santos
Publication date: 01-08-2020
Publisher: Springer US
Published in: Numerical Algorithms / Issue 4/2021
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-020-00941-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 4/2021

Proximal point algorithms based on S-iterative technique for nearly asymptotically quasi-nonexpansive mappings and applications

Continuous and discrete zeroing dynamics models using JMP function array and design formula for solving time-varying Sylvester-transpose matrix inequality

Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation

A novel alternating-direction implicit spectral Galerkin method for a multi-term time-space fractional diffusion equation in three dimensions

Accurate sampling formula for approximating the partial derivatives of bivariate analytic functions

On equivalence of three-parameter iterative methods for singular symmetric saddle-point problem

Premium Partner