doi: 10.3934/jimo.2022107
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Department of Mathematics, Nanjing University, China

Received  January 2022 Revised  March 2022 Early access June 2022

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

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: Guoyong Gu, Junfeng Yang. A unified and tight linear convergence analysis of the relaxed proximal point algorithm. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2022107
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. DouglasJr .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. FangB. HeH. 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.

show all references

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. DouglasJr .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. FangB. HeH. 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.

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

Ram U. Verma. On the generalized proximal point algorithm with applications to inclusion problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 381-390. doi: 10.3934/jimo.2009.5.381

[2]

Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic and Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1

[3]

Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure and Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791

[4]

Yan Tang. Convergence analysis of a new iterative algorithm for solving split variational inclusion problems. Journal of Industrial and Management Optimization, 2020, 16 (2) : 945-964. doi: 10.3934/jimo.2018187

[5]

Mohammad Eslamian, Ahmad Kamandi. A novel algorithm for approximating common solution of a system of monotone inclusion problems and common fixed point problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021210

[6]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053

[7]

Fabio Camilli, Claudio Marchi. On the convergence rate in multiscale homogenization of fully nonlinear elliptic problems. Networks and Heterogeneous Media, 2011, 6 (1) : 61-75. doi: 10.3934/nhm.2011.6.61

[8]

Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial and Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199

[9]

Shahad Al-azzawi, Jicheng Liu, Xianming Liu. Convergence rate of synchronization of systems with additive noise. Discrete and Continuous Dynamical Systems - B, 2017, 22 (2) : 227-245. doi: 10.3934/dcdsb.2017012

[10]

Armand Bernou. A semigroup approach to the convergence rate of a collisionless gas. Kinetic and Related Models, 2020, 13 (6) : 1071-1106. doi: 10.3934/krm.2020038

[11]

Andriy Bondarenko, Guy Bouchitté, Luísa Mascarenhas, Rajesh Mahadevan. Rate of convergence for correctors in almost periodic homogenization. Discrete and Continuous Dynamical Systems, 2005, 13 (2) : 503-514. doi: 10.3934/dcds.2005.13.503

[12]

Feng-Yu Wang. Exponential convergence of non-linear monotone SPDEs. Discrete and Continuous Dynamical Systems, 2015, 35 (11) : 5239-5253. doi: 10.3934/dcds.2015.35.5239

[13]

Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013

[14]

Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027

[15]

Oleg Makarenkov, Paolo Nistri. On the rate of convergence of periodic solutions in perturbed autonomous systems as the perturbation vanishes. Communications on Pure and Applied Analysis, 2008, 7 (1) : 49-61. doi: 10.3934/cpaa.2008.7.49

[16]

Marek Fila, Michael Winkler. Sharp rate of convergence to Barenblatt profiles for a critical fast diffusion equation. Communications on Pure and Applied Analysis, 2015, 14 (1) : 107-119. doi: 10.3934/cpaa.2015.14.107

[17]

Zigen Ouyang, Chunhua Ou. Global stability and convergence rate of traveling waves for a nonlocal model in periodic media. Discrete and Continuous Dynamical Systems - B, 2012, 17 (3) : 993-1007. doi: 10.3934/dcdsb.2012.17.993

[18]

Xinfu Chen, Bei Hu, Jin Liang, Yajing Zhang. Convergence rate of free boundary of numerical scheme for American option. Discrete and Continuous Dynamical Systems - B, 2016, 21 (5) : 1435-1444. doi: 10.3934/dcdsb.2016004

[19]

Zhilei Liang. Convergence rate of solutions to the contact discontinuity for the compressible Navier-Stokes equations. Communications on Pure and Applied Analysis, 2013, 12 (5) : 1907-1926. doi: 10.3934/cpaa.2013.12.1907

[20]

Emmanuel Gobet, Mohamed Mrad. Convergence rate of strong approximations of compound random maps, application to SPDEs. Discrete and Continuous Dynamical Systems - B, 2018, 23 (10) : 4455-4476. doi: 10.3934/dcdsb.2018171

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (107)
  • HTML views (49)
  • Cited by (0)

Other articles
by authors

[Back to Top]