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 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:

FullText(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.