Abstract

We study the usage of regularity properties of collections of sets in convergence analysis of alternating projection methods for solving feasibility problems. Several equivalent characterizations of these properties are provided. Two settings of inexact alternating projections are considered and the corresponding convergence estimates are established and discussed.

Author information

Contact details are reproduced from the original publication and may be historical.

Alexander Y. Kruger

Centre for Informatics and Applied Optimization, Faculty of Science and Technology, Federation University Australia, POB 663, Ballarat, Vic. 3350, Australia

a.kruger@federation.edu.au

Nguyen H. Thao

Centre for Informatics and Applied Optimization, Faculty of Science and Technology, Federation University Australia, POB 663, Ballarat, Vic. 3350, Australia

nhthao@ctu.edu.vn

Keywords

  • Alternating projections
  • uniform regularity
  • normal cone
  • subdifferential

Mathematics Subject Classification

49J53, 49K27, 58E30

References

  1. H. Attouch, J. Bolte, P. Redont, A. Soubeyran: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka–Lojasiewicz inequality, Math. Oper. Res. 35(2) (2010) 438–457.https://doi.org/10.1287/moor.1100.0449Google Scholar
  2. D. Aussel, A. Daniilidis, L. Thibault: Subsmooth sets: functional characterizations and related concepts, Trans. Amer. Math. Soc. 357(4) (2005) 1275–1301.https://doi.org/10.1090/S0002-9947-04-03718-3Google Scholar
  3. H. H. Bauschke, J. M. Borwein: On the convergence of von Neumann’s alternating projection algorithm for two sets, Set-Valued Anal. 1(2) (1993) 185–212.https://doi.org/10.1007/BF01027691Google Scholar
  4. H. H. Bauschke, D. R. Luke, H. M. Phan, X. Wang: Restricted normal cones and the method of alternating projections: applications, Set-Valued Var. Anal. 21(3) (2013) 475–501.https://doi.org/10.1007/s11228-013-0238-3Google Scholar
  5. H. H. Bauschke, D. R. Luke, H. M. Phan, X. Wang: Restricted normal cones and the method of alternating projections: theory, Set-Valued Var. Anal. 21(3) (2013) 431–473.https://doi.org/10.1007/s11228-013-0239-2Google Scholar
  6. L. M. Bregman: The method of successive projection for finding a common point of convex sets, Sov. Math., Dokl. 6 (1965) 688–692.Google Scholar
  7. F. H. Clarke, R. J. Stern, P. R. Wolenski: Proximal smoothness and the lower-C 2 property, J. Convex Analysis 2 (1995) 97–116.https://doi.org/10.68381/jca02008Google Scholar
  8. E. De Giorgi, A. Marino, M. Tosques: Problems of evolution in metric spaces and maximal decreasing curve, Atti Accad. Naz. Lincei, VIII. Ser., Rend., Cl. Sci. Fis. Mat. Nat. 68(3) (1980) 180–187 (in Italian).Google Scholar
  9. A. L. Dontchev, R. T. Rockafellar: Implicit Functions and Solution Mappings. A View from Variational Analysis, Springer Monographs in Mathematics, Springer, Dordrecht (2009).https://doi.org/10.1007/978-0-387-87821-8Google Scholar
  10. D. Drusvyatskiy, A. D. Ioffe, A. S. Lewis: Alternating projections and coupling slope, arXiv:1401.7569 [math.OC] (2014) 1–17.Google Scholar
  11. D. Drusvyatskiy, A. D. Ioffe, A. S. Lewis: Transversality and alternating projections for nonconvex sets, Found. Comput. Math. 15(6) (2015) 1637–1651.https://doi.org/10.1007/s10208-015-9279-3Google Scholar
  12. M. J. Fabian, R. Henrion, A. Y. Kruger, J. V. Outrata: Error bounds: necessary and sufficient conditions, Set-Valued Var. Anal. 18(2) (2010) 121–149.https://doi.org/10.1007/s11228-010-0133-0Google Scholar
  13. A. D. Ioffe: Metric regularity and subdifferential calculus, Russ. Math. Surv. 55 (2000) 501–558.https://doi.org/10.1070/RM2000v055n03ABEH000292Google Scholar
  14. A. Y. Kruger: Stationarity and regularity of set systems, Pac. J. Optim. 1(1) (2005) 101–126.Google Scholar
  15. A. Y. Kruger: About regularity of collections of sets, Set-Valued Anal. 14(2) (2006) 187–206.https://doi.org/10.1007/s11228-006-0014-8Google Scholar
  16. A. Y. Kruger: About stationarity and regularity in variational analysis, Taiwanese J. Math. 13(6A) (2009) 1737–1785.https://doi.org/10.11650/twjm/1500405612Google Scholar
  17. A. Y. Kruger, M. A. López: Stationarity and regularity of infinite collections of sets, J. Optim. Theory Appl. 154(2) (2012) 339–369.https://doi.org/10.1007/s10957-012-0043-4Google Scholar
  18. A. Y. Kruger, N. H. Thao: About uniform regularity of collections of sets, Serdica Math. J. 39 (2013) 287–312.Google Scholar
  19. A. Y. Kruger, N. H. Thao: Quantitative characterizations of regularity properties of collections of sets, J. Optim. Theory Appl. 164(1) (2015) 41–67.https://doi.org/10.1007/s10957-014-0556-0Google Scholar
  20. A. S. Lewis, D. R. Luke, J. Malick: Local linear convergence for alternating and averaged nonconvex projections, Found. Comput. Math. 9(4) (2009) 485–513.https://doi.org/10.1007/s10208-008-9036-yGoogle Scholar
  21. A. S. Lewis, J. Malick: Alternating projection on manifolds, Math. Oper. Res. 33(1) (2008) 216–234.https://doi.org/10.1287/moor.1070.0291Google Scholar
  22. B. S. Mordukhovich: Variational Analysis and Generalized Differentiation. I: Basic Theory, Grundlehren der Mathematischen Wissenschaften 331, Springer, Berlin (2006).https://doi.org/10.1007/3-540-31246-3Google Scholar
  23. D. Noll, A. Rondepierre: On local convergence of the method of alternating projections, Found. Comput. Math. 16(2) (2015) 425–455.https://doi.org/10.1007/s10208-015-9253-0Google Scholar
  24. R. A. Poliquin, R. T. Rockafellar, L. Thibault: Local differentiability of distance functions, Trans. Amer. Math. Soc. 352(11) (2000) 5231–5249.https://doi.org/10.1090/S0002-9947-00-02550-2Google Scholar
  25. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  26. A. Shapiro: Existence and differentiability of metric projections in Hilbert spaces, SIAM J. Optim. 4(1) (1994) 130–141.https://doi.org/10.1137/0804006Google Scholar

Suggested citation

A. Y. Kruger, N. H. Thao. “Regularity of Collections of Sets and Convergence of Inexact Alternating Projections.” Journal of Convex Analysis 23 (2016), No. 3, 823–847. https://doi.org/10.68381/jca23031

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2016. Rights now held by Banach Press LLC.