Advanced Search
Article Contents
Article Contents

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

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
  • 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.

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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. BertsekasConstrained 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. PowellA 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.
  • 加载中



Article Metrics

HTML views(1412) PDF downloads(292) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint