Abstract

We propose two inexact parallel splitting algorithms for computing the resolvent of a weighted sum of maximal monotone operators in a Hilbert space and show their strong convergence. We start by establishing new results on the asymptotic behavior of the Douglas-Rachford splitting algorithm for the sum of two operators. These results serve as a basis for the first algorithm. The second algorithm is based on an extension of a recent Dykstra-like method for computing the resolvent of the sum of two maximal monotone operators. Under standard qualification conditions, these two algorithms provide a means for computing the proximity operator of a weighted sum of lower semicontinuous convex functions. We show that a version of the second algorithm performs the same task without requiring any qualification condition. In turn, this provides a parallel splitting algorithm for qualification-free strongly convex programming.

Author information

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

Patrick L. Combettes

UPMC Université Paris 06, Lab. J.-L. Lions - UMR 7598, 75005 Paris, France

plc@math.jussieu.fr

Keywords

  • Dykstra's algorithm
  • Douglas-Rachford algorithm
  • maximal monotone operator
  • method of partial inverses
  • operator splitting
  • proximity operator
  • resolvent

Mathematics Subject Classification

47H05; 47J25, 49M29, 65K05, 90C25

References

  1. H. Attouch, H. Brézis: Duality for the sum of convex functions in general Banach spaces, in: Aspects of Mathematics and its Applications, J. A. Barroso (ed.), North-Holland Math. Library 34, North-Holland, Amsterdam (1986) 125–133.https://doi.org/10.1016/S0924-6509(09)70252-1Google Scholar
  2. H. Attouch, H. Riahi, M. Théra: Somme ponctuelle d’opérateurs maximaux monotones, Serdica Math. J. 22 (1996) 267–292.Google Scholar
  3. J.-P. Aubin, H. Frankowska: Set-Valued Analysis, Birkhäuser, Boston (1990).Google Scholar
  4. H. H. Bauschke, J. M. Borwein: Dykstra’s alternating projection algorithm for two sets, J. Approx. Theory 79 (1994) 418–443.https://doi.org/10.1006/jath.1994.1136Google 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, P. L. Combettes: A Dykstra-like algorithm for two monotone operators, Pacific J. Optim. 4 (2008) 383–391.Google Scholar
  7. H. H. Bauschke, P. L. Combettes, D. R. Luke: Finding best approximation pairs relative to two closed convex sets in Hilbert spaces, J. Approx. Theory 127 (2004) 178–192.https://doi.org/10.1016/j.jat.2004.02.006Google Scholar
  8. H. H. Bauschke, P. L. Combettes, S. Reich: The asymptotic behavior of the composition of two resolvents, Nonlinear Anal., Theory Methods Appl. 60A (2005) 283–301.https://doi.org/10.1016/j.na.2004.07.054Google Scholar
  9. J. P. Boyle, R. L. Dykstra: A method for finding projections onto the intersection of convex sets in Hilbert spaces, in: Advances in Order Restricted Statistical Inference, R. L. Dykstra et al. (ed.), Lecture Notes in Statistics 37, Springer, Berlin (1986) 28–47.https://doi.org/10.1007/978-1-4613-9940-7_3Google Scholar
  10. H. Brézis: Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert, North-Holland, Amsterdam (1973).Google Scholar
  11. H. Brézis, P.-L. Lions: Produits infinis de résolvantes, Israel J. Math. 29 (1978) 329–345.https://doi.org/10.1007/BF02761171Google Scholar
  12. Y. Censor, T. Elfving: A multiprojection algorithm using Bregman projections in a product space, Numer. Algorithms 8 (1994) 221–239.https://doi.org/10.1007/BF02142692Google Scholar
  13. C. Chaux, P. L. Combettes, J.-C. Pesquet, V. R. Wajs: A variational formulation for frame-based inverse problems, Inverse Probl. 23 (2007) 1495–1518.https://doi.org/10.1088/0266-5611/23/4/008Google Scholar
  14. P. L. Combettes: Inconsistent signal feasibility problems: least-squares solutions in a product space, IEEE Trans. Signal Process. 42 (1994) 2955–2966.https://doi.org/10.1109/78.330356Google Scholar
  15. P. L. Combettes: Fejér monotonicity in convex optimization, in: Encyclopedia of Optimization. Vol. 2, C. A. Floudas, P. M. Pardalos (eds.), Kluwer, Dordrecht (2001) 106–114.Google Scholar
  16. P. L. Combettes: Quasi-Fejérian analysis of some optimization algorithms, in: Inherently Parallel Algorithms for Feasibility and Optimization and their Applications, D. Butnariu, Y. Censor, S. Reich (eds.), Elsevier, Amsterdam (2001) 115–152.https://doi.org/10.1016/S1570-579X(01)80010-0Google Scholar
  17. P. L. Combettes: Solving monotone inclusions via compositions of nonexpansive averaged operators, Optimization 53 (2004) 475–504.https://doi.org/10.1080/02331930412331327157Google Scholar
  18. P. L. Combettes, S. A. Hirstoaga: Visco-penalization of the sum of two monotone operators, Nonlinear Anal., Theory Methods Appl. 69A (2008) 579–591.https://doi.org/10.1016/j.na.2007.06.003Google Scholar
  19. P. L. Combettes, J.-C. Pesquet: Proximal thresholding algorithm for minimization over orthonormal bases, SIAM J. Optim. 18 (2007) 1351–1376.https://doi.org/10.1137/060669498Google Scholar
  20. P. L. Combettes, J.-C. Pesquet: A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery, IEEE J. Selected Topics Signal Process. 1 (2007) 564–574.https://doi.org/10.1109/JSTSP.2007.910264Google Scholar
  21. P. L. Combettes, J.-C. Pesquet: A proximal decomposition method for solving convex variational inverse problems, Inverse Probl. 24 (2008), Article ID 065014.https://doi.org/10.1088/0266-5611/24/6/065014Google Scholar
  22. P. L. Combettes, V. R. Wajs: Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul. 4 (2005) 1168–1200.https://doi.org/10.1137/050626090Google Scholar
  23. F. Deutsch: Best Approximation in Inner Product Spaces, Springer, New York (2001).https://doi.org/10.1007/978-1-4684-9298-9Google Scholar
  24. J. Douglas, H. H. Rachford: On the numerical solution of heat conduction problems in two or three space variables, Trans. Amer. Math. Soc. 82 (1956) 421–439.https://doi.org/10.1090/S0002-9947-1956-0084194-4Google Scholar
  25. R. L. Dykstra: An algorithm for restricted least squares regression, J. Amer. Stat. Assoc. 78 (1983) 837–842.https://doi.org/10.1080/01621459.1983.10477029Google Scholar
  26. J. Eckstein, D. P. Bertsekas: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., Ser. A 55 (1992) 293–318.https://doi.org/10.1007/BF01581204Google Scholar
  27. N. Gaffke, R. Mathar: A cyclic projection algorithm via duality, Metrika 36 (1989) 29–54.https://doi.org/10.1007/BF02614077Google Scholar
  28. H. Idrissi, O. Lefebvre, C. Michelot: Applications and numerical convergence of the partial inverse method, in: Optimization, S. Dolecki (ed.), Lecture Notes in Mathematics 1405, Springer, Berlin (1989) 39–54.https://doi.org/10.1007/BFb0083585Google Scholar
  29. A. N. Iusem, A. R. de Pierro: On the convergence of Han’s method for convex programming with quadratic objective, Math. Program., Ser. B 52 (1991) 265–284.https://doi.org/10.1007/BF01582891Google Scholar
  30. M. L. Lapidus: Generalization of the Trotter-Lie formula, Integral Equations Oper. Theory 4 (1981) 366–415.https://doi.org/10.1007/BF01697972Google Scholar
  31. J. Lawrence, J. E. Spingarn: On fixed points of nonexpansive piecewise isometric mappings, Proc. Lond. Math. Soc., III. Ser. 55 (1987) 605–624.https://doi.org/10.1112/plms/s3-55.3.605Google Scholar
  32. B. Lemaire: The proximal algorithm, in: New Methods in Optimization and their Industrial Uses, J.-P. Penot (ed.), International Series of Numerical Mathematics 87, Birkhäuser, Basel (1989) 73–87.Google Scholar
  33. P.-L. Lions: Une méthode itérative de résolution d’une inéquation variationnelle, Israel J. Math. 31 (1978) 204–208.https://doi.org/10.1007/BF02760552Google Scholar
  34. 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
  35. Ph. Mahey, S. Oualibouch, Pham Dinh Tao: Proximal decomposition on the graph of a maximal monotone operator, SIAM J. Optim. 5 (1995) 454–466.https://doi.org/10.1137/0805023Google Scholar
  36. B. Martinet: Algorithmes pour la Résolution de Problèmes d’Optimisation et de Minimax, Thèse, Université de Grenoble (1972).Google Scholar
  37. J.-J. Moreau: Fonctions convexes duales et points proximaux dans un espace hilbertien, C. R. Acad. Sci., Paris 255 (1962) 2897–2899.Google Scholar
  38. J.-J. Moreau: Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  39. G. B. Passty: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Anal. Appl. 72 (1979) 383–390.https://doi.org/10.1016/0022-247X(79)90234-8Google Scholar
  40. G. Pierra: Éclatement de contraintes en parallèle pour la minimisation d’une forme quadratique, in: Optimization Techniques. Modeling and Optimization in the Service of Man. Part 2, J. Cea (ed.), Lecture Notes in Computer Science 41, Springer, Berlin (1976) 200–218.https://doi.org/10.1007/3-540-07623-9_288Google Scholar
  41. G. Pierra: Decomposition through formalization in a product space, Math. Program. 28 (1984) 96–115.https://doi.org/10.1007/BF02612715Google Scholar
  42. B. T. Polyak: Introduction to Optimization, Optimization Software, New York (1987).Google Scholar
  43. S. Reich: A limit theorem for projections, Linear Multilinear Algebra 13 (1983) 281–290.https://doi.org/10.1080/03081088308817526Google Scholar
  44. 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
  45. R. T. Rockafellar, R. J. B. Wets: Variational Analysis, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  46. L. I. Rudin, S. Osher, E. Fatemi: Nonlinear total variation based noise removal algorithms, Physica D 60 (1992) 259–268.https://doi.org/10.1016/0167-2789(92)90242-FGoogle Scholar
  47. S. Simons: From Hahn-Banach to Monotonicity, Lecture Notes in Mathematics 1693, Springer, Berlin (2008).Google Scholar
  48. J. E. Spingarn: Partial inverse of a monotone operator, Appl. Math. Optimization 10 (1983) 247–265.https://doi.org/10.1007/BF01448388Google Scholar
  49. J. E. Spingarn: Applications of the method of partial inverses to convex programming: decomposition, Math. Program. 32 (1985) 199–223.https://doi.org/10.1007/BF01586091Google Scholar
  50. J. E. Spingarn: A projection method for least-squares solutions to overdetermined systems of linear inequalities, Linear Algebra Appl. 86 (1987) 211–236.https://doi.org/10.1016/0024-3795(87)90296-5Google Scholar
  51. J. A. Tropp: Just relax: convex programming methods for identifying sparse signals in noise, IEEE Trans. Inf. Theory 52 (2006) 1030–1051.https://doi.org/10.1109/TIT.2005.864420Google Scholar
  52. E. Zeidler: Nonlinear Functional Analysis and its Applications. II/B: Nonlinear Monotone Operators, Springer, New York (1990).https://doi.org/10.1007/978-1-4612-0985-0Google Scholar

Suggested citation

P. L. Combettes. “Iterative Construction of the Resolvent of a Sum of Maximal Monotone Operators.” Journal of Convex Analysis 16 (2009), No. 3&4, 727–748. https://doi.org/10.68381/jca16044

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2009. Rights now held by Banach Press.