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.
Similar content being viewed by others
References
Attouch, H., Peypouquet, J., Redont, P.: Backward–forward algorithms for structured monotone inclusions in Hilbert spaces. J. Math. Anal. Appl. (2016)
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)
Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 1st edn. Springer Publishing Company Incorporated, Berlin (2011)
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)
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)
Candes, E., Plan, Y.: Matrix completion with noise. Proc. IEEE 98(6), 925–936 (2010)
Cesàro, E.: Sur la convergence des séries. Nouvelles annales de mathé,matiques 3(7), 49–59 (1888)
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)
Combettes, P.L.: Systems of structured monotone inclusions: duality, algorithms, and applications. SIAM J. Optim. 23(4), 2420–2447 (2013)
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)
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)
Combettes, P.L., Yamada, I.: Compositions and convex combinations of averaged nonexpansive operators. J. Math. Anal. Appl. 425(1), 55–70 (2015)
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)
Davis, D.: Convergence rate analysis of the forward-Douglas-Rachford splitting scheme. SIAM J. Optim. 25(3), 1760–1786 (2014). arXiv:1410.2654v3
Davis, D.: Convergence rate analysis of primal-dual splitting schemes. SIAM J. Optim. 25(3), 1912–1943 (2015)
Davis, D.: Convergence rate analysis of the Forward-Douglas-Rachford splitting scheme. SIAM J. Optim. 25(3), 1760–1786 (2015)
Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes. arXiv:1406.4834v2 (2014)
Davis, D., Yin, W.: A Three-Operator Splitting Scheme and Its Optimization Applications. Tech. Rep CAM 15-13. University of California, Los Angeles (2015)
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)
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)
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)
Krasnosel’skii, M.A.: Two remarks on the method of successive approximations. Uspekhi Matematicheskikh Nauk 10(1), 123–127 (1955)
Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)
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)
Mann, W.R.: Mean value methods in iteration. Proc. Am. Math. Soc. 4(3), 506–510 (1953)
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)
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)
Stolz, O.: Vorlesungen ü Ber Allgemeine Arithmetik: Nach Den Neueren Ansichten. Leipzig, Teubners (1885)
Svaiter, B.F.: On weak convergence of the Douglas-Rachford method. SIAM J. Control. Optim. 49(1), 280–287 (2011)
Tseng, P.: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control. Optim. 29(1), 119–138 (1991)
Tseng, P.: A modified Forward-Backward splitting method for maximal monotone mappings. SIAM J. Control. Optim. 38(2), 431–446 (2000)
Vũ, B.C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. 38(3), 667–681 (2013)
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
Corresponding author
Rights and permissions
About this article
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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-017-0421-z
Keywords
- Operator splitting
- Three operators
- Fixed point
- Convex optimization
- Monotone inclusion
- Acceleration
- Douglas Rachford
- Forward backward