Abstract
We present two modified versions of the primal-dual splitting algorithm relying on forward–backward splitting proposed in V\(\tilde{\mathrm{u}}\) (Adv Comput Math 38(3):667–681, 2013) for solving monotone inclusion problems. Under strong monotonicity assumptions for some of the operators involved we obtain for the sequences of iterates that approach the solution orders of convergence of \(\mathcal{{O}}(\frac{1}{n})\) and \(\mathcal{{O}}(\omega ^n)\), for \(\omega \in (0,1)\), respectively. The investigated primal-dual algorithms are fully decomposable, in the sense that the operators are processed individually at each iteration. We also discuss the modified algorithms in the context of convex optimization problems and present numerical experiments in image processing and pattern recognition in cluster analysis.
Similar content being viewed by others
References
Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics. Springer, New York (2011)
Beck, A., Teboulle, M.: A fast iterative shrinkage-tresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202 (2009)
Borwein, J.M., Vanderwerff, J.D.: Convex Functions: Constructions, Characterizations and Counterexamples. Cambridge University Press, Cambridge (2010)
Boţ, R.I.: Conjugate Duality in Convex Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 637. Springer, Berlin (2010)
Boţ, R.I., Csetnek, E.R.: Regularity conditions via generalized interiority notions in convex optimization: new achievements and their relation to some classical statements. Optimization 61(1), 35–65 (2012)
Boţ, R.I., Csetnek, E.R., Heinrich, A.: A primal-dual splitting algorithm for fnding zeros of sums of maximally monotone operators. SIAM J. Optimiz. 23(4), 2011–2036 (2013)
Boţ, R.I., Hendrich, C.: Convergence analysis for a primal-dual monotone + skew splitting algorithm with applications to total variation minimization. J. Math. Imaging Vis. doi:10.1007/s10851-013-0486-8
Boţ, R.I., Hendrich, C.: A Douglas-Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators. SIAM J. Optimiz. 23(4), 2541–2565 (2013)
Briceño-Arias, L.M., Combettes, P.L.: A monotone + skew splitting model for composite monotone inclusions in duality. SIAM J. Optimiz. 21(4), 1230–1250 (2011)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1–2), 89–97 (2004)
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)
Chi, E.C., Lange, K.: Splitting methods for convex clustering. arXiv:1304.0499 [stat.ML] (2013)
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 type 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)
Douglas, J., Rachford, H.H.: On the numerical solution of the heat conduction problem in \(2\) and \(3\) space variables. Trans. Am. Math. Soc. 82, 421–439 (1956)
Ekeland, I., Temam, R.: Convex Analysis and Variational Problems. North-Holland, Amsterdam (1976)
Hocking, T., Vert, J., Bach, F., Joulin, A.: Clusterpath: an algorithm for clustering using convex fusion penalties. In: Proceedings of the 28th International Conference on Machine Learning. Bellevue (2011)
Lindsten, F., Ohlsson, H., Ljung, L.: Just relax and come clustering! A convexication of k-means clustering, Technical report from Automatic Control, Linköpings Universitet, Report no.: LiTH-ISY-R-2992, (2011)
Nesterov, Y.: A method for unconstrained convex minimization problem with the rate of convergence \(O(1/k^2)\). Doklady AN SSSR (translated as Soviet Math. Docl.) 269, 543–547 (1983)
Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Prog. 103(1), 127–152 (2005)
Rockafellar, R.T.: On the maximal monotonicity of subdifferential mappings. Pac. J. Math. 33(1), 209–216 (1970)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optimiz. 14(5), 877–898 (1976)
Simons, S.: From Hahn-Banach to Monotonicity. Springer, Berlin (2008)
Tseng, P.: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control Optimiz. 29(1), 119–138 (1991)
Tseng, P.: A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optimiz. 38(2), 431–446 (2000)
Vũ, B.C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. 38(3), 667–681 (2013)
Zălinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, Singapore (2002)
Zhu, M., Chan, T.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration, Cam Reports 08–34 UCLA, Center for Applied Mathematics (2008)
Acknowledgments
The authors are grateful to anonymous reviewers for remarks and suggestions which improved the quality of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Radu Ioan Boţ: Research partially supported by DFG (German Research Foundation), project BO 2516/4-1.
Ernö Robert Csetnek: Research supported by DFG (German Research Foundation), project BO 2516/4-1.
André Heinrich: Research supported by the European Union, the European Social Fund (ESF) and prudsys AG in Chemnitz.
Christopher Hendrich: Research supported by a Graduate Fellowship of the Free State Saxony, Germany.
Rights and permissions
About this article
Cite this article
Boţ, R.I., Csetnek, E.R., Heinrich, A. et al. On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems. Math. Program. 150, 251–279 (2015). https://doi.org/10.1007/s10107-014-0766-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-014-0766-0
Keywords
- Maximally monotone operator
- Strongly monotone operator
- Resolvent
- Operator splitting
- Subdifferential
- Strongly convex function
- Convex optimization algorithm
- Duality