Skip to main content
SpringerLink
Log in

A new projection method for finding the closest point in the intersection of convex sets

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper we present a new iterative projection method for finding the closest point in the intersection of convex sets to any arbitrary point in a Hilbert space. This method, termed AAMR for averaged alternating modified reflections, can be viewed as an adequate modification of the Douglas–Rachford method that yields a solution to the best approximation problem. Under a constraint qualification at the point of interest, we show strong convergence of the method. In fact, the so-called strong CHIP fully characterizes the convergence of the AAMR method for every point in the space. We report some promising numerical experiments where we compare the performance of AAMR against other projection methods for finding the closest point in the intersection of pairs of finite dimensional subspaces.

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
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

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

    Article  MathSciNet  MATH  Google Scholar 

  2. Aragón Artacho, F.J., Borwein, J.M., Tam, M.K.: Douglas–Rachford feasibility methods for matrix completion problems. ANZIAM J. 55(4), 299–326 (2014)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  5. Aronszajn, L.: Theory of reproducing kernels. Trans. Am. Math. Soc. 68, 337–404 (1950)

    Article  MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Bauschke, H.H., Borwein, J.M.: Dykstra’s alternating projection algorithm for two sets. J. Approx. Theory 79(3), 418–443 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  10. Bauschke, H.H., Borwein, J.M., Tseng, P.: Bounded linear regularity, strong CHIP, and CHIP are distinct properties. J. Convex Anal. 7(2), 395–412 (2000)

    MathSciNet  MATH  Google Scholar 

  11. Bauschke, H.H., Combettes, P.L.: A weak-to-strong convergence principle for Fejér-monotone methods in Hilbert spaces. Math. Oper. Res. 26(2), 248–264 (2001)

    Article  MathSciNet  MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

  13. Bauschke, H.H., Combettes, P.L., Luke, D.R.: A strongly convergent reflection method for finding the projection onto the intersection of two closed convex sets in a Hilbert space. J. Approx. Theory 141, 63–69 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  14. Bauschke, H.H., Cruz, J.B., Nghia, T.T., 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 

  15. Bauschke, H.H., Cruz, J.B., Nghia, T.T., 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–44 (2015)

    MathSciNet  Google Scholar 

  16. Bauschke, H.H., Koch, V.R.: Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces. Contemp. Math. 636, 1–40 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  17. Bauschke, H.H., Matoušková, E., Reich, S.: Projection and proximal point methods: convergence results and counterexamples. Nonlinear Anal. 56(5), 715–738 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  18. Bauschke, H.H., Moursi, W.M.: On the Douglas–Rachford algorithm. Math. Program. 164((1—-2)), 263–284 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  19. Bauschke, H.H., Noll, D.: On the local convergence of the Douglas–Rachford algorithm. Arch. Math. 102(6), 589–600 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  20. Benoist, J.: The Douglas–Rachford algorithm for the case of the sphere and the line. J. Global Optim. 63(2), 363–380 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  21. Borwein, J.M., Li, G., Yao, L.: Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets. SIAM J. Optim. 24(1), 498–527 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  22. Borwein, J.M., Sims, B.: The Douglas–Rachford algorithm in the absence of convexity. In: Bauschke, H.H., Burachik, R., Combettes, P.L., Elser, V., Luke, D.R., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 93–109. Springer-Verlag, New York (2011)

    Chapter  Google Scholar 

  23. Boyle, J.P., Dykstra, R.L.: A method for finding projections onto the intersection of convex sets in Hilbert spaces. Advances in order restricted statistical inference, 28–47. Lecture Notes in Statist., 37. Springer, Berlin (1986)

  24. Burachik, R.S., Jeyakumar, V.: A simple closure condition for the normal cone intersection formula. Proc. Am. Math. Soc. 133(6), 1741–1748 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  25. Cegielski, A.: Iterative methods for fixed point problems in Hilbert spaces. Lecture Notes in Mathematics, vol. 2057. Springer, Heidelberg (2012)

  26. Censor, Y., Cegielski, A.: Projection methods: an annotated bibliography of books and reviews. Optimization 64(11), 2343–2358 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  27. Cinderella software. http://www.cinderella.de

  28. Chui, C.K., Deutsch, F., Ward, J.D.: Constrained best approximation in Hilbert space. Constr. Approx. 6(1), 35–64 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  29. Chui, C.K., Deutsch, F., Ward, J.D.: Constrained best approximation in Hilbert space II. J. Approx. Theory 71(2), 213–238 (1992)

    Article  MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  31. Deutsch, F.: Rate of convergence of the method of alternating projections. Parametric optimization and approximation (Oberwolfach, 1983), 96107, Internat. Schriftenreihe Numer. Math., 72. Birkhäuser, Basel (1985)

  32. Deutsch, F.: Best Approximation in Inner Product Spaces. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer-Verlag, New York (2001)

    Book  Google Scholar 

  33. Deutsch, F., Hundal, H.: The rate of convergence for the method of alternating projections. II. J. Math. Anal. Appl. 205(2), 381–405 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  34. Deutsch, F., Li, W., Ward, J.D.: A dual approach to constrained interpolation from a convex subset of Hilbert space. J. Approx. Theory 90(3), 385–414 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  35. Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82, 421–439 (1956)

    Article  MathSciNet  MATH  Google Scholar 

  36. Dykstra, R.L.: An algorithm for restricted least squares regression. J. Am. Statist. Assoc. 78(384), 837–842 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  37. Escalante, R., Raydan, M.: Alternating Projection Methods. Fundamentals of Algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2011)

    Book  MATH  Google Scholar 

  38. Halperin, I.: The product of projection operators. Acta Sci. Math. (Szeged) 23, 96–99 (1962)

    MathSciNet  MATH  Google Scholar 

  39. Halpern, B.: Fixed points of nonexpanding maps. Bull. AMS 73, 957–961 (1967)

    Article  MathSciNet  MATH  Google Scholar 

  40. Haugazeau, Y.: Sur les inequality variationnelles etla minimmization de fonctionnelles convexes. Université de Paris, France, Thèse (1968)

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

    Article  MathSciNet  MATH  Google Scholar 

  42. Hundal, H.S.: An alternating projection that does not converge in norm. Nonlinear Anal. 57(1), 35–61 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  43. Kopecká, E., Reich, S.: A note on the von Neumann alternating projections algorithm. J. Nonlinear Convex Anal. 5(3), 379–386 (2004)

    MathSciNet  MATH  Google Scholar 

  44. Kruger, A.Y., Luke, D.R., Thao, N.H.: Set regularities and feasibility problems. Math. Program., Ser. B. (2016). doi:10.1007/s10107-016-1039-x

  45. Lewis, A.S., Malick, J.: Alternating projections on manifolds. Math. Oper. Res. 33(1), 216–234 (2008)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

  48. Matoušková, E., Reich, S.: The Hundal example revisited. J. Nonlinear Convex Anal. 4(3), 411–427 (2003)

    MathSciNet  MATH  Google Scholar 

  49. Von Neumann, J.: Functional operators II: The geometry of orthogonal spaces. Princeton University Press (1950). (Reprint of mimeographed lecture notes first distributed in 1933.)

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

    Article  MathSciNet  MATH  Google Scholar 

  51. Phan, H.M.: Linear convergence of the Douglas–Rachford method for two closed sets. Optimization 65(2), 369–385 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  52. Pierra, G.: Decomposition through formalization in a product space. Math. Program. 28, 96–115 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  53. Reich, S., Zalas, R.: A modular string averaging procedure for solving the common fixed point problem for quasi-nonexpansive mappings in Hilbert space. Numer. Algor. 72(2), 297–323 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  54. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton, N.J. (1970)

    Book  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors thank Heinz Bauschke for his careful reading of a previous version of this paper, and for making various perceptive comments and suggestions. We also thank D. Russell Luke for his insightful comments. We are indebted to one of the referees for a number of constructive suggestions and for pointing us to reference [30], which led us to prove strong convergence of the shadow sequence in Theorem 4.1. This work was partially supported by MINECO of Spain and ERDF of EU, Grant MTM2014-59179-C2-1-P. F.J. Aragón Artacho was supported by the Ramón y Cajal program by MINECO of Spain and ERDF of EU (RYC-2013-13327) and R. Campoy was supported by MINECO of Spain and ESF of EU (BES-2015-073360) under the program “Ayudas para contratos predoctorales para la formación de doctores 2015”.

Author information

Authors and Affiliations

  1. University of Alicante, 03080, Alicante, Spain

    Francisco J. Aragón Artacho & Rubén Campoy

Authors
  1. Francisco J. Aragón Artacho
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rubén Campoy
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francisco J. Aragón Artacho.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Aragón Artacho, F.J., Campoy, R. A new projection method for finding the closest point in the intersection of convex sets. Comput Optim Appl 69, 99–132 (2018). https://doi.org/10.1007/s10589-017-9942-5

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-017-9942-5

Keywords

Mathematics Subject Classification

Search

Navigation