Abstract

Operator splitting methods have been recently concerned with inclusions problems based on composite operators made of the sum of two monotone operators, one of them associated with a linear transformation. We analyze here a general and new splitting method which indeed splits both operator proximal steps, and avoiding costly numerical algebra on the linear operator. The family of algorithms induced by our generalized setting includes known methods like Chambolle-Pock primal-dual algorithm and Shefi-Teboulle Proximal Alternate Direction Method of Multipliers. The study of the ergodic and non ergodic convergence rates show similar rates with the classical Douglas-Rachford splitting scheme. We end with an application to a multi-block convex optimization model which leads to a generalized Separable Augmented Lagrangian Algorithm.

Author information

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

Ernesto Oré-Albornoz

IMCA, Universidad Nacional de Ingeniería, Lima, Peru
and: LIMOS, Université Clermont Auvergne, Clermont-Ferrand, France

Philippe Mahey

LIMOS, Université Clermont Auvergne, Clermont-Ferrand, France

mahey@isima.fr

Eladio Ocaña-Anaya

IMCA, Universidad Nacional de Ingeniería, Lima, Peru

Keywords

  • Splitting methods
  • monotone inclusions
  • convergence analysis

Mathematics Subject Classification

90C25, 90C30, 65K13

References

  1. M. A. Alghamdi, A. Alotaibi, P. L. Combettes, N. Shahzad: A primal-dual method of partial inverses for composite inclusions, Optimization Letters 8 (2014) 2271–2284.https://doi.org/10.1007/s11590-014-0734-xGoogle Scholar
  2. H. Attouch, M. Soueycatt: Augmented Lagrangian and proximal alternating direction method of multipliers in Hilbert spaces. Applications to games, PDE’s and control, Pacific J. Optimization 5 (2008) 17–37.Google Scholar
  3. A. Beck, M. Teboulle: A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009) 183–202.https://doi.org/10.1137/080716542Google Scholar
  4. S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein: Distributed optimization and statistical learning with the alternating direction method of multipliers, Foundations and Trends in Machine Learning 3 (2011) 1–122.https://doi.org/10.1561/2200000016Google Scholar
  5. L. M. Briceno-Arias, P. L. Combettes: A monotone + skew splitting model for composite monotone inclusions in duality, SIAM J. Optimization 21 (2011) 1230–1250.https://doi.org/10.1137/10081602XGoogle Scholar
  6. A. Chambolle, T. Pock: A first-order primal-dual algorithm for convex programs with applications to imaging, J. Math. Imaging Vision 40 (2011) 1–26.https://doi.org/10.1007/s10851-010-0251-1Google Scholar
  7. L. Condat: A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optimization Theory Appl. 158 (2013) 460–479.https://doi.org/10.1007/s10957-012-0245-9Google Scholar
  8. D. Davis: Convergence rate analysis of forward-Douglas-Rachford splitting scheme, arXiv:1410.2654 (2014).https://doi.org/10.1137/140992291Google Scholar
  9. D. Davis, W. Yin: Convergence rate analysis of several splitting schemes, in: Splitting Methods in Communication, Imaging, Science and Engineering, R. Glowinski, S. J. Osher and W. Yin (eds.), Springer, Cham (2016) 115–163.https://doi.org/10.1007/978-3-319-41589-5_4Google Scholar
  10. J. P. Dussault, O. M. Gueye, P. Mahey: Separable augmented Lagrangian algorithm with multidimensional scaling for monotropic programming, J. Optimization Theory Appl. 127 (2005) 329–345.https://doi.org/10.1007/s10957-005-6547-4Google Scholar
  11. J. Eckstein, D. P. Bertsekas: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Programming 55 (1992) 293–318.https://doi.org/10.1007/BF01581204Google Scholar
  12. D. Gabay: Applications of the method of multipliers to variational inequalities, in: Augmented Lagrangian Methods: Application to Numerical Solutions of Boundary-Value Problems, M. Fortin, R. Glowinski (eds.), Studies in Mathematics and its Applications 15, North-Holland, Amsterdam (1983) 299–331.https://doi.org/10.1016/S0168-2024(08)70034-1Google Scholar
  13. A. Lenoir, P. Mahey: A survey of monotone operator splitting methods for the decomposition of convex programs, RAIRO Oper. Res. 51 (2017) 17–41.https://doi.org/10.1051/ro/2015065Google Scholar
  14. P. L. Lions, B. Mercier: Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Analysis 16 (1979) 964–979.https://doi.org/10.1137/0716071Google Scholar
  15. P. Mahey, J. P. Dussault, A. Benchakroun, A. Hamdi: Adaptive scaling and convergence rates of a separable augmented Lagrangian algorithm, in: Optimization, Lecture Notes in Economics and Mathematical Systems 481, V. H. Nguyen, J. J. Strodiot, P. Tossings (eds.), Springer, Berlin (2000) 278–287.https://doi.org/10.1007/978-3-642-57014-8_19Google Scholar
  16. P. Mahey, S. Oualibouch, D. T. Pham: Proximal decomposition on the graph of a maximal monotone operator, SIAM J. Optimization 5 (1995) 454–466.https://doi.org/10.1137/0805023Google Scholar
  17. J. J. Moreau: Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. Française 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  18. Y. Nesterov: Smooth minimization of nonsmooth functions, Math. Programming, Series A 103 (2005) 127–152.https://doi.org/10.1007/s10107-004-0552-5Google Scholar
  19. T. Pennanen: A splitting method for composite mappings, Num. Functional Analysis Optimization 23 (2002) 875–890.https://doi.org/10.1081/NFA-120016274Google Scholar
  20. R. T. Rockafellar: Augmented lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1 (1976) 97–116.https://doi.org/10.1287/moor.1.2.97Google Scholar
  21. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optimization 14 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  22. R. Shefi, M. Teboulle: Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optimization 24 (2014) 269–297.https://doi.org/10.1137/130910774Google Scholar
  23. J. E. Spingarn: Partial inverse of a monotone operator, Appl. Math. Optimization 10 (1983) 247-265.https://doi.org/10.1007/BF01448388Google Scholar
  24. J. E. Spingarn: Applications of the method of partial inverses to convex programming:decomposition, Math. Programming 32 (1985) 199–223.https://doi.org/10.1007/BF01586091Google Scholar
  25. R. S. Varga: Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, (1966).Google Scholar

Suggested citation

E. Oré-Albornoz, P. Mahey, E. Ocaña-Anaya. “A Unified Splitting Algorithm for Composite Monotone Inclusions.” Journal of Convex Analysis 27 (2020), No. 3, 893–922. https://doi.org/10.68381/jca27045

Download BibTeXPublished by Heldermann Verlag.

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