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 and 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[17]

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

[18]

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

[19]

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

[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.

[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.

[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.

[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.

[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.

[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.

[26]

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

[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.

[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.

[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.

[30]

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

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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[17]

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

[18]

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

[19]

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

[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.

[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.

[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.

[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.

[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.

[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.

[26]

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

[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.

[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.

[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.

[30]

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

[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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[14]

Xiayang Zhang, Yuqian Kong, Shanshan Liu, Yuan Shen. A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022008
[15]

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

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

Lican Kang, Yuan Luo, Jerry Zhijian Yang, Chang Zhu. A primal and dual active set algorithm for truncated $L_1$ regularized logistic regression. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022050
[18]

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

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

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 and Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053

2020 Impact Factor: 1.639

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy