[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

On the Douglas–Rachford algorithm

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

The Douglas–Rachford algorithm is a very popular splitting technique for finding a zero of the sum of two maximally monotone operators. The behaviour of the algorithm remains mysterious in the general inconsistent case, i.e., when the sum problem has no zeros. However, more than a decade ago, it was shown that in the (possibly inconsistent) convex feasibility setting, the shadow sequence remains bounded and its weak cluster points solve a best approximation problem. In this paper, we advance the understanding of the inconsistent case significantly by providing a complete proof of the full weak convergence in the convex feasibility setting. In fact, a more general sufficient condition for the weak convergence in the general case is presented. Our proof relies on a new convergence principle for Fejér monotone sequences. Numerous examples illustrate our results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. To the best of our knowledge, the Douglas–Rachford algorithm has never been applied in infinite-dimensional spaces; nonetheless, Svaiter’s result is a milestone in abstract infinite-dimensional optimization.

  2. Let \(w\in X\) be fixed. The inner and outer shifts associated with A are defined by \({A}{_w}: X\rightrightarrows X :x \mapsto A(x-w)\) and . Note that \(A_{w}\) and \({_w}A\) are maximally monotone because A is.

  3. Suppose that U is a closed affine subspace of X. We use \({\text {par}}U\) to denote the parallel space of U which is defined by \({\text {par}}U=U-U\).

  4. It follows from [7, Corollary 3.20] that \(P_U\) is linear, hence, \(P_UR_U=P_U(2P_U-{\text {{ Id}}})=2P_U-P_U=P_U\).

  5. \(A:X\rightrightarrows X\) is a linear relation if \({\text {gra}}A\) is a linear subspace of \(X\times X\).

References

  1. Aragón Artacho, F.J., Borwein, J.M., Tam, M.K.: Recent results on Douglas–Rachford methods for combinatorial optimization problems. J. Global Optim. 163, 1–30 (2014)

  2. Aragón Artacho, F.J., Borwein, J.M.: Global convergence of a non-convex Douglas–Rachford iteration. J. Global Optim. 57, 753–769 (2013)

  3. Attouch, H., Théra, M.: A general duality principle for the sum of two operators. J. Convex Anal. 3, 1–24 (1996)

    MathSciNet  MATH  Google Scholar 

  4. Baillon, J.B., Bruck, R.E., Reich, S.: On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces. Houst. J. Math. 4, 1–9 (1978)

    MathSciNet  MATH  Google Scholar 

  5. Bauschke, H.H.: Projection algorithms and monotone operators. PhD thesis, Simon Fraser University, Burnaby, B.C., Canada (August 1996)

  6. Bauschke, H.H.: A note on the paper by Eckstein and Svaiter on ‘General projective splitting for sums of maximal monotone operators’. SIAM J. Control Optim. 48, 2513–2515 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011)

    Book  MATH  Google Scholar 

  8. Bauschke, H.H., Moursi, W.M.: The Douglas–Rachford algorithm for two (not necessarily intersecting) affine subspaces. SIAM J. Optim. 26, 968–985 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bauschke, H.H., Lukens, B., Moursi, W.M.: Affine nonexpansive operators, Attouch–Théra duality and the Douglas–Rachford algorithm. arXiv:1603.09418 [math.OC]

  10. Bauschke, H.H., Combettes, P.L., Luke, D.R.: Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization. J. Opt. Soc. Am. 19, 1334–1345 (2002)

    Article  MathSciNet  Google Scholar 

  11. Bauschke, H.H., Combettes, P.L., Luke, D.R.: Finding best approximation pairs relative to two closed convex sets in Hilbert spaces. J. Approx. Theory 127, 178–192 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bauschke, H.H., Wang, X., Yao, L.: Examples of discontinuous maximal monotone linear operators and the solution to a recent problem posed by B.F. Svaiter. J. Math. Anal. Appl. 370, 224–241 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Bauschke, H.H., Moffat, S.M., Wang, X.: Firmly nonexpansive mappings and maximally monotone operators: correspondence and duality. Set-Valued Var. Anal. 20, 131–153 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  14. Bauschke, H.H., Boţ, R.I., Hare, W.L., Moursi, W.M.: Attouch-Théra duality revisited: paramonotonicity and operator splitting. J. Approx. Theory 164, 1065–1084 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. 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)

  16. Bauschke, H.H., Hare, W.L., Moursi, W.M.: Generalized solutions for the sum of two maximally monotone operators. SIAM J. Control Optim. 52, 1034–1047 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  17. Bauschke, H.H., Dao, M.N., Moursi, W.M.: On Fejér monotone sequences and nonexpansive mappings. Linear Nonlinear Anal. 1, 287–295 (2015)

    MathSciNet  MATH  Google Scholar 

  18. Bauschke, H.H., Hare, W.L., Moursi, W.M.: On the range of the Douglas–Rachford operator. Math. Oper. Res. 41, 884–897 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  19. Borwein, J.M.: Fifty years of maximal monotonicity. Optim. Lett. 4, 473–490 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  20. 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, Optimization and Applications 49. Springer, New York (2011)

    Google Scholar 

  21. Borwein, J.M., Tam, M.K.: The cyclic Douglas–Rachford method for inconsistent feasibility problems. J. Nonlinear Convex Anal. 16, 537–584 (2015)

    MathSciNet  MATH  Google Scholar 

  22. Brezis, H.: Operateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert, North-Holland/Elsevier (1973)

  23. Brezis, H., Haraux, A.: Image d’une Somme d’opérateurs monotones et applications. Isr. J. Math. 23, 165–186 (1976)

    Article  MATH  Google Scholar 

  24. Bruck, R.E., Reich, S.: Nonexpansive projections and resolvents of accretive operators in Banach spaces. Houst. J. Math. 3, 459–470 (1977)

    MathSciNet  MATH  Google Scholar 

  25. Burachik, R.S., Iusem, A.N.: Set-Valued Mappings and Enlargements of Monotone Operators. Springer, Berlin (2008)

    MATH  Google Scholar 

  26. Combettes, P.L.: Inconsistent signal feasibility problems: least-squares solutions in a product space. IEEE Trans. Signal Process. 42, 2955–2966 (1994)

    Article  Google Scholar 

  27. Combettes, P.L.: The convex feasibility problem in image recovery. Adv. Imaging Electron Phys. 25, 155–270 (1995)

    Google Scholar 

  28. Combettes, P.L.: Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53, 475–504 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  29. Combettes, P.L.: Iterative construction of the resolvent of a sum of maximal monotone operators. J. Convex Anal. 16, 727–748 (2009)

    MathSciNet  MATH  Google Scholar 

  30. Combettes, P.L., Pesquet, J.-C.: A Douglas–Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE J. Sel. Top. Signal Process. 1, 564–574 (2007)

    Article  Google Scholar 

  31. Combettes, P.L., Pesquet, J.-C.: A proximal decomposition method for solving convex variational inverse problems. Inverse Probl. 24, 065014 (2008)

  32. Combettes, P.L., Pesquet, J.-C.: Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping. SIAM J. Optim. 25, 1221–1248 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  33. Douglas, J., Rachford, H.H.: On the numerical solution of the heat conduction problem in 2 and 3 space variables. Trans. AMS 82, 421–439 (1956)

    Article  MathSciNet  MATH  Google Scholar 

  34. Drusvyatskiy, D., Li, C.-K., Pelejo, D.C., Voronin, Y.-L., Wolkowicz, H.: Projection methods for quantum channel construction. Quantum Inf. Process. 14, 3075–3095 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  35. Eckstein, J.: Splitting methods for monotone operators with applications to parallel optimization. Ph.D. thesis, MIT (1989)

  36. Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. Ser. A. 55, 293–318 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  37. Eckstein, J., Svaiter, B.F.: A family of projective splitting methods for the sum of two maximal monotone operators. Math. Program. Ser. B 111, 173–199 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  38. Elser, V., Rankenburg, I.: Deconstructing the energy landscape: constraint-based algorithm for folding heteropolymers. Phys. Rev. E 73, 026702 (2006)

    Article  Google Scholar 

  39. Elser, V., Rankenburg, I., Thibault, P.: Searching with iterated maps. Proc. Natl. Acad. Sci. USA 102, 418–423 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  40. GeoGebra. http://www.geogebra.org

  41. Hesse, R., Luke, D.R.: Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems. SIAM J. Optim. 23, 2397–2419 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  42. Hesse, R., Luke, D.R., Neumann, P.: Alternating projections and Douglas-Rachford for sparse affine feasibility. IEEE Trans. Signal Process. 62, 4868 (2014)

    Article  MathSciNet  Google Scholar 

  43. Iusem, A.N.: On some properties of paramonotone operators. J. Convex Anal. 5, 269–278 (1998)

    MathSciNet  MATH  Google Scholar 

  44. Lieutaud, J.: Approximations d’opérateurs monotones par des méthodes de splitting, doctoral thesis, University of Paris (1969)

  45. Li, G., Pong, T.K.: Douglas–Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems. Math. Prog. Ser. A 159, 371–401 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  46. Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  47. Mercier, B.: Inéquations Variationnelles de la Mécanique (Publications Mathématiques d’Orsay, no. 80.01), Orsay, France: Université de Paris-XI (1980). http://portail.mathdoc.fr/PMO/PDF/M_MERCIER-87

  48. Minty, G.J.: Monotone (nonlinear) operators in Hilbert spaces. Duke Math. J. 29, 341–346 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  49. Pazy, A.: Asymptotic behavior of contractions in Hilbert space. Isr. J. Math. 9, 235–240 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  50. Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Berlin (2009). (Corrected 3rd printing)

    MATH  Google Scholar 

  51. Simons, S.: Minimax and Monotonicity. Springer, Berlin (1998)

    Book  MATH  Google Scholar 

  52. Simons, S.: From Hahn–Banach to Monotonicity. Springer, Berlin (2008)

    MATH  Google Scholar 

  53. Svaiter, B.F.: On weak convergence of the Douglas–Rachford method. SIAM J. Control Optim. 49, 280–287 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  54. Zarantonello, E.H.: Projections on convex sets in Hilbert space and spectral theory. In: Zarantonello, E.H. (ed.) Contributions to Nonlinear Functional Analysis, pp. 237–424. Academic Press, New York (1971)

    Chapter  Google Scholar 

  55. Zeidler, E.: Nonlinear Functional Analysis and Its Applications II/A: Linear Monotone Operators. Springer, Berlin (1990)

    Book  MATH  Google Scholar 

  56. Zeidler, E.: Nonlinear Functional Analysis and Its Applications II/B: Nonlinear Monotone Operators. Springer, Berlin (1990)

    Book  MATH  Google Scholar 

Download references

Acknowledgments

We are grateful to Patrick Combettes for helpful comments and pointing out additional references. We also would like to thank the anonymous referees for comments that were constructive. HHB was partially supported by the Natural Sciences and Engineering Research Council of Canada and by the Canada Research Chair Program.

Author information

Authors and Affiliations

  1. Mathematics, University of British Columbia, Kelowna, BC, V1V 1V7, Canada

    Heinz H. Bauschke & Walaa M. Moursi

  2. Mathematics Department, Faculty of Science, Mansoura University, Mansoura, 35516, Egypt

    Walaa M. Moursi

Authors
  1. Heinz H. Bauschke
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Walaa M. Moursi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Heinz H. Bauschke.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-016-1086-3

Keywords

Mathematics Subject Classification