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.
Citation: |
Figure 1. Illustration of the bounds. Left: results in [27]. Right: results of this work
[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.![]() ![]() ![]() |
Illustration of the bounds. Left: results in [27]. Right: results of this work