Abstract

Many iterative methods for solving optimization or feasibility problems have been invented, and often convergence of the iterates to some solution is proven. Under favourable conditions, one might have additional bounds on the distance of the iterate to the solution leading thus to worst case estimates, i.e., how fast the algorithm must converge. Exact convergence estimates are typically hard to come by. In this paper, we consider the complementary problem of finding best case estimates, i.e., how slow the algorithm has to converge, and we also study exact asymptotic rates of convergence. Our investigation focuses on convex feasibility in the Euclidean plane, where one set is the real axis while the other is the epigraph of a convex function. This case study allows us to obtain various convergence rate results. We focus on the popular method of alternating projections and the Douglas-Rachford algorithm. These methods are connected to the proximal point algorithm which is also discussed. Our findings suggest that the Douglas-Rachford algorithm outperforms the method of alternating projections in the absence of constraint qualifications. Various examples illustrate the theory.

Author information

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

Heinz H. Bauschke

Dept. of Mathematics, University of British Columbia, Kelowna, B.C. V1V 1V7, Canada

heinz.bauschke@ubc.ca

Minh N. Dao

Dept. of Mathematics and Informatics, Hanoi National University of Education, 136 Xuan Thuy, Hanoi, Vietnam
and: Dept. of Mathematics, University of British Columbia, Kelowna, B.C. V1V 1V7, Canada

minhdn@hnue.edu.vn

Dominikus Noll

Institut de Mathématiques, Université de Toulouse, 118 route de Narbonne, 31062 Toulouse, France

noll@mip.ups-tlse.fr

Hung M. Phan

Dept. of Mathematical Sciences, University of Massachusetts Lowell, 265 Riverside Street, Olney Hall 428, Lowell, MA 01854, U.S.A.

hung_phan@uml.edu

Keywords

  • Alternating projections
  • convex feasibility problem
  • convex set
  • Douglas-Rachford algorithm
  • projection
  • proximal mapping
  • proximal point algorithm
  • proximity operator

Mathematics Subject Classification

65K05; 65K10, 90C25

References

  1. Y. I. Alber, S. Reich: An iterative method for solving a class of nonlinear operator equations in Banach spaces, Panam. Math. J. 4 (1994) 39–54.Google Scholar
  2. H. H. Bauschke, J. Y. Bello Cruz, T. T. A. Nghia, H. M. Phan, X. Wang: The rate of linear convergence of the Douglas–Rachford algorithm for subspaces is the cosine of the Friedrichs angle, J. Approx. Theory 185 (2014) 63–79.https://doi.org/10.1016/j.jat.2014.06.002Google Scholar
  3. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, Berlin (2011).https://doi.org/10.1007/978-1-4419-9467-7Google Scholar
  4. H. H. Bauschke, P. L. Combettes, D. R. Luke: Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization, J. Opt. Soc. Amer. 19 (2002) 1334–1345.https://doi.org/10.1364/JOSAA.19.001334Google Scholar
  5. 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 (2013) 475–501.https://doi.org/10.1007/s11228-013-0238-3Google Scholar
  6. H. H. Bauschke, D. Noll, H. M. Phan: Linear and strong convergence of algorithms involving averaged nonexpansive operators, J. Math. Anal. Appl. 421 (2015) 1–20.https://doi.org/10.1016/j.jmaa.2014.06.075Google Scholar
  7. J. M. Borwein, G. Li, L. Yao: Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets, SIAM J. Optim. 24 (2014) 498–527.https://doi.org/10.1137/130919052Google Scholar
  8. 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
  9. F. Deutsch, H. Hundal: Arbitrarily slow convergence sequences of linear operators: a survey, in: Fixed-Point Algorithms for Inverse Problems in Science and Engineering (Banff, 2009), H. H. Bauschke et al. (ed.), Springer Optimization and its Applications 49, Springer, New York (2011) 213–242.https://doi.org/10.1007/978-1-4419-9569-8_11Google Scholar
  10. O. Güler: On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optimization 29 (1991) 403–419.https://doi.org/10.1137/0329022Google Scholar
  11. P.-L. Lions, B. Mercier: Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16 (1979) 964–979.https://doi.org/10.1137/0716071Google Scholar
  12. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Franç. Inform. Rech. Opér. 4 (1970) 154–158.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  13. J.-J. Moreau: Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. Fr. 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  14. H. M. Phan: Linear convergence of the Douglas–Rachford method for two closed sets, Optimization 65 (2016) 369–385.https://doi.org/10.1080/02331934.2015.1051532Google Scholar
  15. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  16. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optimization 14 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar

Suggested citation

H. H. Bauschke, M. N. Dao, D. Noll, H. M. Phan. “Proximal Point Algorithm, Douglas-Rachford Algorithm and Alternating Projections: a Case Study.” Journal of Convex Analysis 23 (2016), No. 1, 237–261. https://doi.org/10.68381/jca23009

Download BibTeXPublished by Heldermann Verlag.

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