Skip to main content
SpringerLink
Log in

The Method of Alternating Relaxed Projections for Two Nonconvex Sets

  • Published:
Vietnam Journal of Mathematics Aims and scope Submit manuscript

Abstract

The Method of Alternating Projections (MAP), a classical algorithm for solving feasibility problems, has recently been intensely studied for nonconvex sets. However, intrinsically available are only local convergence results: convergence occurs if the starting point is not too far away from solutions to avoid getting trapped in certain regions. Instead of taking full projection steps, it can be advantageous to underrelax, i.e., to move only part way towards the constraint set, in order to enlarge the regions of convergence.

In this paper, we thus systematically study the Method of Alternating Relaxed Projections (MARP) for two (possibly nonconvex) sets. Complementing our recent work on MAP, we establish local linear convergence results for the MARP. Several examples illustrate our analysis.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. We follow a common but convenient abuse of notation and write a n =P A b n−1 etc. if the set of nearest points is a singleton.

  2. This will follow from Example 7 below.

  3. Note that one may alternatively require that (2) only holds eventually at the expense of possibly enlarging M; see, e.g., [9, Remark 3.7].

  4. In fact, the results in this section hold true in any complete metric space.

References

  1. Aharoni, R., Censor, Y.: Block-iterative projection methods for parallel computation of solutions to convex feasibility problems. Linear Algebra Appl. 120, 165–175 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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  Google Scholar 

  3. Baillon, J.-B., Combettes, P.L., Cominetti, R.: Asymptotic behaviour of compositions of under-relaxed nonexpansive operators. arXiv:1304.7078 (2013)

  4. Bauschke, H.H.: The approximation of fixed points of compositions of nonexpansive mappings in Hilbert space. J. Math. Anal. Appl. 202, 150–159 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bauschke, H.H., Borwein, J.M.: On the convergence of von Neumann’s alternating projection algorithm for two sets. Set-Valued Anal. 1, 185–212 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996)

    Article  MathSciNet  MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

  8. Bauschke, H.H., Luke, D.R., Phan, H.M., Wang, X.: Restricted normal cones and the method of alternating projections: theory. Set-Valued Var. Anal. 21, 431–473 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bauschke, H.H., Luke, D.R., Phan, H.M., Wang, X.: Restricted normal cones and the method of alternating projections: applications. Set-Valued Var. Anal. 21, 475–501 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  10. Borwein, J.M., Vanderwerff, J.D.: Convex Functions. Cambridge University Press, Cambridge (2010)

    MATH  Google Scholar 

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

  12. Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces. Lect. Notes Math., vol. 2057. Springer, Berlin (2012)

    MATH  Google Scholar 

  13. Censor, Y., Zenios, S.A.: Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press, New York (1997)

    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. Combettes, P.L., Trussell, H.J.: Method of successive projections for finding a common point of sets in metric spaces. J. Optim. Theory Appl. 67, 487–507 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  16. Deutsch, F.: Best Approximation in Inner Product Spaces. Springer, New York (2001)

    Book  MATH  Google Scholar 

  17. Deutsch, F., Hundal, H.: The rate of convergence for the cyclic projections algorithm I: angles between convex sets. J. Approx. Theory 142, 36–55 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  18. Deutsch, F., Hundal, H.: The rate of convergence for the cyclic projections algorithm II: norms of nonlinear operators. J. Approx. Theory 142, 56–82 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  19. Deutsch, F., Hundal, H.: The rate of convergence for the cyclic projections algorithm III: regularity of convex sets. J. Approx. Theory 155, 155–184 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  20. Goebel, K., Kirk, W.A.: Topics in Metric Fixed Point Theory. Cambridge University Press, Cambridge (1990)

    Book  MATH  Google Scholar 

  21. Goebel, K., Reich, S.: Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings. Dekker, New York (1984)

    MATH  Google Scholar 

  22. Gubin, L.G., Polyak, B.T., Raik, E.V.: The method of projections for finding the common point of convex sets. USSR Comput. Math. Math. Phys. 7, 1–24 (1967)

    Article  Google Scholar 

  23. Lewis, A.S., Luke, D.R., Malick, J.: Local linear convergence for alternating and averaged nonconvex projections. Found. Comput. Math. 9, 485–513 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  24. Luke, D.R.: Finding best approximation pairs relative to a convex and prox-regular set in a Hilbert space. SIAM J. Optim. 19, 714–739 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  25. Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation I. Springer, Berlin (2006)

    Google Scholar 

  26. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    MATH  Google Scholar 

  27. Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis, corrected 3rd printing edn. Springer, Berlin (2009)

    MATH  Google Scholar 

  28. von Neumann, J.: Functional Operators, Vol. II: The Geometry of Orthogonal Spaces. Annals of Mathematical Studies, vol. 22. Princeton University Press, Princeton (1950)

    MATH  Google Scholar 

  29. Wang, X., Bauschke, H.H.: Compositions and averages of two resolvents: relative geometry of fixed point sets and a partial answer to a question by C. Byrne. Nonlinear Anal. 20, 131–153 (2012)

    MathSciNet  MATH  Google Scholar 

  30. Wiener, N.: On the factorization of matrices. Comment. Math. Helv. 29, 97–111 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  31. Zălinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, Singapore (2002)

    Book  MATH  Google Scholar 

Download references

Acknowledgements

The authors are grateful to two referees for their pertinent and constructive comments. H.H.B. was partially supported by a Discovery Grant and an Accelerator Supplement of the Natural Sciences and Engineering Research Council of Canada and by the Canada Research Chair Program. H.M.P. was supported by a PIMS postdoctoral fellowship, University of British Columbia Okanagan internal grant, and University of Victoria internal grant. X.W. was partially supported by a Discovery Grant of the Natural Sciences and Engineering Research Council of Canada.

Author information

Authors and Affiliations

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

    Heinz H. Bauschke & Xianfu Wang

  2. Mathematics and Statistics, University of Victoria, PO Box 3060 STN CSC, Victoria, BC, V8W 3R4, Canada

    Hung M. Phan

Authors
  1. Heinz H. Bauschke
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hung M. Phan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xianfu Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Heinz H. Bauschke.

Additional information

Dedicated to Boris Mordukhovich on the occasion of his 65th Birthday.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bauschke, H.H., Phan, H.M. & Wang, X. The Method of Alternating Relaxed Projections for Two Nonconvex Sets. Vietnam J. Math. 42, 421–450 (2014). https://doi.org/10.1007/s10013-013-0049-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10013-013-0049-8

Keywords

Mathematics Subject Classification (2010)

Search

Navigation