Abstract

We give a quantitative analysis of a theorem due to Fenghui Wang and Huanhuan Cui concerning the convergence of a multi-parametric version of the proximal point algorithm. Wang and Cui's result ensures the convergence of the algorithm to a zero of the operator. Our quantitative analysis provides explicit bounds on the metastability (in the sense of Terence Tao) for the convergence and the asymptotic regularity of the iteration. Moreover, our analysis bypasses the need of sequential weak compactness and only requires a weak form of the metric projection argument.

Author information

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

Bruno Dinis

Departamento de Matemática, Faculdade de Ciências, Universidade de Lisboa, Portugal

bmdinis@fc.ul.pt

Keywords

  • Maximal monotone operator
  • proximal point algorithm
  • metastability
  • asymptotic regularity
  • proof mining

Mathematics Subject Classification

47H09, 47N10, 03F10, 46S30

References

  1. K. Aoyama, M. Toyoda: Approximation of zeros of accretive operators in a Banach space, Israel J. Math. 220(2) (2017) 803–816.https://doi.org/10.1007/s11856-017-1511-1Google Scholar
  2. H. Bauschke, P. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., CMS Books in Mathematics, Springer, Cham (2017).https://doi.org/10.1007/978-3-319-48311-5Google Scholar
  3. M. Bezem: Strongly majorizable functionals of finite type: A model for barrecursion containing discontinuous functionals, J. Symb. Logic 50(3) (1985) 652–660.https://doi.org/10.2307/2274319Google Scholar
  4. O. Boikanyo, G. Moroşanu: Four parameter proximal point algorithms, Nonlinear Anal. Theory, Meth. Appl. 74(2) (1974) 544–555.https://doi.org/10.1016/j.na.2010.09.008Google Scholar
  5. O. Boikanyo, G. Moroşanu: Inexact Halpern-type proximal point algorithm, J. Global Optimization 51(1) (2011) 11–26.https://doi.org/10.1007/s10898-010-9616-7Google Scholar
  6. F. Browder: Nonexpansive nonlinear operators in a Banach space, Proc. Nat. Acad. Sci. U.S.A. 54 (1965) 1041–1044.https://doi.org/10.1073/pnas.54.4.1041Google Scholar
  7. B. Dinis, P. Pinto: Metastability of the proximal point algorithm with multi-parameters, Port. Math. 17/3-4 (2020) 345–381.https://doi.org/10.4171/pm/2054Google Scholar
  8. F. Ferreira: Injecting uniformities into Peano arithmetic, Ann. Pure Appl. Logic 157/2-3 (2009) 122–129.https://doi.org/10.1016/j.apal.2008.09.004Google Scholar
  9. F. Ferreira, L. Leuştean, P. Pinto: On the removal of weak compactness arguments in proof mining, Advances in Mathematics 354 (2019) 106728.https://doi.org/10.1016/j.aim.2019.106728Google Scholar
  10. F. Ferreira, P. Oliva: Bounded functional interpretation, Ann. Pure Appl. Logic 135/1-3 (2005) 73–112.https://doi.org/10.1016/j.apal.2004.11.001Google Scholar
  11. O. Güler: On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optimization 29(2) (1991) 403–419.https://doi.org/10.1137/0329022Google Scholar
  12. B. Halpern: Fixed points of nonexpanding maps, Bull. Amer. Math. Soc. 73/6 (1967) 957–961.https://doi.org/10.1090/S0002-9904-1967-11864-0Google Scholar
  13. S. Kamimura, W. Takahashi: Approximating solutions of maximal monotone operators in Hilbert spaces, J. Approximation Theory 106/2 (2000) 226–240.https://doi.org/10.1006/jath.2000.3493Google Scholar
  14. D. Koernlein: Quantitative results for Halpern iterations of nonexpansive mappings, J. Math. Anal. Appl. 428/2 (2015) 1161–1172.https://doi.org/10.1016/j.jmaa.2015.03.020Google Scholar
  15. U. Kohlenbach: Applied Proof Theory: Proof Interpretations and their Use in Mathematics, Springer Monographs in Mathematics, Springer, Berlin (2008).Google Scholar
  16. U. Kohlenbach: On quantitative versions of theorems due to F. E. Browder and R. Wittmann, Advances in Mathematics 226/3 (2011) 2764–2795.https://doi.org/10.1016/j.aim.2010.10.002Google Scholar
  17. U. Kohlenbach: Recent progress in proof mining in nonlinear analysis, IFCoLog J. Logics Appl. 10 (2017) 3357–3406.Google Scholar
  18. U. Kohlenbach: Proof-theoretic methods in nonlinear analysis, in: Proceedings of the ICM2018, Vol. 2, B. Sirakov, P. Ney de Souza and M. Viana (eds.), World Scientific, Singapore (2019) 61–82.https://doi.org/10.1142/9789813272880_0045Google Scholar
  19. U. Kohlenbach: Quantitative analysis of a Halpern-type proximal point algorithm for accretive operators in Banach spaces, J. Nonlinear Convex Analysis 21 (2020) 2125–2138.Google Scholar
  20. L. Leuştean, P. Pinto: Quantitative results on a Halpern-type proximal point algorithm, Comp. Optimization Appl. 79/1 (2021) 101–125.https://doi.org/10.1007/s10589-021-00263-wGoogle Scholar
  21. P.-E. Maingé: Strong convergence of projected subgradient methods for nonsmooth and nonstrictly convex minimization, Set-Valued Analysis 16/7-8 (2008) 899–912.https://doi.org/10.1007/s11228-008-0102-zGoogle Scholar
  22. G. Marino, H.-K. Xu: Convergence of generalized proximal point algorithms, Commun. Pure Appl. Anal. 3/4 (2004) 791–808.https://doi.org/10.3934/cpaa.2004.3.791Google Scholar
  23. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Franç. Inform. Rech. Opér., Sér. R-3, 4 (1970) 154–158.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  24. P. Pinto: A rate of metastability for the Halpern type proximal point algorithm, Numer. Funct. Analysis Optimization 42/3 (2021).https://doi.org/10.1080/01630563.2021.1876726Google Scholar
  25. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optimization 14/5 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  26. T. Tao: Norm convergence of multiple ergodic averages for commuting transformations, Ergodic Theory Dyn. Systems 28/2 (2008) 657–688.https://doi.org/10.1017/S0143385708000011Google Scholar
  27. T. Tao: Structure and randomness. Pages from year one of a mathematical blog, American Mathematical Society, Providence (2008).Google Scholar
  28. F. Wang, H. Cui: On the contraction-proximal point algorithms with multi-parameters, J. Global Optimization 54/3 (2012) 485–491.https://doi.org/10.1007/s10898-011-9772-4Google Scholar
  29. H.-K. Xu: Iterative algorithms for nonlinear operators, J. London Math. Soc., Second Series, 66(1) (2002) 240–256.https://doi.org/10.1112/S0024610702003332Google Scholar
  30. Y. Yonghong, M. A. Noor: On convergence criteria of generalized proximal point algorithms, J. Comput. Appl. Math. 217/1 (2008) 46–55.https://doi.org/10.1016/j.cam.2007.06.013Google Scholar

Suggested citation

B. Dinis, P. Pinto. “Quantitative Results on the Multi-Parameters Proximal Point Algorithm.” Journal of Convex Analysis 28 (2021), No. 3, 729–750. https://doi.org/10.68381/jca28041

Download BibTeXPublished by Heldermann Verlag.

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