[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the order of the operators in the Douglas–Rachford algorithm

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

The Douglas–Rachford algorithm is a popular method for finding zeros of sums of monotone operators. By its definition, the Douglas–Rachford operator is not symmetric with respect to the order of the two operators. In this paper we provide a systematic study of the two possible Douglas–Rachford operators. We show that the reflectors of the underlying operators act as bijections between the fixed points sets of the two Douglas–Rachford operators. Some elegant formulae arise under additional assumptions. Various 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. Recall that \(A:X\rightrightarrows X\) is monotone if whenever the pairs (x, u) and (y, v) lie in \({\text {gra}}A\) we have \(\langle x-y,u-v\rangle \ge 0\), and is maximally monotone if it is monotone and any proper enlargement of the graph of A (in terms of set inclusion) does not preserve the monotonicity of A.

  2. The identity operator on X is denoted by \({\text {{Id}}}\). It is well-known that, when A is maximally monotone, \(J_A\) is single-valued, maximally monotone and firmly nonexpansive and \(R_A\) is nonexpansive.

  3. Suppose that C and D are two nonempty subsets of X. We recall that \(Q:C\rightarrow D\) is an isometry if \((\forall x\in C)(\forall y\in C)\) \(||Qx-Qy||=||x-y||\). The set of fixed points of T is \({\text {Fix}}T:=\big \{{x\in X}~\big |~{x=Tx}\big \}\).

  4. Throughout the paper we use \(N_C\) and \(P_C\) to denote the normal cone and projector associated with a nonempty closed convex subset C of X respectively.

  5. We set and .

  6. For further information on the extended solution set, we refer the reader to [15, Section 2.1].

  7. See [19] for definition and detailed discussion on paramonotone operators.

  8. In passing, we point out that this is equivalent to saying that \(A=N_U\) and \(B=N_V\) where U and V are closed affine subspaces of X. Indeed, \(R_A^2={\text {{Id}}}\iff J_A=J_A^2\) and therefore we conclude that \({\text {ran}}J_A={\text {Fix}}J_A\). Combining with [25, Theorem 1.2] yields that \(J_A\) is a projection, hence A is an affine normal cone operator using [6, Example 23.4].

  9. Recall the when A is maximally monotone the inverse resolvent identity states that \(J_A+J_{A^{-1}}={\text {{Id}}}\). Consequently, \(R_{A^{-1}}=-R_A\).

  10. For every \(x\in \mathbb {R}\), we set \(x^+:=\max \{x,0\}\) and \(x^{-}:=\min \{x,0\}.\)

  11. See [4, Proposition 3.5] for the case when U and V are linear subspaces.

References

  1. Aragón Artacho, F.J., Borwein, J.M.: Global convergence of a non-convex Douglas-Rachford iteration. J. Glob. Optim. 57, 753–769 (2013). doi:10.1007/s10898-012-9958-4

    Article  MATH  Google Scholar 

  2. Aragón Artacho, F.J., Borwein, J.M., Tam, M.K.: Recent results on Douglas-Rachford methods for combinatorial optimization problems. J. Glob. Optim. 163, 1–30 (2014). doi:10.1007/s10957-013-0488-0

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  5. 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 

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

  7. Bauschke, H.H., Dao, M.N., Noll D., Phan H.M.: On Slater’s condition and finite convergence of the Douglas-Rachford algorithm, arXiv:1504.06969 [math.OC]

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Bauschke, H.H., Noll, D., Phan, H.M.: Linear and strong convergence of algorithms involving averaged nonexpansive operators. J. Math. Anal. Appl. 421, 1–20 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  10. Borwein, J.M., Sims, B.: The Douglas-Rachford algorithm in the absence of convexity, Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Optimization and Applications, 49th edn, pp. 93–109. Springer, New York (2011)

    Google Scholar 

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

    MathSciNet  Google Scholar 

  12. Borwein, J.M., Tam, M.K.: A cyclic Douglas-Rachford iteration scheme. J. Optim.Theory Appl. 160, 1–29 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  13. 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 

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

    Article  MathSciNet  MATH  Google Scholar 

  15. Eckstein, J., Svaiter, B.F.: A family of projective splitting methods for the sum of two maximal monotone operators. Math. Progr. Series B 111, 171–199 (2008)

    MathSciNet  Google Scholar 

  16. GeoGebra, URL: http://www.geogebra.org

  17. 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 

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

    Article  MathSciNet  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  21. Phan H.M: Linear convergence of the Douglas-Rachford method for two closed sets, arXiv:1401.6509v3 [math.OC]

  22. Rockafellar R.T., Wets R.J-B.: Variational Analysis, Springer-Verlag, corrected 3rd printing, 2009

  23. Spingarn, J.E.: A primal-dual projection method for solving systems of linear inequalities. Linear Algeb. Appl. 65, 45–62 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  24. Yan, M., Yin, W.: Self equivalence of the alternating direction method of multipliers, arXiv:1407.7400v3 [math.OC]

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

    Google Scholar 

Download references

Acknowledgments

The authors thank an anonymous referee for constructive comments and very careful reading, and Matt Tam and Wotao Yin for bringing, respectively, [11, 24] to our attention. HHB was partially supported by the Natural Sciences and Engineering Research Council of Canada and by the Canada Research Chair Program. WMM was partially supported by the Natural Sciences and Engineering Research Council of Canada of HHB.

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 order of the operators in the Douglas–Rachford algorithm. Optim Lett 10, 447–455 (2016). https://doi.org/10.1007/s11590-015-0920-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-015-0920-5

Keywords

Mathematics Subject Classification

Search

Navigation