Abstract
We shed light on the structure of the “three-operator” version of the forward-Douglas–Rachford splitting algorithm for finding a zero of a sum of maximally monotone operators \(A + B + C\), where B is cocoercive, involving only the computation of B and of the resolvent of A and of C, separately. We show that it is a straightforward extension of a fixed-point algorithm proposed by us as a generalization of the forward–backward splitting algorithm, initially designed for finding a zero of a sum of an arbitrary number of maximally monotone operators \(\sum _{i=1}^n A_i + B\), where B is cocoercive, involving only the computation of B and of the resolvent of each \(A_i\) separately. We argue that, the former is the “true” forward-Douglas–Rachford splitting algorithm, in contrast to the initial use of this designation in the literature. Then, we highlight the extension to an arbitrary number of maximally monotone operators in the splitting, \(\sum _{i=1}^{n} A_i + B + C\), in a formulation admitting preconditioning operators. We finally demonstate experimentally its interest in the context of nonsmooth convex optimization.
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11590-018-1272-8/MediaObjects/11590_2018_1272_Fig1_HTML.gif)
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11590-018-1272-8/MediaObjects/11590_2018_1272_Fig2_HTML.gif)
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11590-018-1272-8/MediaObjects/11590_2018_1272_Fig3_HTML.gif)
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11590-018-1272-8/MediaObjects/11590_2018_1272_Fig4_HTML.gif)
Similar content being viewed by others
Notes
Note that we use here both standard notations: when N is an integer, \(\mathbb {R}^N\) is the Cartesian product of N copies of the set \(\mathbb {R}\); when E is a finite set, \(\mathbb {R}^E\) is the set of all applications from E to \(\mathbb {R}\), isomorphic to \(\mathbb {R}^{|E|}\).
References
Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)
Becker, H., Albera, L., Comon, P., Gribonval, R., Merlet, I.: Fast, variation-based methods for the analysis of extended brain sources. In: European Signal Processing Conference (2014)
Brice no-Arias, L.M.: Forward-Douglas–Rachford splitting and forward-partial inverse method for solving monotone inclusions. Optimization 64(5), 1239–1261 (2015)
Cevher, V., Vu, C.B., Yurtsever, A.: Stochastic forward-Douglas-Rachford splitting for monotone inclusions. Technical Report, EPFL (2016)
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)
Combettes, P.L.: Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53(5–6), 475–504 (2004)
Combettes, P.L., Pesquet, J.-C.: Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum monotone operators. Set Valued Var. Anal. 20(2), 307–330 (2012)
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., Yin, W.: A three-operator splitting scheme and its optimization applications. Set Valued Var. Anal. 25(4), 829–858 (2017)
Demantké, J., Mallet, C., David, N., Vallet, B.: Dimensionality based scale selection in 3D LIDAR point clouds. In: International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXXVIII-5/W12, pp. 97–102 (2011)
Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(3), 293–318 (1992)
Gramfort, A., Thirion, B., Varoquaux, G.: Identifying predictive regions from fMRI with TV-\(\ell _1\) prior. In: Pattern Recognition in Neuroimaging, IEEE (2013)
Guinard, S., Landrieu, L.: Weakly supervised segmentation-aided classification of urban scenes from 3D LiDAR point clouds. In: ISPRS Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XLII-1/W1, pp. 151–157 (2017)
Landrieu, L., Raguet, H., Vallet, B., Mallet, C., Weinmann, M.: A structured regularization framework for spatially smoothing semantic labelings of 3D point clouds. J. Photogramm. Remote Sens. 132, 102–118 (2017)
Lions, P.-L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)
Minty, G.J.: Monotone (nonlinear) operators in Hilbert space. Duke Math. J. 29, 341–346 (1962)
Pock, T., Chambolle, A.: Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In: IEEE International Conference on Computer Vision, pp. 1762–1769. IEEE (2011)
Raguet, H., Fadili, J., Peyré, G.: A generalized forward–backward splitting. SIAM J. Imaging Sci. 6(3), 1199–1226 (2013)
Raguet, H.: A Signal Processing Approach to Voltage-Sensitive Dye Optical Imaging. Ph.D. thesis, Université Paris-Dauphine, Paris (2014)
Raguet, H., Landrieu, L.: Preconditioning of a generalized forward-backward splitting and application to optimization on graphs. SIAM J. Imaging Sci. 8(4), 2706–2739 (2015)
S**arn, J.E.: Partial inverse of a monotone operator. Appl. Math. Optim. 10(1), 247–265 (1983)
Vu, B.C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. 38(3), 667–681 (2013)
Weinmann, M., Jutzi, B., Hinz, S., Mallet, C.: Semantic point cloud interpretation based on optimal neighborhoods, relevant features and efficient classifiers. ISPRS 105, 286–304 (2015)
Zou, H., Hastie, T., Tibshirani, R.: On the “degrees of freedom” of the LASSO. Ann. Stat. 35(5), 2173–2192 (2007)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Raguet, H. A note on the forward-Douglas–Rachford splitting for monotone inclusion and convex optimization. Optim Lett 13, 717–740 (2019). https://doi.org/10.1007/s11590-018-1272-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-018-1272-8