On the Metric Resolvent: Nonexpansiveness, Convergence Rates and Applications

doi:10.1007/s40305-023-00518-9

Abstract

Abstract: In this paper, we study the nonexpansive properties of metric resolvent and present the convergence analysis for the associated fixed-point iterations of both Banach-Picard and Krasnosel’ski$\breve{1}$–Mann types. A by-product of our expositions also extends the proximity operator and Moreau’s decomposition identity to arbitrary metric. It is further shown that many classes of the first-order operator splitting algorithms, including the alternating direction methods of multipliers, primal–dual hybrid gradient and Bregman iterations, can be expressed by the fixed-point iterations of a simple metric resolvent, and thus, the convergence can be easily obtained within this unified framework.

Key words: Metric resolvent, Nonexpansiveness, Convergence rates, Operator splitting algorithms

CLC Number:

Feng Xue. On the Metric Resolvent: Nonexpansiveness, Convergence Rates and Applications[J]. Journal of the Operations Research Society of China, 2025, 13(4): 966-988.

TrendMD

References

[1] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics, 2nd ed. Springer, New York (2017)
[2] Combettes, P., Wajs, V.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4(4), 1168–1200 (2005)
[3] Teboulle, M.: A simplified view of first order methods for optimization. Math. Program. Ser. B 170, 67–96 (2018)
[4] Lions, P., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1976)
[5] Glowinski, R., Marrocco, A.: Sur l’approximation par éléments finis d’ordure un et la résolution par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires. Revue Fr. Autom. Inf. Rech. Opér. Anal. Numér. 2, 41–76 (1975)
[6] Glowinski, R.: Numerical Methods for Nonlinear Variational Problems. Springer, New York (1984)
[7] Zhu, M., Chan, T.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration. CAM Report 08-34, UCLA (2008)
[8] Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imag. Vis. 40(1), 120–145 (2011)
[9] Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. Multiscale Model. Simul. 4(2), 460–489 (2005)
[10] Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for l₁-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1), 143–168 (2008)
[11] Goldstein, T., Osher, S.: The split Bregman method for l₁-regularized problems. SIAM J. Imaging Sci. 2(2), 323–343 (2009)
[12] Zhang, X., Burger, M., Osher, S.: A unified primal-dual algorithm framework based on Bregman iteration. J. Sci. Comput. 46(1), 20–46 (2011)
[13] Liang, J., Fadili, J., Peyré, G.: Convergence rates with inexact non-expansive operators. Math. Program. 159, 403–434 (2016)
[14] Combettes, P., Vu, B.: Variable metric quasi-Fejér monotonicity. Nonlinear Anal. Theory Methods Appl. 78, 17–31 (2016)
[15] Latafat, P., Patrinos, P.: Primal-Dual Proximal Algorithms for Structured Convex Optimization: A Unifying Framework, pp. 97–120. Springer, Cham (2018)
[16] Jakovetic, D.: A unification and generalization of exact distributed first-order methods. IEEE Trans. Signal Inf. Process. Over Netw. 5(1), 31–46 (2019)
[17] Beck, A., Teboulle, M.: Smoothing and first order methods: a unified framework. SIAM J. Optim. 22(2), 557–580 (2012)
[18] Giselsson, P., Boyd, S.: Linear convergence and metric selection for Douglas-Rachford splitting and ADMM. IEEE Trans. Autom. Control 62(2), 532–544 (2017)
[19] Giselsson, P., Boyd, S.: Diagonal scaling in Douglas–Rachford splitting and ADMM. In: 53rd IEEE Conference on Decision and Control, LA, California, USA, pp. 5033–5039 (2014)
[20] He, B., Yuan, X.: On the convergence rate of Douglas–Rachford operator splitting method. Math. Program. 153(2), 715–722 (2015)
[21] Raguet, H., Fadili, J., Peyré, G.: A generalized forward-backward splitting. SIAM J. Imaging Sci. 6(3), 1199–1226 (2013)
[22] Davis, D., Yin, W.: A three-operator splitting scheme and its optimization applications. Set-Valued Var. Anal. 25(4), 829–858 (2017)
[23] He, B., Yuan, X.: On the O(1/n) convergence rate of the Douglas–Rachford alternating direction method. SIAM J. Numer. Anal. 50(2), 700–709 (2012)
[24] He, B., Liu, H., Wang, Z., Yuan, X.: A strictly contractive Peaceman–Rachford splitting method for convex programming. SIAM J. Optim. 24(3), 1011–1040 (2014)
[25] He, B., Yuan, X.: Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective. SIAM J. Imaging Sci. 5(1), 119–149 (2012)
[26] He, B., Yuan, X.: On non-ergodic convergence rate of Douglas–Rachford alternating direction method of multipliers. Numer. Math. 130(3), 567–577 (2015)
[27] He, B., Ma, F., Yuan, X.: An algorithmic framework of generalized primal-dual hybrid gradient methods for saddle point problems. J. Math. Imaging Vis. 58(2), 279–293 (2017)
[28] Cai, J., Osher, S., Shen, Z.: Linearized Bregman iterations for compressed sensing. Math. Comput. 78, 1515–1536 (2009)
[29] Cai, J., Osher, S., Shen, Z.: Convergence of the linearized Bregman iteration for l₁-normminimization. Math. Comput. 78, 2127–2136 (2009)
[30] Esser, E., Zhang, X., Chan, T.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imag. Sci. 3(4), 1015–1046 (2010)
[31] Parente, L.A., Lotito, P.A., Solodov, M.V.:A class of inexact variablemetric proximal point algorithms. SIAM J. Optim. 19(1), 240–260 (2008)
[32] Burke, J.V., Qian, M.: A variable metric proximal point algorithm for monotone operators. SIAM J. Control. Optim. 37(2), 353–375 (1999)
[33] Bonnans, J., Gilbert, J., Lemaréchal, C., Sagastizabal, C.: A family of variable metric proximal methods. Math. Program. 68, 15–47 (1995)
[34] Martinet, B.: Régularisation d’inéquations variationnelles par approximations successives. Rev. Fr. Informatique et Recherche Opérationnelle 4, 154–158 (1970)
[35] Rochafellar, R.: Monotone operators and the proximal point algorithm. SIAM J. Control. Optim. 14(5), 877–898 (1976)
[36] Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, Princeton (1996)
[37] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis, vol. 317. Springer, Grundlehren der Mathematischen Wissenschaft (2004)
[38] Beck, A.: First-Order Methods in Optimization. SIAM-Society for Industrial and Applied Mathematics (2017)
[39] Xue, F.: On the nonexpansive operators based on arbitrary metric: a degenerate analysis. Results Math. https://doi.org/10.1007/s00025-022-01766-6 (2022)
[40] Chouzenoux, E., Pesquet, J., Repetti, A.: A block coordinate variable metric forward–backward algorithm. J. Global Optim. 66, 457–485 (2016)
[41] Bredies, K., Sun, H.: A proximal point analysis of the preconditioned alternating direction method of multipliers. J. Optim. Theory Appl. 173, 878–907 (2017)
[42] Passty, G.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. J. Math. Anal. Appl. 72, 383–390 (1979)
[43] Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1(3), 123–231 (2014)
[44] Bertsekas, D.P.: Convex Optimization Theory, 1st ed. Athena Scientific, Nashua (2009)
[45] Opial, Z.: Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Am. Math. Soc. 73, 591–597 (1967)
[46] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2011)
[47] Fang, E.X., He, B., Liu, H., Yuan, X.: Generalized alternating direction method of multipliers: new theoretical insights and applications. Math. Program. Comput. 7(2), 149–187 (2015)
[48] Li, X., Sun, D., Toh, K.C.: A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions. Math. Program. 155, 333–373 (2016)
[49] Sawatzky, A., Xu, Q., Schirra, C.O., Anastasio, M.A.: Proximal ADMM for multi-channel image reconstruction in spectral X-ray CT. IEEE Trans. Med. Imaging 33(8), 1657–1668 (2014)
[50] Bot, R., Csetnek, E., Heinrich, A., Hendrich, C.: On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems. Math. Program. Ser. A 150, 251–279 (2015)
[51] Ma, F., Ni, M.: A class of customized proximal point algorithms for linearly constrained convex optimization. Comput. Appl. Math. 37, 896–911 (2018)
[52] Tao, M., Yuan, X.: On the optimal linear convergence rate of a generalized proximal point algorithm. J. Sci. Comput. 74, 826–850 (2018)
[53] Yang, J., Yuan, X.: Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization. Math. Comput. 82(281), 301–329 (2013)
[54] Chen, C., He, B., Yuan, X.: The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program. Ser. A 155, 57–79 (2016)
[55] He, B., Yuan, X.: A class of ADMM-based algorithms for three-block separable convex programming. Comput. Optim. Appl. 70, 791–826 (2018)
[56] Deng, W., Lai, M., Peng, Z., Yin, W.: Parallel multi-block ADMM with O(1/k) convergence. J. Sci. Comput. 71(2), 712–736 (2017)