Abstract

We develop rapidly convergent forward-backward algorithms for computing zeroes of the sum of finitely many maximally monotone operators. A modification of the classical forward-backward method for two general operators is first considered, by incorporating an inertial term (close to the acceleration techniques introduced by Nesterov), a constant relaxation factor and a correction term. In a Hilbert space setting, we prove the weak convergence to equilibria of the iterates (xn)(x_n), with worst-case rates of o(n−1)o(n^{-1}) in terms of both the discrete velocity and the fixed point residual, instead of the classical rates of O(n−1/2){\cal O}(n^{-1/2}) established so far for related algorithms. Our procedure is then adapted to more general monotone inclusions and a fast primal-dual algorithm is proposed for solving convex-concave saddle point problems.

Author information

Contact details are reproduced from the original publication and may be historical.

Keywords

  • Nesterov-type algorithm
  • inertial-type algorithm
  • global rate of convergence
  • fast first-order method
  • relaxation factors
  • correction term
  • accelerated proximal algorithm
  • fixed point problem

Mathematics Subject Classification

90C25, 90C30, 90C60, 68Q25, 49M25

References

  1. H. Attouch, A. Cabot: Convergence of a relaxed inertial forward-backward algorithm for structured monotone inclusions, Appl. Math. Optim. 80 (2019) 547–598.https://doi.org/10.1007/s00245-019-09584-zGoogle Scholar
  2. H. Attouch, S. C. László: Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators, SIAM J. Optim. 30/4 (2020) 3252–3283.https://doi.org/10.1137/20M1333316Google Scholar
  3. H. Attouch, J. Peypouquet: The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than 1/k 2, SIAM J. Optimization 26/3 (2016) 1824–1834.https://doi.org/10.1137/15M1046095Google Scholar
  4. H. Attouch, J. Peypouquet: Convergence of inertial dynamics and proximal algorithms governed by maximal monotone operators, Math. Programming 174 (2019) 391–432.https://doi.org/10.1007/s10107-018-1252-xGoogle Scholar
  5. H. Attouch, M. Soueycatt: Augmented Lagrangian and proximal alternating direction methods of multipliers in Hilbert spaces. Applications to games, PDE’s and control, Pac. J. Optimization 5/1 (2009) 17–37.Google Scholar
  6. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, New York (2017).https://doi.org/10.1007/978-3-319-48311-5Google Scholar
  7. A. Beck, M. Teboulle: A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2/1 (2009) 183-202.https://doi.org/10.1137/080716542Google Scholar
  8. R. I. Boţ, M. Sedlmayer, P. T. Vuong: A relaxed inertial forward-backward-forward algorithm for solving monotone inclusions with application to GANs, arXiv: 2003. 07886 (2020).Google Scholar
  9. H. Brezis: Opérateurs Maximaux Monotones, North Holland Mathematics Studies 5, North-Holland, Amsterdam (1973).Google Scholar
  10. H. Brezis, P. L. Lions: Produits infinis de résolvantes, Israel J. Math. 29 (1978) 329–345.https://doi.org/10.1007/BF02761171Google Scholar
  11. V. Cevher, B. C. Vu: A reflected forward-backward splitting method for monotone inclusions involving Lipschitzian operators, Set-Valued Var. Anal. 29 (2021) 163–174.https://doi.org/10.1007/s11228-020-00542-4Google Scholar
  12. A. Chambolle, C. Dossal: On the convergence of the iterates of Fista, J. Optimization Theory Appl. 166/3 (2015) 968–982.https://doi.org/10.1007/s10957-015-0746-4Google Scholar
  13. P. L. Combettes: Monotone operator theory in convex optimization, Math. Programming B 170/1 (2018) 177–206.https://doi.org/10.1007/s10107-018-1303-3Google Scholar
  14. P. L. Combettes, J.-C. Pesquet: Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators, Set-Valued Var. Analysis 20/2 (2012) 307–330.https://doi.org/10.1007/s11228-011-0191-yGoogle Scholar
  15. P. L. Combettes, B. C. Vu: Variable metric forward-backward splitting with applications to monotone inclusions in duality, Optimization 63/9 (2014) 1289–1318.https://doi.org/10.1080/02331934.2012.733883Google Scholar
  16. P. L. Combettes, V. Wajs: Signal recovery by proximal forwardbackward splitting, SIAM Multiscale Modelling and Simulation 4/4 (2005) 1168–1200.https://doi.org/10.1137/050626090Google Scholar
  17. L. Condat: A primal-dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms, J. Optimization Theory Appl. 158/2 (2013) 460–479.https://doi.org/10.1007/s10957-012-0245-9Google Scholar
  18. E. Corman, X. Yuan: A generalized proximal point algorithm and its convergence rate, SIAM J. Optimization 24/4 (2014) 1614–1638.https://doi.org/10.1137/130940402Google Scholar
  19. I. Daubechies, M. Defrise, C. De Mol: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math. 57 (2004) 1413–1457.https://doi.org/10.1002/cpa.20042Google Scholar
  20. J. Douglas, H. H. Rachford: On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Society 82 (1956) 421–439.https://doi.org/10.1090/S0002-9947-1956-0084194-4Google Scholar
  21. Y. Drori, M. Teboulle: Performance of first-order methods for smooth convex minimization: A novel approach, Math. Programming 145/1-2 (2014) 451–482.https://doi.org/10.1007/s10107-013-0653-0Google Scholar
  22. J. Duchi, Y. Singer: Efficient online and batch learning using forward backward splitting, J. Machine Learning Res. 10 (2009) 2899–2934.Google Scholar
  23. J. Eckstein, D. P. Bertsekas: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Programming 55/1-3 (1992) 293–318.https://doi.org/10.1007/BF01581204Google Scholar
  24. O. Güler: On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optimization 29 (1991) 403–419.https://doi.org/10.1137/0329022Google Scholar
  25. O. Güler: New proximal point algorithms for convex minimization, SIAM J. Optimization 2/4 (1992) 649–664.https://doi.org/10.1137/0802032Google Scholar
  26. D. Kim: Accelerated proximal point method for maximally monotone operators, Math. Programming 190/1-2 (A) (2021) 57–87.https://doi.org/10.1007/s10107-021-01643-0Google Scholar
  27. B. Lemaire: The proximal algorithm, in: New Methods in Optimization and their Industrial Uses, J. P. Penot (ed.), International Series in Numerical Mathematics 87, Birkhäuser, Basel (1989) 73–87.Google Scholar
  28. H. Lin, J. Mairal, Z. Harchaoui: Catalyst acceleration for first-order convex optimization: from theory to practice, J. Machine Learning Res. 18/212 (2018) 1–54.Google Scholar
  29. P. L. Lions, B. Mercier: Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Analysis 16/6 (1979) 964–979.https://doi.org/10.1137/0716071Google Scholar
  30. D. A. Lorenz, T. Pock: An inertial forward-backward algorithm for monotone inclusions, J. Math. Imaging Vision 51 (2015) 311–325.https://doi.org/10.1007/s10851-014-0523-2Google Scholar
  31. P. E. Maingé: Accelerated proximal algorithms with a correction term for monotone inclusions, Appl. Math. Optimization 84/2 (2021) 2027–2061.https://doi.org/10.1007/s00245-021-09819-yGoogle Scholar
  32. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Fr. Auto. Infor. Rech. Oper. 4 (1970) 154–158.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  33. A. Moudafi, M. Oliny: Convergence of a splitting inertial proximal method for monotone operators, J. Comput. Appl. Math. 155/2 (2003) 447–454.https://doi.org/10.1016/S0377-0427(02)00906-8Google Scholar
  34. Y. Nesterov: A method of solving a convex programming problem with convergence rate O(1/k2), Soviet Math. Doklady 27 (1983) 372–376.Google Scholar
  35. Y. Nesterov: A method for unconstrained convex minimization problem with the rate of convergence O(1/k2), Dokl. Akad. Nauk. USSR 269/3 (1983) 543–547.Google Scholar
  36. Y. Nesterov: Gradient methods for minimizing composite objective function, Math. Programming B 140 (2013) 125–161.https://doi.org/10.1007/s10107-012-0629-5Google Scholar
  37. G. B. Passty: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Analysis Appl. 72 (1979) 383–390.https://doi.org/10.1016/0022-247X(79)90234-8Google Scholar
  38. D. W. Peaceman, H. H. Rachford: The numerical solution of parabolic and elliptic differential equations, J. Soc. Indust. Appl. Math. 3/1 (1955) 28–41.https://doi.org/10.1137/0103003Google Scholar
  39. M. J. D. Powell: A method for nonlinear constraints in minimization problems, in: Optimization, R. Fletcher (ed.), Academic Press, New York (1969) 283–298.Google Scholar
  40. H. Raguet, J. Fadili, G. Peyré: A generalized forward–backward splitting, SIAM J. Imaging Sci. 6 (2013) 1199–1226.https://doi.org/10.1137/120872802Google Scholar
  41. R. T. Rockafellar: Monotone operators associated with saddle functions and minimax problems, in: Nonlinear Functional Analysis, Part 1, F. E. Browder (ed.), Symposia in Pure Math. 18, American Mathematical Society, Providence (1970) 397–407.https://doi.org/10.1090/pspum/018.1/0285942Google Scholar
  42. R. T. Rockafellar: Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1/2 (1976) 97–116.https://doi.org/10.1287/moor.1.2.97Google Scholar
  43. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control. Optimization 14/5 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  44. R. T. Rockafellar, J. B. Wets: Variational Analysis, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  45. Z. Sebestyen, Z. Tarcsay: On the square root of a positive selfadjoint operator, Periodica Math. Hung. 75 (2017) 268–272.https://doi.org/10.1007/s10998-017-0192-1Google Scholar
  46. W. Takahashi: Nonlinear Functional Analysis, Yokohama Publ., Yokohama (2000).Google Scholar
  47. P. Tseng: A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optimization 38/2 (2000) 431–446.https://doi.org/10.1137/S0363012998338806Google Scholar
  48. S. Villa, S. Salzo, L. Baldassarre, A. Verri: Accelerated and inexact forward-backward algorithms, SIAM J. Optimization 23/3 (2013) 1607–1633.https://doi.org/10.1137/110844805Google Scholar
  49. B. Vu: A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comput. Math. 38/3 (2013) 667–681.https://doi.org/10.1007/s10444-011-9254-8Google Scholar
  50. X. Q. Zhang, M. Burger, X. Bresson, S. Osher: Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM J. Imag. Sci. 3/3 (2010) 253–276.https://doi.org/10.1137/090746379Google Scholar

Suggested citation

P.-E. Maingé. “Fast Convergence of Generalized Forward-Backward Algorithms for Structured Monotone Inclusions.” Journal of Convex Analysis 29 (2022), No. 3, 893–920. https://doi.org/10.68381/jca29051

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2022. Rights now held by Banach Press LLC.