American Institute of Mathematical Sciences

Advanced
August  2016, 10(3): 617-640. doi: 10.3934/ipi.2016014

Solving monotone inclusions involving parallel sums of linearly composed maximally monotone operators

Radu Ioan Boţ 1, and  Christopher Hendrich 2,

1. 

University of Vienna, Faculty of Mathematics, Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria
2. 

Chemnitz University of Technology, Department of Mathematics, D-09107 Chemnitz, Germany

Received  June 2014 Revised  April 2016 Published  August 2016

The aim of this article is to present two different primal-dual methods for solving structured monotone inclusions involving parallel sums of compositions of maximally monotone operators with linear bounded operators. By employing some elaborated splitting techniques, all of the operators occurring in the problem formulation are processed individually via forward or backward steps. The treatment of parallel sums of linearly composed maximally monotone operators is motivated by applications in imaging which involve first- and second-order total variation functionals, to which a special attention is given.
Keywords: primal-dual algorithm., infimal convolution, parallel sum, Convex optimization, Fenchel duality, monotone inclusion.
Mathematics Subject Classification: Primary: 90C25, 90C46; Secondary: 47A5.
Citation: Radu Ioan Boţ, Christopher Hendrich. Solving monotone inclusions involving parallel sums of linearly composed maximally monotone operators. Inverse Problems & Imaging, 2016, 10 (3) : 617-640. doi: 10.3934/ipi.2016014
References:
[1]

H. Attouch, L. M. Briceño-Arias and P. L. Combettes, A parallel splitting method for coupled monotone inclusions, SIAM J. Control Optim., 48 (2010), 3246-3270. doi: 10.1137/090754297.  Google Scholar

[2]

H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics, Springer, New York, 2011. doi: 10.1007/978-1-4419-9467-7.  Google Scholar

[3]

S. Becker and P. L. Combettes, An algorithm for splitting parallel sums of linearly composed monotone operators, with applications to signal recovery, J. Nonlinear Convex A., 15 (2014), 137-159.  Google Scholar

[4]

R. I. Boţ, Conjugate Duality in Convex Optimization, Lecture Notes in Economics and Mathematical Systems, Vol. 637, Springer, Berlin, 2010. doi: 10.1007/978-3-642-04900-2.  Google Scholar

[5]

R. I. Boţ, E. R. Csetnek and A. Heinrich, A primal-dual splitting algorithm for finding zeros of sums of maximally monotone operators, SIAM J. Optim., 23 (2013), 2011-2036. doi: 10.1137/12088255X.  Google Scholar

[6]

R. I. Boţ, E. R. Csetnek, A. Heinrich and C. Hendrich, On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems, Math. Program., 150 (2015), 251-279. doi: 10.1007/s10107-014-0766-0.  Google Scholar

[7]

R. I. Boţ, S. M. Grad and G. Wanka, Duality in Vector Optimization, Springer, Berlin, 2009. doi: 10.1007/978-3-642-02886-1.  Google Scholar

[8]

R. I. Boţ and C. Hendrich, A variable smoothing algorithm for solving convex optimization problems, TOP, 23 (2015), 124-150. doi: 10.1007/s11750-014-0326-z.  Google Scholar

[9]

R. I. Boţ and C. Hendrich, Convergence analysis for a primal-dual monotone + skew splitting algorithm with applications to total variation minimization, J. Math. Imaging Vis., 49 (2014), 551-568. doi: 10.1007/s10851-013-0486-8.  Google Scholar

[10]

R. I. Boţ and C. Hendrich, On the acceleration of the double smoothing technique for unconstrained convex optimization problems, Optimization, 64 (2015), 265-288. doi: 10.1080/02331934.2012.745530.  Google Scholar

[11]

R. I. Boţ and C. Hendrich, A double smoothing technique for solving unconstrained nondifferentiable convex optimization problems, Comput. Optim. Appl., 54 (2013), 239-262. doi: 10.1007/s10589-012-9523-6.  Google Scholar

[12]

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

[13]

L. M. Briceño-Arias and P. L. Combettes, A monotone + skew splitting model for composite monotone inclusions in duality, SIAM J. Optim., 21 (2011), 1230-1250. doi: 10.1137/10081602X.  Google Scholar

[14]

A. Chambolle and P.-L. Lions, Image recovery via total variation minimization and related problems, Numer. Math., 76 (1997), 167-188. doi: 10.1007/s002110050258.  Google Scholar

[15]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.  Google Scholar

[16]

P. L. Combettes, Quasi-Fejérian analysis of some optimization algorithms, In: D. Butnariu, Y. Censor and S. Reich (Eds.), Inherently Parallel Algorithms in Feasibility and Optimization and their Applications, Elsevier, New York, 8 (2001), 115-152. doi: 10.1016/S1570-579X(01)80010-0.  Google Scholar

[17]

P. L. Combettes, Solving monotone inclusions via compositions of nonexpansive averaged operators, Optimization, 53 (2004), 475-504. doi: 10.1080/02331930412331327157.  Google Scholar

[18]

P. L. Combettes, Iterative construction of the resolvent of a sum of maximal monotone operators, J. Convex Anal., 16 (2009), 727-748.  Google Scholar

[19]

P. L. Combettes, Systems of structured monotone inclusions: Duality, algorithms, and applications, SIAM J. Optim., 23 (2013), 2420-2447. doi: 10.1137/130904160.  Google Scholar

[20]

P. L. Combettes and J.-C. Pesquet, Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators, Set-Valued Var. Anal., 20 (2012), 307-330. doi: 10.1007/s11228-011-0191-y.  Google Scholar

[21]

L. Condat, A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl., 158 (2013), 460-479. doi: 10.1007/s10957-012-0245-9.  Google Scholar

[22]

J. Douglas and H. H. Rachford, On the numerical solution of the heat conduction problem in two and three space variables, Trans. of the Amer. Math. Soc., 82 (1956), 421-439. doi: 10.1090/S0002-9947-1956-0084194-4.  Google Scholar

[23]

J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318. doi: 10.1007/BF01581204.  Google Scholar

[24]

S. Harizanov, J.-C. Pesquet and G. Steidl, Epigraphical projection for solving least squares anscombe transformed constrained optimization problems, In: Scale Space and Variational Methods in Computer Vision, Springer, Berlin Heidelberg, 7893 (2013), 125-136. doi: 10.1007/978-3-642-38267-3_11.  Google Scholar

[25]

R. T. Rockafellar, On the maximal monotonicity of subdifferential mappings, Pacific J. Math., 33 (1970), 209-216. doi: 10.2140/pjm.1970.33.209.  Google Scholar

[26]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898. doi: 10.1137/0314056.  Google Scholar

[27]

S. Setzer, G. Steidl and T. Teuber, Infimal convolution regularizations with discrete $l_1$-type functionals, Commun. Math. Sci., 9 (2011), 797-827. doi: 10.4310/CMS.2011.v9.n3.a7.  Google Scholar

[28]

P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim., 38 (2000), 431-446. doi: 10.1137/S0363012998338806.  Google Scholar

[29]

B. C. Vũ, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comp. Math., 38 (2013), 667-681. doi: 10.1007/s10444-011-9254-8.  Google Scholar

[30]

C. Zălinescu, Convex Analysis in General Vector Spaces, World Scientific, Singapore, 2002. doi: 10.1142/9789812777096.  Google Scholar

show all references

References:
[1]

H. Attouch, L. M. Briceño-Arias and P. L. Combettes, A parallel splitting method for coupled monotone inclusions, SIAM J. Control Optim., 48 (2010), 3246-3270. doi: 10.1137/090754297.  Google Scholar

[2]

H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics, Springer, New York, 2011. doi: 10.1007/978-1-4419-9467-7.  Google Scholar

[3]

S. Becker and P. L. Combettes, An algorithm for splitting parallel sums of linearly composed monotone operators, with applications to signal recovery, J. Nonlinear Convex A., 15 (2014), 137-159.  Google Scholar

[4]

R. I. Boţ, Conjugate Duality in Convex Optimization, Lecture Notes in Economics and Mathematical Systems, Vol. 637, Springer, Berlin, 2010. doi: 10.1007/978-3-642-04900-2.  Google Scholar

[5]

R. I. Boţ, E. R. Csetnek and A. Heinrich, A primal-dual splitting algorithm for finding zeros of sums of maximally monotone operators, SIAM J. Optim., 23 (2013), 2011-2036. doi: 10.1137/12088255X.  Google Scholar

[6]

R. I. Boţ, E. R. Csetnek, A. Heinrich and C. Hendrich, On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems, Math. Program., 150 (2015), 251-279. doi: 10.1007/s10107-014-0766-0.  Google Scholar

[7]

R. I. Boţ, S. M. Grad and G. Wanka, Duality in Vector Optimization, Springer, Berlin, 2009. doi: 10.1007/978-3-642-02886-1.  Google Scholar

[8]

R. I. Boţ and C. Hendrich, A variable smoothing algorithm for solving convex optimization problems, TOP, 23 (2015), 124-150. doi: 10.1007/s11750-014-0326-z.  Google Scholar

[9]

R. I. Boţ and C. Hendrich, Convergence analysis for a primal-dual monotone + skew splitting algorithm with applications to total variation minimization, J. Math. Imaging Vis., 49 (2014), 551-568. doi: 10.1007/s10851-013-0486-8.  Google Scholar

[10]

R. I. Boţ and C. Hendrich, On the acceleration of the double smoothing technique for unconstrained convex optimization problems, Optimization, 64 (2015), 265-288. doi: 10.1080/02331934.2012.745530.  Google Scholar

[11]

R. I. Boţ and C. Hendrich, A double smoothing technique for solving unconstrained nondifferentiable convex optimization problems, Comput. Optim. Appl., 54 (2013), 239-262. doi: 10.1007/s10589-012-9523-6.  Google Scholar

[12]

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

[13]

L. M. Briceño-Arias and P. L. Combettes, A monotone + skew splitting model for composite monotone inclusions in duality, SIAM J. Optim., 21 (2011), 1230-1250. doi: 10.1137/10081602X.  Google Scholar

[14]

A. Chambolle and P.-L. Lions, Image recovery via total variation minimization and related problems, Numer. Math., 76 (1997), 167-188. doi: 10.1007/s002110050258.  Google Scholar

[15]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.  Google Scholar

[16]

P. L. Combettes, Quasi-Fejérian analysis of some optimization algorithms, In: D. Butnariu, Y. Censor and S. Reich (Eds.), Inherently Parallel Algorithms in Feasibility and Optimization and their Applications, Elsevier, New York, 8 (2001), 115-152. doi: 10.1016/S1570-579X(01)80010-0.  Google Scholar

[17]

P. L. Combettes, Solving monotone inclusions via compositions of nonexpansive averaged operators, Optimization, 53 (2004), 475-504. doi: 10.1080/02331930412331327157.  Google Scholar

[18]

P. L. Combettes, Iterative construction of the resolvent of a sum of maximal monotone operators, J. Convex Anal., 16 (2009), 727-748.  Google Scholar

[19]

P. L. Combettes, Systems of structured monotone inclusions: Duality, algorithms, and applications, SIAM J. Optim., 23 (2013), 2420-2447. doi: 10.1137/130904160.  Google Scholar

[20]

P. L. Combettes and J.-C. Pesquet, Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators, Set-Valued Var. Anal., 20 (2012), 307-330. doi: 10.1007/s11228-011-0191-y.  Google Scholar

[21]

L. Condat, A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl., 158 (2013), 460-479. doi: 10.1007/s10957-012-0245-9.  Google Scholar

[22]

J. Douglas and H. H. Rachford, On the numerical solution of the heat conduction problem in two and three space variables, Trans. of the Amer. Math. Soc., 82 (1956), 421-439. doi: 10.1090/S0002-9947-1956-0084194-4.  Google Scholar

[23]

J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318. doi: 10.1007/BF01581204.  Google Scholar

[24]

S. Harizanov, J.-C. Pesquet and G. Steidl, Epigraphical projection for solving least squares anscombe transformed constrained optimization problems, In: Scale Space and Variational Methods in Computer Vision, Springer, Berlin Heidelberg, 7893 (2013), 125-136. doi: 10.1007/978-3-642-38267-3_11.  Google Scholar

[25]

R. T. Rockafellar, On the maximal monotonicity of subdifferential mappings, Pacific J. Math., 33 (1970), 209-216. doi: 10.2140/pjm.1970.33.209.  Google Scholar

[26]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898. doi: 10.1137/0314056.  Google Scholar

[27]

S. Setzer, G. Steidl and T. Teuber, Infimal convolution regularizations with discrete $l_1$-type functionals, Commun. Math. Sci., 9 (2011), 797-827. doi: 10.4310/CMS.2011.v9.n3.a7.  Google Scholar

[28]

P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim., 38 (2000), 431-446. doi: 10.1137/S0363012998338806.  Google Scholar

[29]

B. C. Vũ, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comp. Math., 38 (2013), 667-681. doi: 10.1007/s10444-011-9254-8.  Google Scholar

[30]

C. Zălinescu, Convex Analysis in General Vector Spaces, World Scientific, Singapore, 2002. doi: 10.1142/9789812777096.  Google Scholar

[1]

Yixuan Yang, Yuchao Tang, Meng Wen, Tieyong Zeng. Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications. Inverse Problems & Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014
[2]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
[3]

Elimhan N. Mahmudov. Infimal convolution and duality in convex optimal control problems with second order evolution differential inclusions. Evolution Equations & Control Theory, 2021, 10 (1) : 37-59. doi: 10.3934/eect.2020051
[4]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509
[5]

Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021134
[6]

Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031
[7]

Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073
[8]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[9]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[10]

Yuying Zhou, Gang Li. The Toland-Fenchel-Lagrange duality of DC programs for composite convex functions. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 9-23. doi: 10.3934/naco.2014.4.9
[11]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[12]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91
[13]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[14]

Anulekha Dhara, Aparna Mehra. Conjugate duality for generalized convex optimization problems. Journal of Industrial & Management Optimization, 2007, 3 (3) : 415-427. doi: 10.3934/jimo.2007.3.415
[15]

Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023
[16]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077
[17]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134
[18]

Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053
[19]

Yongjian Liu, Zhenhai Liu, Dumitru Motreanu. Differential inclusion problems with convolution and discontinuous nonlinearities. Evolution Equations & Control Theory, 2020, 9 (4) : 1057-1071. doi: 10.3934/eect.2020056
[20]

Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021028

2020 Impact Factor: 1.639

Tools

Metrics

  • PDF downloads (184)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences