SpringerLink
Log in

Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

Given the success of Douglas–Rachford splitting (DRS), it is natural to ask whether DRS can be generalized. Are there other 2 operator resolvent-splittings sharing the favorable properties of DRS? Can DRS be generalized to 3 operators? This work presents the answers: no and no. In a certain sense, DRS is the unique 2 operator resolvent-splitting, and generalizing DRS to 3 operators is impossible without lifting, where lifting roughly corresponds to enlarging the problem size. The impossibility result further raises a question. How much lifting is necessary to generalize DRS to 3 operators? This work presents the answer by providing a novel 3 operator resolvent-splitting with provably minimal lifting that directly generalizes DRS.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Banert, S.: A relaxed forward–backward splitting algorithm for inclusions of sums of monotone operators. Master’s thesis, Technische Universität Chemnitz (2012)

  2. Barbero, Á., Sra, S.: Fast Newton-type methods for total variation regularization. In: Proceedings of the 28th International Conference on International Conference on Machine Learning (ICML), pp. 313–320 (2011)

  3. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd edn. Springer, New York (2017)

    MATH  Google Scholar 

  4. Boţ, R., Wanka, G.: Farkas-type results with conjugate functions. SIAM J. Optim. 15(2), 540–554 (2005)

    MathSciNet  MATH  Google Scholar 

  5. Boţ, R.I., Hendrich, C.: A Douglas–Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators. SIAM J. Optim. 23(4), 2541–2565 (2013)

    MathSciNet  MATH  Google Scholar 

  6. Boţ, R.I., Hendrich, C.: Convex risk minimization via proximal splitting methods. Optim. Lett. 9(5), 867–885 (2015)

    MathSciNet  MATH  Google Scholar 

  7. Brezis, H., Lions, P.L.: Produits infinis de resolvantes. Isr. J. Math. 29(4), 329–345 (1978)

    MATH  Google Scholar 

  8. Briceño-Arias, L.M.: Forward-Douglas–Rachford splitting and forward-partial inverse method for solving monotone inclusions. Optimization 64(5), 1239–1261 (2015)

    MathSciNet  MATH  Google Scholar 

  9. Briceño-Arias, L.M., Combettes, P.L.: A monotone + skew splitting model for composite monotone inclusions in duality. SIAM J. Optim. 21(4), 1230–1250 (2011)

    MathSciNet  MATH  Google Scholar 

  10. Briceño-Arias, L.M., Davis, D.: Forward–backward–half forward algorithm with non self-adjoint linear operators for solving monotone inclusions. SIAM J. Optim. 28(4), 2839–2871 (2018)

    MathSciNet  MATH  Google Scholar 

  11. Brodie, J., Daubechies, I., De Mol, C., Giannone, D., Loris, I.: Sparse and stable Markowitz portfolios. Proc. Natl. Acad. Sci. U. S. A. 106(30), 12267–12272 (2009)

    MATH  Google Scholar 

  12. Byrne, C.L.: Iterative image reconstruction algorithms based on cross-entropy minimization. IEEE Trans. Image Process. 2(1), 96–103 (1993)

    Google Scholar 

  13. Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120–145 (2011)

    MathSciNet  MATH  Google Scholar 

  14. Chaux, C., Pesquet, J., Pustelnik, N.: Nested iterative algorithms for convex constrained image recovery problems. SIAM J. Imaging Sci. 2(2), 730–762 (2009)

    MathSciNet  MATH  Google Scholar 

  15. Chen, P., Huang, J., Zhang, X.: A primal-dual fixed point algorithm for convex separable minimization with applications to image restoration. Inverse Probl. 29(2), 025011 (2013)

    MathSciNet  MATH  Google Scholar 

  16. Chen, P., Huang, J., Zhang, X.: A primal-dual fixed point algorithm for minimization of the sum of three convex separable functions. Fixed Point Theory Appl. 2016, 54 (2016)

    MathSciNet  MATH  Google Scholar 

  17. Chen, Y., Ye, X.: Projection onto a simplex. ar**v preprint ar**v:1101.6081 (2011)

  18. Combettes, P.L., Condat, L., Pesquet, J.C., Vũ, B.C.: A forward–backward view of some primal-dual optimization methods in image recovery. In: IEEE International Conference on Image Processing (2014)

  19. Combettes, P.L., Eckstein, J.: Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions. Math. Program. 168(1), 645–672 (2018)

    MathSciNet  MATH  Google Scholar 

  20. Combettes, P.L., Pesquet, J.C.: A proximal decomposition method for solving convex variational inverse problems. Inverse Probl. 24(6), 065014 (2008)

    MathSciNet  MATH  Google Scholar 

  21. Combettes, P.L., Pesquet, J.C.: Proximal splitting methods in signal processing. In: Bauschke, H., Burachik, R., Combettes, P., Elser, V., Luke, D., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 185–212. Springer, Berlin (2011)

    MATH  Google Scholar 

  22. Combettes, P.L., Pesquet, J.C.: Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators. Set Valued Var. Anal. 20(2), 307–330 (2012)

    MathSciNet  MATH  Google Scholar 

  23. Condat, L.: A direct algorithm for 1-D total variation denoising. IEEE Signal Process. Lett. 20(11), 1054–1057 (2013)

    Google Scholar 

  24. Condat, L.: A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl. 158(2), 460–479 (2013)

    MathSciNet  MATH  Google Scholar 

  25. Davis, D., Yin, W.: A three-operator splitting scheme and its optimization applications. Set Valued Var. Anal. 25(4), 829–858 (2017)

    MathSciNet  MATH  Google Scholar 

  26. Dinh, N., Goberna, M.A., López, M.A., Son, T.Q.: New Farkas-type constraint qualifications in convex infinite programming. ESAIM Control Optim. Calc. Var. 13(3), 580–597 (2007)

    MathSciNet  MATH  Google Scholar 

  27. Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82, 421–439 (1956)

    MathSciNet  MATH  Google Scholar 

  28. Drori, Y., Sabach, S., Teboulle, M.: A simple algorithm for a class of nonsmooth convex–concave saddle-point problems. Oper. Res. Lett. 43(2), 209–214 (2015)

    MathSciNet  MATH  Google Scholar 

  29. Eckstein, J.: A simplified form of block-iterative operator splitting and an asynchronous algorithm resembling the multi-block alternating direction method of multipliers. J. Optim. Theory Appl. 173(1), 155–182 (2017)

    MathSciNet  MATH  Google Scholar 

  30. Esser, E., Zhang, X., Chan, T.F.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015–1046 (2010)

    MathSciNet  MATH  Google Scholar 

  31. Farkas, J.: Theorie der einfachen ungleichungen. Journal für die reine und angewandte Mathematik 124, 1–27 (1902)

    MathSciNet  MATH  Google Scholar 

  32. Johnstone, P.R., Eckstein, J.: Projective splitting with forward steps: asynchronous and block-iterative operator splitting. ar**v preprint ar**v:1803.07043 (2018)

  33. Johnstone, P.R., Eckstein, J.: Convergence rates for projective splitting. SIAM J. Optim. (2019)

  34. Kamilov, U., Bostan, E., Unser, M.: Generalized total variation denoising via augmented Lagrangian cycle spinning with Haar wavelets. In: 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 909–912 (2012)

  35. Karahanoglu, F.I., Bayram, İ., Ville, D.V.D.: A signal processing approach to generalized 1-D total variation. IEEE Trans. Signal Process. 59(11), 5265–5274 (2011)

    MathSciNet  MATH  Google Scholar 

  36. Latafat, P., Patrinos, P.: Asymmetric forward–backward–adjoint splitting for solving monotone inclusions involving three operators. Comput. Optim. Appl. 68(1), 57–93 (2017)

    MathSciNet  MATH  Google Scholar 

  37. Le, T., Chartrand, R., Asaki, T.J.: A variational approach to reconstructing images corrupted by Poisson noise. J. Math. Imaging Vis. 27(3), 257–263 (2007)

    MathSciNet  Google Scholar 

  38. Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)

    MathSciNet  MATH  Google Scholar 

  39. Loris, I., Verhoeven, C.: On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty. Inverse Probl. 27(12), 125007 (2011)

    MathSciNet  MATH  Google Scholar 

  40. Malitsky, Y., Tam, M.K.: A forward–backward splitting method for monotone inclusions without cocoercivity. ar**v preprint ar**v:1808.04162 (2018)

  41. Martinet, B.: Régularisation d’inéquations variationnelles par approximations successives. Rev. Fr. d’Inform. Rech. Oper. Sér. Rouge 4(3), 154–158 (1970)

    MATH  Google Scholar 

  42. Martinet, B.: Determination approchée d’un point fixe d’une application pseudo-contractante. C. R. l’Acad. Sci. Sér. A 274, 163–165 (1972)

    MATH  Google Scholar 

  43. Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. J. Math. Anal. Appl. 72(2), 383–390 (1979)

    MathSciNet  MATH  Google Scholar 

  44. Peaceman, D.W., Rachford, H.H.: The numerical solution of parabolic and elliptic differential equations. J. Soc. Ind. Appl. Math. 3(1), 28–41 (1955)

    MathSciNet  MATH  Google Scholar 

  45. Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the Mumford-Shah functional. In: IEEE International Conference on Computer Vision (2009)

  46. Raguet, H.: A note on the forward-Douglas-Rachford splitting for monotone inclusion and convex optimization. Optim. Lett. 13(4), 717–740 (2019). https://doi.org/10.1007/s11590-018-1272-8

    Article  MathSciNet  MATH  Google Scholar 

  47. Raguet, H., Fadili, J., Peyré, G.: A generalized forward–backward splitting. SIAM J. Imaging Sci. 6(3), 1199–1226 (2013)

    MathSciNet  MATH  Google Scholar 

  48. Rapaport, F., Barillot, E., Vert, J.P.: Classification of arrayCGH data using fused SVM. Bioinformatics 24(13), i375–i382 (2008)

    Google Scholar 

  49. Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877–898 (1976)

    MathSciNet  MATH  Google Scholar 

  50. Ryu, E.K., Boyd, S.: Primer on monotone operator methods. Appl. Comput. Math. 15, 3–43 (2016)

    MathSciNet  MATH  Google Scholar 

  51. S**arn, J.E.: Applications of the method of partial inverses to convex programming: decomposition. Math. Program. 32(2), 199–223 (1985)

    MathSciNet  MATH  Google Scholar 

  52. Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., Knight, K.: Sparsity and smoothness via the fused lasso. J. R. Stat. Soc. Ser. B. Stat. Methodol. 67(1), 91–108 (2005)

    MathSciNet  MATH  Google Scholar 

  53. Tibshirani, R., Wang, P.: Spatial smoothing and hot spot detection for CGH data using the fused lasso. Biostatistics 9(1), 18–29 (2008)

    MATH  Google Scholar 

  54. Tseng, P.: A modified forward–backward splitting method for maximal monotone map**s. SIAM J. Control Optim. 38(2), 431–446 (2000)

    MathSciNet  MATH  Google Scholar 

  55. Vũ, B.C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. 38(3), 667–681 (2013)

    MathSciNet  MATH  Google Scholar 

  56. Wahlberg, B., Boyd, S., Annergren, M., Wang, Y.: An ADMM algorithm for a class of total variation regularized estimation problems. IFAC Proc. Vol. 45(16), 83–88 (2012)

    Google Scholar 

  57. Yan, M.: A new primal-dual algorithm for minimizing the sum of three functions with a linear operator. J. Sci. Comput. 76(3), 1698–1717 (2018)

    MathSciNet  MATH  Google Scholar 

  58. Zanella, R., Boccacci, P., Zanni, L., Bertero, M.: Efficient gradient projection methods for edge-preserving removal of Poisson noise. Inverse Probl. 25(4), 045010 (2009)

    MathSciNet  MATH  Google Scholar 

  59. Zhu, M., Chan, T.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration. UCLA CAM Report 08–34 (2008)

Download references

Acknowledgements

I would like to thank Wotao Yin for helpful comments and suggestions. I would also like to thank the anonymous associate editor and referees whose comments improved the paper significantly. In particular, the signal denoising numerical example was suggested by one of the anonymous reviewers. This work is supported in part by NSF Grant DMS-1720237 and ONR Grant N000141712162.

Author information

Authors and Affiliations

  1. 7324 Mathematical Sciences, UCLA, Los Angeles, CA, 90095, USA

    Ernest K. Ryu

Authors
  1. Ernest K. Ryu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ernest K. Ryu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ryu, E.K. Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting. Math. Program. 182, 233–273 (2020). https://doi.org/10.1007/s10107-019-01403-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-019-01403-1

Keywords

Mathematics Subject Classification

Search

Navigation