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

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

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

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

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

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

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

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

[7]

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

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

[17]

P. L. Combettes, Solving monotone inclusions via compositions of nonexpansive averaged operators,, Optimization, 53 (2004), 475. 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.

[19]

P. L. Combettes, Systems of structured monotone inclusions: Duality, algorithms, and applications,, SIAM J. Optim., 23 (2013), 2420. 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. 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. 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. 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. 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, 7893 (2013), 125. 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. 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. 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. 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. doi: 10.1137/S0363012998338806.

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

[30]

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

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

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

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

[7]

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

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

[17]

P. L. Combettes, Solving monotone inclusions via compositions of nonexpansive averaged operators,, Optimization, 53 (2004), 475. 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.

[19]

P. L. Combettes, Systems of structured monotone inclusions: Duality, algorithms, and applications,, SIAM J. Optim., 23 (2013), 2420. 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. 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. 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. 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. 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, 7893 (2013), 125. 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. 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. 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. 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. doi: 10.1137/S0363012998338806.

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

[30]

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

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

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018134

[13]

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

[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

2017 Impact Factor: 1.465

Metrics

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

Other articles
by authors

[Back to Top]