A unified and tight linear convergence analysis of the relaxed proximal point algorithm

Guoyong Gu; Junfeng Yang

doi:10.3934/jimo.2022107

Article Contents

2023, Volume 19, Issue 5: 3742-3749. Doi: 10.3934/jimo.2022107

This issue Previous Article Generalized minimal Gershgorin set for tensors Next Article Control parameterization approach to time-delay optimal control problems: A survey

A unified and tight linear convergence analysis of the relaxed proximal point algorithm

Guoyong Gu and
Junfeng Yang

Department of Mathematics, Nanjing University, China

Received: January 2022

Revised: March 2022

Early access: June 2022

Published: May 2023

The first author was supported by NSFC grant 11671195. The second author was supported by NSFC grants 11922111 and 12126337

Abstract / Introduction Full Text(HTML) Figure(1) Related Papers Cited by

Abstract

Finding a zero of a maximal monotone operator is fundamental in convex optimization and monotone operator theory, and proximal point algorithm (PPA) is a primary method for solving this problem. PPA converges not only globally under fairly mild conditions but also asymptotically at a fast linear rate provided that the underlying inverse operator is Lipschitz continuous at the origin. These nice convergence properties are preserved by a relaxed variant of PPA. Recently, a linear convergence bound was established in [M. Tao, and X. M. Yuan, J. Sci. Comput., 74 (2018), pp. 826-850] for the relaxed PPA, and it was shown that the bound is tight when the relaxation factor $ \gamma $ lies in $ [1,2) $. However, for other choices of $ \gamma $, the bound obtained by Tao and Yuan is suboptimal. In this paper, we establish tight linear convergence bounds for any choice of $ \gamma\in(0,2) $ using a unified and much simplified analysis. These results sharpen our understandings to the asymptotic behavior of the relaxed PPA and make the whole picture for $ \gamma\in(0,2) $ clear.

Keywords:

Proximal point algorithm,
maximal monotone operator inclusion problems,
linear convergence rate,
tight convergence rate.

Mathematics Subject Classification: Primary: 65K10, 9C025.

Citation:

Full Text(HTML)

Figure 1. Illustration of the bounds. Left: results in [27]. Right: results of this work

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202. doi: 10.1137/080716542.
[2]	D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Computer Science and Applied Mathematics. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982.
[3]	E. Corman and X. Yuan, A generalized proximal point algorithm and its convergence rate, SIAM J. Optim., 24 (2014), 1614-1638. doi: 10.1137/130940402.
[4]	D. Davis and W. Yin, Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions, Math. Oper. Res., 42 (2017), 783-805. doi: 10.1287/moor.2016.0827.
[5]	J. Douglas, Jr ., H. H. Rachford and Jr ., On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., 82 (1956), 421-439. doi: 10.1090/S0002-9947-1956-0084194-4.
[6]	J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Programming, 55 (1992), 293-318. doi: 10.1007/BF01581204.
[7]	E. X. Fang, B. He, H. Liu and X. Yuan, Generalized alternating direction method of multipliers: New theoretical insights and applications, Math. Program. Comput., 7 (2015), 149-187. doi: 10.1007/s12532-015-0078-2.
[8]	D. Gabay, Applications of the method of multipliers to variational inequalities, in Fortin, M., Glowinski, R. (eds. ) Augmented Lagrange Methods: Applications to the Solution of Boundary-valued Problems, North Holland, Amsterdam, 1983, 299–331.
[9]	D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers and Mathematics with Applications, 2 (1976), 17-40. doi: 10.1016/0898-1221(76)90003-1.
[10]	R. Glowinski and A. Marrocco, Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité, d'une classe de problèmes de Dirichlet non linéaires, R.A.I.R.O., R2, 9 (1975), 41-76. doi: 10.1051/m2an/197509R200411.
[11]	G. Gu and J. Yang, Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems, SIAM J. Optim., 30 (2020), 1905-1921. doi: 10.1137/19M1299049.
[12]	O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim., 29 (1991), 403-419. doi: 10.1137/0329022.
[13]	O. Güler, New proximal point algorithms for convex minimization, SIAM J. Optim., 2 (1992), 649-664. doi: 10.1137/0802032.
[14]	B. He and X. Yuan, On the convergence rate of Douglas-Rachford operator splitting method, Math. Program., 153 (2015), 715-722. doi: 10.1007/s10107-014-0805-x.
[15]	M. R. Hestenes, Multiplier and gradient methods, J. Optimization Theory Appl., 4 (1969), 303-320. doi: 10.1007/BF00927673.
[16]	D. Leventhal, Metric subregularity and the proximal point method, J. Math. Anal. Appl., 360 (2009), 681-688. doi: 10.1016/j.jmaa.2009.07.012.
[17]	P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), 964-979. doi: 10.1137/0716071.
[18]	B. Martinet, Régularisation d'inéquations variationnelles par approximations successives, Rev. Française Informat. Recherche Opérationnelle, 4 (1970), 154-158.
[19]	B. Martinet, Détermination approchée d'un point fixe d'une application pseudo-contractante. Cas de l'application prox, C. R. Acad. Sci. Paris Sér. A-B, 274 (1972), A163–A165.
[20]	G. J. Minty, Monotone (nonlinear) operators in Hilbert space, Duke Mathematical Journal, 29 (1962), 341-346.
[21]	J.-J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, C. R. Acad. Sci. Paris, 255 (1962), 2897-2899.
[22]	J.-J. Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93 (1965), 273-299.
[23]	Y. E. Nesterov, A method for solving the convex programming problem with convergence rate $O(1/k^{2})$, Dokl. Akad. Nauk SSSR, 269 (1983), 543-547.
[24]	M. J. D. Powell, A method for nonlinear constraints in minimization problems, in Optimization (Sympos., Univ. Keele, Keele, 1968), Academic Press, London, 1969.
[25]	R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1 (1976), 97-116. doi: 10.1287/moor.1.2.97.
[26]	R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optimization, 14 (1976), 877-898. doi: 10.1137/0314056.
[27]	M. Tao and X. Yuan, On the optimal linear convergence rate of a generalized proximal point algorithm, J. Sci. Comput., 74 (2018), 826-850. doi: 10.1007/s10915-017-0477-9.