Skip to main content
SpringerLink
Log in

A Three-Operator Splitting Scheme and its Optimization Applications

  • Published:
Set-Valued and Variational Analysis Aims and scope Submit manuscript

Abstract

Operator-splitting methods convert optimization and inclusion problems into fixed-point equations; when applied to convex optimization and monotone inclusion problems, the equations given by operator-splitting methods are often easy to solve by standard techniques. The hard part of this conversion, then, is to design nicely behaved fixed-point equations. In this paper, we design a new, and thus far, the only nicely behaved fixed-point equation for solving monotone inclusions with three operators; the equation employs resolvent and forward operators, one at a time, in succession. We show that our new equation extends the Douglas-Rachford and forward-backward equations; we prove that standard methods for solving the equation converge; and we give two accelerated methods for solving the equation.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Attouch, H., Peypouquet, J., Redont, P.: Backward–forward algorithms for structured monotone inclusions in Hilbert spaces. J. Math. Anal. Appl. (2016)

  2. Bauschke, H.H., Bello Cruz, J.Y., Nghia, T.T.A., Phan, H.M., Wang, X.: The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle. Journal of Approximation Theory 185(0), 63–79 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 1st edn. Springer Publishing Company Incorporated, Berlin (2011)

    Book  MATH  Google Scholar 

  4. Boṫ, R.I., Csetnek, E.R., Heinrich, A., Hendrich, C.: On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems. Math. Program. 150(2), 251–279 (2015)

    Article  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)

    Article  MathSciNet  MATH  Google Scholar 

  6. Candes, E., Plan, Y.: Matrix completion with noise. Proc. IEEE 98(6), 925–936 (2010)

    Article  Google Scholar 

  7. Cesàro, E.: Sur la convergence des séries. Nouvelles annales de mathé,matiques 3(7), 49–59 (1888)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Combettes, P.L.: Systems of structured monotone inclusions: duality, algorithms, and applications. SIAM J. Optim. 23(4), 2420–2447 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  10. 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. Paris, France (2014)

  11. 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 and Variational Analysis 20(2), 307–330 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  12. Combettes, P.L., Yamada, I.: Compositions and convex combinations of averaged nonexpansive operators. J. Math. Anal. Appl. 425(1), 55–70 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  13. 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)

    Article  MathSciNet  MATH  Google Scholar 

  14. Davis, D.: Convergence rate analysis of the forward-Douglas-Rachford splitting scheme. SIAM J. Optim. 25(3), 1760–1786 (2014). arXiv:1410.2654v3

  15. Davis, D.: Convergence rate analysis of primal-dual splitting schemes. SIAM J. Optim. 25(3), 1912–1943 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  16. Davis, D.: Convergence rate analysis of the Forward-Douglas-Rachford splitting scheme. SIAM J. Optim. 25(3), 1760–1786 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  17. Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes. arXiv:1406.4834v2 (2014)

  18. Davis, D., Yin, W.: A Three-Operator Splitting Scheme and Its Optimization Applications. Tech. Rep CAM 15-13. University of California, Los Angeles (2015)

    Google Scholar 

  19. Davis, D., Yin, W.: Convergence Rate Analysis of Several Splitting Schemes. In: Glowinski, R., Osher, S., Yin, W. (eds.) Splitting Methods in Communication and Imaging, Science and Engineering, p. Chapter 4, pp. 115–163. Springer, Berlin (2016)

  20. Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & Mathematics with Applications 2(1), 17–40 (1976)

    Article  MATH  Google Scholar 

  21. Glowinski, R., Marroco, A.: On the approximation by finite elements of order one, and resolution, penalisation-duality for a class of nonlinear Dirichlet problems. ESAIM: Mathematical Modelling and Numerical Analysis - Mathematical Modelling and Numerical Analysis 9(R2), 41–76 (1975)

    MATH  Google Scholar 

  22. Krasnosel’skii, M.A.: Two remarks on the method of successive approximations. Uspekhi Matematicheskikh Nauk 10(1), 123–127 (1955)

    MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  24. Liu, J., Musialski, P., Wonka, P., Ye, J.: Tensor completion for estimating missing values in visual data. IEEE Trans. Pattern Anal. Mach. Intell. 35(1), 208–220 (2013)

    Article  Google Scholar 

  25. Mann, W.R.: Mean value methods in iteration. Proc. Am. Math. Soc. 4(3), 506–510 (1953)

    Article  MathSciNet  MATH  Google Scholar 

  26. 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)

    Article  MathSciNet  MATH  Google Scholar 

  27. Peng, Z., Wu, T., Xu, Y., Yan, M., Yin, W.: Coordinate friendly structures, algorithms and applications. Ann. Mater. Sci. Appl. 1(1), 57–119 (2016)

    Google Scholar 

  28. Stolz, O.: Vorlesungen ü Ber Allgemeine Arithmetik: Nach Den Neueren Ansichten. Leipzig, Teubners (1885)

    Google Scholar 

  29. Svaiter, B.F.: On weak convergence of the Douglas-Rachford method. SIAM J. Control. Optim. 49(1), 280–287 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  30. Tseng, P.: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control. Optim. 29(1), 119–138 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  31. Tseng, P.: A modified Forward-Backward splitting method for maximal monotone mappings. SIAM J. Control. Optim. 38(2), 431–446 (2000)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The work is supported in part by an NSF math postdoctoral fellowship, NSF grant ECCS-1462397, and ONR Grant N000141712162.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of California, Los Angeles, CA, 90055, USA

    Damek Davis & Wotao Yin

Authors
  1. Damek Davis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wotao Yin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wotao Yin.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Davis, D., Yin, W. A Three-Operator Splitting Scheme and its Optimization Applications. Set-Valued Var. Anal 25, 829–858 (2017). https://doi.org/10.1007/s11228-017-0421-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11228-017-0421-z

Keywords

Mathematics Subject Classification (2010)

Search

Navigation