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. 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, (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. Google Scholar

[4]

R. I. Boţ, Conjugate Duality in Convex Optimization,, Lecture Notes in Economics and Mathematical Systems, (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. 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. doi: 10.1007/s10107-014-0766-0. Google Scholar

[7]

R. I. Boţ, S. M. Grad and G. Wanka, Duality in Vector Optimization,, Springer, (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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1007/s10851-010-0251-1. Google Scholar

[16]

P. L. Combettes, Quasi-Fejérian analysis of some optimization algorithms,, In: D. Butnariu, 8 (2001), 115. 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. 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. Google Scholar

[19]

P. L. Combettes, Systems of structured monotone inclusions: Duality, algorithms, and applications,, SIAM J. Optim., 23 (2013), 2420. 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. 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. 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. 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. 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, 7893 (2013), 125. 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. 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. 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. 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. 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. doi: 10.1007/s10444-011-9254-8. Google Scholar

[30]

C. Zălinescu, Convex Analysis in General Vector Spaces,, World Scientific, (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. 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, (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. Google Scholar

[4]

R. I. Boţ, Conjugate Duality in Convex Optimization,, Lecture Notes in Economics and Mathematical Systems, (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. 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. doi: 10.1007/s10107-014-0766-0. Google Scholar

[7]

R. I. Boţ, S. M. Grad and G. Wanka, Duality in Vector Optimization,, Springer, (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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1007/s10851-010-0251-1. Google Scholar

[16]

P. L. Combettes, Quasi-Fejérian analysis of some optimization algorithms,, In: D. Butnariu, 8 (2001), 115. 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. 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. Google Scholar

[19]

P. L. Combettes, Systems of structured monotone inclusions: Duality, algorithms, and applications,, SIAM J. Optim., 23 (2013), 2420. 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. 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. 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. 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. 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, 7893 (2013), 125. 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. 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. 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. 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. 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. doi: 10.1007/s10444-011-9254-8. Google Scholar

[30]

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

[1]

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
[2]

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
[3]

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
[4]

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
[5]

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
[6]

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

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
[8]

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
[9]

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, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190
[10]

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
[11]

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
[12]

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
[13]

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
[14]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243
[15]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129
[16]

Ram U. Verma. On the generalized proximal point algorithm with applications to inclusion problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 381-390. doi: 10.3934/jimo.2009.5.381
[17]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[18]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[19]

Gang Li, Lipu Zhang, Zhe Liu. The stable duality of DC programs for composite convex functions. Journal of Industrial & Management Optimization, 2017, 13 (1) : 63-79. doi: 10.3934/jimo.2016004
[20]

Murat Adivar, Shu-Cherng Fang. Convex optimization on mixed domains. Journal of Industrial & Management Optimization, 2012, 8 (1) : 189-227. doi: 10.3934/jimo.2012.8.189

2018 Impact Factor: 1.469

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences