Abstract

We introduce the first operator splitting method for composite monotone inclusions outside of Hilbert spaces. The proposed primal-dual method constructs iteratively the best Bregman approximation to an arbitrary point from the Kuhn-Tucker set of a composite monotone inclusion. Strong convergence is established in reflexive Banach spaces without requiring additional restrictions on the monotone operators or knowledge of the norms of the linear operators involved in the model. The monotone operators are activated via Bregman distance-based resolvent operators. The method is novel even in Euclidean spaces, where it provides an alternative to the usual proximal methods based on the standard distance.

Author information

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

Patrick L. Combettes

Sorbonne Universités, UPMC Univ. Paris 06, Laboratoire Jacques-Louis Lions, 75005 Paris, France

plc@ljll.math.upmc.fr

Quang Van Nguyen

Sorbonne Universités, UPMC Univ. Paris 06, Laboratoire Jacques-Louis Lions, 75005 Paris, France

quangnv@ljll.math.upmc.fr

Keywords

  • Best approximation
  • Banach space
  • Bregman distance
  • duality
  • Legendre function
  • monotone operator
  • operator splitting
  • primal-dual algorithm

References

  1. M. A. Alghamdi, A. Alotaibi, P. L. Combettes, N. Shahzad: A primal-dual method of partial inverses for composite inclusions, Optim. Lett. 8 (2014) 2271–2284.https://doi.org/10.1007/s11590-014-0734-xGoogle Scholar
  2. A. Alotaibi, P. L. Combettes, N. Shahzad: Solving coupled composite monotone inclusions by successive Fejér approximations of their Kuhn-Tucker set, SIAM J. Optim. 24 (2014) 2076–2095.https://doi.org/10.1137/130950616Google Scholar
  3. A. Alotaibi, P. L. Combettes, N. Shahzad: Best approximation from the Kuhn-Tucker set of composite monotone inclusions, Numer. Funct. Anal. Optim. 36 (2015) 1513–1532.https://doi.org/10.1080/01630563.2015.1077864Google Scholar
  4. H. Attouch, L. M. Briceño-Arias, P. L. Combettes: A strongly convergent primal-dual method for nonoverlapping domain decomposition, Numer. Math. (2015); publ. online.https://doi.org/10.1007/s00211-015-0751-4Google Scholar
  5. H. H. Bauschke, J. M. Borwein: Legendre functions and the method of random Bregman projections, J. Convex Analysis 4 (1997) 27–67.https://doi.org/10.68381/jca04002Google Scholar
  6. H. H. Bauschke, J. M. Borwein, P. L. Combettes: Essential smoothness, essential strict convexity, and Legendre functions in Banach spaces, Commun. Contemp. Math. 3 (2011) 615–647.https://doi.org/10.1142/S0219199701000524Google Scholar
  7. H. H. Bauschke, J. M. Borwein, P. L. Combettes: Bregman monotone optimization algorithms, SIAM J. Control Optim. 42 (2003) 596–636.https://doi.org/10.1137/S0363012902407120Google Scholar
  8. H. H. Bauschke, P. L. Combettes: Construction of best Bregman approximations in reflexive Banach spaces, Proc. Amer. Math. Soc. 131 (2003) 3757–3766.https://doi.org/10.1090/S0002-9939-03-07050-3Google Scholar
  9. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, New York (2011).https://doi.org/10.1007/978-1-4419-9467-7Google Scholar
  10. J. M. Borwein: Fifty years of maximal monotonicity, Optim. Lett. 4 (2010) 473–490.https://doi.org/10.1007/s11590-010-0178-xGoogle Scholar
  11. R. I. Boţ, E. R. Csetnek, A. Heinrich: A primal-dual splitting algorithm for finding zeros of sums of maximal monotone operators, SIAM J. Optim. 23 (2013) 2011–2036.https://doi.org/10.1137/12088255XGoogle Scholar
  12. R. I. Boţ, C. Hendrich: A Douglas-Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators, SIAM J. Optim. 23 (2013) 2541–2565.https://doi.org/10.1137/120901106Google Scholar
  13. L. M. Bregman: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Comput. Math. Math. Phys. 7 (1967) 200–217.https://doi.org/10.1016/0041-5553(67)90040-7Google Scholar
  14. L. M. Briceño-Arias, P. L. Combettes: A monotone+skew splitting model for composite monotone inclusions in duality, SIAM J. Optim. 21 (2011) 1230–1250.https://doi.org/10.1137/10081602XGoogle Scholar
  15. F. E. Browder: Multi-valued monotone nonlinear mappings and duality mappings in Banach spaces, Trans. Amer. Math. Soc. 118 (1965) 338–351.https://doi.org/10.1090/S0002-9947-1965-0180884-9Google Scholar
  16. Y. Censor, S. A. Zenios: Parallel Optimization: Theory, Algorithms and Applications, Oxford University Press, Oxford (1997).Google Scholar
  17. I. Cioranescu: Geometry of Banach spaces, Duality Mappings and Nonlinear Problems, Kluwer, Dordrecht (1990).https://doi.org/10.1007/978-94-009-2121-4Google Scholar
  18. P. L. Combettes: Strong convergence of block-iterative outer approximation methods for convex optimization, SIAM J. Control Optim. 38 (2000) 538–565.https://doi.org/10.1137/S036301299732626XGoogle Scholar
  19. P. L. Combettes: Systems of structured monotone inclusions: Duality, algorithms, and applications, SIAM J. Optim. 23 (2013) 2420–2447.https://doi.org/10.1137/130904160Google Scholar
  20. P. L. Combettes, B. C. Vũ: Variable metric forward-backward splitting with applications to monotone inclusions in duality, Optimization 63 (2014) 1289–1318.https://doi.org/10.1080/02331934.2012.733883Google Scholar
  21. R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, D. E. Knuth: On the Lambert W function, Adv. Comput. Math. 5 (1996) 329–359.https://doi.org/10.1007/BF02124750Google Scholar
  22. J. Eckstein: Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming, Math. Oper. Res. 18 (1993) 202–226.https://doi.org/10.1287/moor.18.1.202Google Scholar
  23. Y. Haugazeau: Sur les Inéquations Variationnelles et la Minimisation de Fonctionnelles Convexes, Thèse, Université de Paris, Paris (1968).Google Scholar
  24. R. I. Kačurovskiĭ: On monotone operators and convex functionals, Usp. Mat. Nauk. 15 (1960) 213–215.Google Scholar
  25. G. Kassay: The proximal points algorithm for reflexive Banach spaces, Studia Univ. Babeş-Bolyai Math. 30 (1985) 9–17.Google Scholar
  26. J. H. Lamberti: Observationes variae in mathesin puram, Acta Helvetica, Physico-Mathematico-Anatomico-Botanico-Medica 3 (1758) 128–168.Google Scholar
  27. P. L. Lions, B. Mercier: Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16 (1979) 964–979.https://doi.org/10.1137/0716071Google Scholar
  28. B. Mercier: Topics in Finite Element Solution of Elliptic Problems, Lectures on Mathematics 63, Tata Institute of Fundamental Research, Bombay (1979).https://doi.org/10.1007/978-3-662-00973-4Google Scholar
  29. G. J. Minty: On the maximal domain of a “monotone” function, Michigan Math. J. 8 (1961) 135–137.https://doi.org/10.1307/mmj/1028998564Google Scholar
  30. G. J. Minty: Monotone (nonlinear) operators in Hilbert space, Duke Math. J. 29 (1962) 341–346.https://doi.org/10.1215/S0012-7094-62-02933-2Google Scholar
  31. J. J. Moreau: Fonctions convexes duales et points proximaux dans un espace hilbertien, C. R. Acad. Sci., Paris 255 (1962) 2897–2899.Google Scholar
  32. J. J. Moreau: Fonctionnelles sous-différentiables, C. R. Acad. Sci., Paris 257 (1963) 4117–4119.Google Scholar
  33. T. Pennanen: Dualization of generalized equations of maximal monotone type, SIAM J. Optim. 10 (2000) 809–835.https://doi.org/10.1137/S1052623498340448Google Scholar
  34. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  35. S. Simons: From Hahn-Banach to Monotonicity, 2nd Ed., Lecture Notes in Math. 1693, Springer, New York (2008).Google Scholar
  36. M. Teboulle: Entropic proximal mappings with applications to nonlinear programming, Math. Oper. Res. 17 (1992) 670–690.https://doi.org/10.1287/moor.17.3.670Google Scholar
  37. P. Tseng: A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim. 38 (2000) 431–446.https://doi.org/10.1137/S0363012998338806Google Scholar
  38. B. C. Vũ: A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comput. Math. 38 (2013) 667–681.https://doi.org/10.1007/s10444-011-9254-8Google Scholar
  39. C. Zălinescu: On uniformly convex functions, J. Math. Anal. Appl. 95 (1983) 344–374.https://doi.org/10.1016/0022-247X(83)90112-9Google Scholar
  40. C. Zălinescu: Convex Analysis in General Vector Spaces, World Scientific, River Edge (2002).https://doi.org/10.1142/5021Google Scholar
  41. E. H. Zarantonello: Solving functional equations by contractive averaging, Tech. Report 160, Math. Res. Center, University of Wisconsin, Madison (1960).Google Scholar
  42. E. Zeidler: Nonlinear Functional Analysis and Its Applications, Vols. I–V, Springer, New York (1985–1993).https://doi.org/10.1007/978-1-4612-5020-3Google Scholar

Suggested citation

P. L. Combettes, Q. V. Nguyen. “Solving Composite Monotone Inclusions in Reflexive Banach Spaces by Constructing Best Bregman Approximations from Their Kuhn-Tucker Set.” Journal of Convex Analysis 23 (2016), No. 2, 481–510. https://doi.org/10.68381/jca23018

Download BibTeXPublished by Heldermann Verlag.

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