Skip to main content
SpringerLink
Log in

Sharp convergence rates for averaged nonexpansive maps

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

Abstract

We establish sharp estimates for the convergence rate of the Kranosel’skiĭ–Mann fixed point iteration in general normed spaces, and we use them to show that the optimal constant of asymptotic regularity is exactly \(1/\sqrt \pi \). To this end we consider a nested family of optimal transport problems that provide a recursive bound for the distance between the iterates. We show that these bounds are tight by building a nonexpansive map T: [0, 1]N → [0, 1]N that attains them with equality, settling a conjecture by Baillon and Bruck. The recursive bounds are in turn reinterpreted as absorption probabilities for an underlying Markov chain which is used to establish the tightness of the constant \(1/\sqrt \pi \).

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.

Similar content being viewed by others

References

  1. N. Aronszajn and P. Panitchpakdi, Extension of uniformly continuous transformations and hyperconvex metric spaces, Pacific Journal of Mathematics 6 (1956), 405–439.

    Article  MathSciNet  MATH  Google Scholar 

  2. Y. Aygen-Satik, Optimal Bounds of Asymptotic Regularity, Ph.D. Thesis, University of Southern California, 1994.

    Google Scholar 

  3. J. B. Baillon and R. E. Bruck, Optimal rates of asymptotic regularity for averaged nonexpansive mappings, In Fixed Point Theory and Applications (Halifax, NS, 1991), World Scientific, River Edge, NJ, 1992, pp. 27–66.

    Google Scholar 

  4. J. B. Baillon and R. E. Bruck, The rate of asymptotic regularity is O(1/ √ n), in Theory and Applications of Nonlinear Operators of Accretive and Monotone Type, Lecture Notes in Pure and Applied Mathematics, Vol. 178, Dekker, New York, 1996, pp. 51–81.

    MathSciNet  MATH  Google Scholar 

  5. J.-B. Baillon, R. Cominetti and J. Vaisman, A sharp uniform bound for the distribution of sums of Bernoulli trials, Combinatorics, Probability and Computing 25 (2016), 352–361.

    Article  MathSciNet  MATH  Google Scholar 

  6. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics, Springer, New York, 2011.

    Book  MATH  Google Scholar 

  7. J. Borwein, S. Reich and I. Shafrir, Krasnosel’skiĭ-Mann iterations in normed spaces, Canadian Mathematical Bulletin 35 (1992), 21–28.

    Article  MathSciNet  MATH  Google Scholar 

  8. F. E. Browder and W. V. Petryshyn, The solution by iteration of nonlinear functional equations in Banach spaces, Bulletin of the American Mathematical Society 72 (1966), 571–575.

    Article  MathSciNet  MATH  Google Scholar 

  9. F. E. Browder and W. V. Petryshyn, Construction of fixed points of nonlinear mappings in Hilbert space, Journal of Mathematical Analysis and Applications 20 (1967), 197–228.

    Article  MathSciNet  MATH  Google Scholar 

  10. R. E. Bruck, Asymptotic behavior of nonexpansive mappings, in Fixed Points and Nonexpansive Mappings (Cincinnati, Ohio, 1982), Contemporary Mathematics, Vol. 18, American Mathematical Society, Providence, RI, 1983, pp. 1–47.

    MATH  Google Scholar 

  11. R. Cominetti, J. Soto and J. Vaisman, On the rate of convergence of Krasnosel’skiĭ–Mann iterations and their connection with sums of Bernoullis, Israel Journal of Mathematics 199 (2014), 757–772.

    Article  MathSciNet  MATH  Google Scholar 

  12. M. Edelstein, A remark on a theorem of M. A. Krasnosel’skiĭ, American Mathematical Monthly 73 (1966), 509–510.

    Article  MathSciNet  MATH  Google Scholar 

  13. M. Edelstein and R. C. O’Brien, Nonexpansive mappings, asymptotic regularity and successive approximations, Journal of the London Mathematical Society 17 (1978), 547–554.

    Article  MathSciNet  MATH  Google Scholar 

  14. K. Goebel and W. A. Kirk, Iteration processes for nonexpansive mappings, in Topological Methods in Nonlinear Functional Analysis (Toronto, ON, 1982), Contemporary Mathematics, Vol. 21, American Mathematical Society, Providence, RI, 1983, pp. 115–123.

    MATH  Google Scholar 

  15. C. W. Groetsch, A note on segmenting Mann iterates, Journal of Mathematical Analysis and Applications 40 (1972), 369–372.

    Article  MathSciNet  MATH  Google Scholar 

  16. S. Ishikawa, Fixed points and iterations of a nonexpansive mapping in a Banach space, Proceedings of the American Mathematical Society 59 (1976), 65–71.

    Article  MathSciNet  MATH  Google Scholar 

  17. U. Kohlenbach, Uniform asymptotic regularity for Mann iterates, Journal of Mathematical Analysis and Applications 279 (2003), 531–544.

    Article  MathSciNet  MATH  Google Scholar 

  18. M. A. Krasnosel’skiĭ, Two remarks on the method of successive approximations, Uspekhi Matematicheskikh Nauk 10 (1955), 123–127.

    MathSciNet  Google Scholar 

  19. W. R. Mann, Mean value methods in iteration, Proceedings of the American Mathematical Society 4 (1953), 506–510.

    Article  MathSciNet  MATH  Google Scholar 

  20. S. Reich, Weak convergence theorems for nonexpansive mappings in Banach spaces, Journal of Mathematical Analysis and Applications 67 (1979), 274–276.

    Article  MathSciNet  MATH  Google Scholar 

  21. S. Reich and I. Shafrir, Nonexpansive iterations in hyperbolic spaces, Nonlinear Analysis 15 (1990), 537–558.

    Article  MathSciNet  MATH  Google Scholar 

  22. H. Schaefer, Über die Methode sukzessiver Approximationen, Jahresbericht der Deutschen Mathematiker-Vereinigung 59 (1957), 131–140.

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Matemática y Ciencia de la Computación, Universidad de Santiago de Chile, Alameda Libertador Bernardo O’higgins 3363, Santiago, Chile

    Mario Bravo

  2. Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Diagonal Las Torres 2640, Santiago, Chile

    Roberto Cominetti

Authors
  1. Mario Bravo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roberto Cominetti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Roberto Cominetti.

Additional information

The work of Mario Bravo was partially funded by FONDECYT Grant 11151003 and the Núcleo Milenio Información y Coordinación en Redes ICM/FIC RC130003.

Roberto Cominetti gratefully acknowledges the support provided by FONDECYT 1130564 and FONDECYT 1171501.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bravo, M., Cominetti, R. Sharp convergence rates for averaged nonexpansive maps. Isr. J. Math. 227, 163–188 (2018). https://doi.org/10.1007/s11856-018-1723-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11856-018-1723-z

Search

Navigation