×

zbMATH — the first resource for mathematics

On the ergodic convergence rates of a first-order primal-dual algorithm. (English) Zbl 1350.49035
This paper displays refined ergodic convergence rates for a first-order primal-dual algorithm applied to composite convex-concave saddle-point problems. These new convergence rates are expressed in terms of the primal-dual gap function for accelerated variants of the algorithm. Several computational examples illustrate the performances of the proposed algorithms.

MSC:
49M29 Numerical methods involving duality
65K10 Numerical optimization and variational techniques
90C25 Convex programming
65Y20 Complexity and performance of numerical algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alvarez, F., Attouch, H.: An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping. Set-Valued Anal. 9(1-2), 3-11 (2001) · Zbl 0991.65056
[2] Beck, A; Teboulle, M, Mirror descent and nonlinear projected subgradient methods for convex optimization, Oper. Res. Lett., 31, 167-175, (2003) · Zbl 1046.90057
[3] Beck, A; Teboulle, M, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202, (2009) · Zbl 1175.94009
[4] Boţ, RI; Csetnek, ER; Heinrich, A; Hendrich, C, On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems, Math. Program., 150, 251-279, (2015) · Zbl 1312.47081
[5] Chambolle, A; Pock, T, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40, 120-145, (2011) · Zbl 1255.68217
[6] Chen, G; Teboulle, M, Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM J. Optim., 3, 538-543, (1993) · Zbl 0808.90103
[7] Chen, Yunmei; Lan, Guanghui; Ouyang, Yuyuan, Optimal primal-dual methods for a class of saddle point problems, SIAM J. Optim., 24, 1779-1814, (2014) · Zbl 1329.90090
[8] Combettes, P.L., Condat, L., Pesquet, J.-C., Vũ, B.C.: A forward-backward view of some primal-dual optimization methods in image recovery. In: Proceedings ICIP 2014 Conference, Paris, Oct. 2014 (2014) (to appear) · Zbl 0765.90073
[9] Condat, L, A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl., 158, 460-479, (2013) · Zbl 1272.90110
[10] Davis, D., Yin, W.: A three-operator splitting scheme and its optimization applications. Technical report, CAM Report 15-13/preprint arXiv:1504.01032 (2015) · Zbl 1206.90117
[11] Drori, Y; Sabach, S; Teboulle, M, A simple algorithm for a class of nonsmooth convex-concave saddle-point problems, Oper. Res. Lett., 43, 209-214, (2015) · Zbl 1408.90234
[12] Duchi, J., Shalev-Shwartz, S., Singer, Y., Chandra, T.: Efficient projections onto the \(ℓ _1\)-ball for learning in high dimensions. In: Proceedings of the 25th international conference on machine learning, ICML ’08, pages 272-279, New York (2008). ACM · Zbl 1272.90110
[13] Eckstein, J, Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming, Math. Oper. Res., 18, 202-226, (1993) · Zbl 0807.47036
[14] Eckstein, J; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318, (1992) · Zbl 0765.90073
[15] Esser, E; Zhang, X; Chan, TF, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci., 3, 1015-1046, (2010) · Zbl 1206.90117
[16] He, B; Yuan, X, Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective, SIAM J. Imaging Sci., 5, 119-149, (2012) · Zbl 1250.90066
[17] He, B; Yuan, X, On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Anal., 50, 700-709, (2012) · Zbl 1245.90084
[18] Hohage, T., Homann, C.: A generalization of the Chambolle-Pock algorithm to Banach spaces with applications to inverse problems. Technical report, arXiv:1412.0126 (2014) · Zbl 0808.90103
[19] Lorenz, DA; Pock, T, An inertial forward-backward algorithm for monotone inclusions, J. Math. Imaging Vis., 51, 311-325, (2015) · Zbl 1327.47063
[20] Nemirovski, AS, Prox-method with rate of convergence \(O(1/t)\) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optim., 15, 229-251, (2004) · Zbl 1106.90059
[21] Nemirovski, A.S., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983). Translated from the Russian and with a preface by E.R. Dawson, Wiley-Interscience Series in Discrete Mathematics
[22] Nesterov, Y.: Introductory Lectures on Convex Optimization. Applied Optimization, vol. 87. Kluwer Academic Publishers, Boston (2004). A basic course · Zbl 1086.90045
[23] Nesterov, Y, Smooth minimization of non-smooth functions, Math. Program., 103, 127-152, (2005) · Zbl 1079.90102
[24] Opial, Z, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Am. Math. Soc., 73, 591-597, (1967) · Zbl 0179.19902
[25] Pesquet, J.-C., Repetti, A.: A class of randomized primal-dual algorithms for distributed optimization. arXiv:1406.6404 (2014) · Zbl 1336.65113
[26] Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the Mumford-Shah functional. In: ICCV Proceedings, LNCS. Springer (2009)
[27] Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898, (1976) · Zbl 0358.90053
[28] Shefi, R; Teboulle, M, Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optim., 24, 269-297, (2014) · Zbl 1291.90176
[29] Teboulle, M, Entropic proximal mappings with applications to nonlinear programming, Math. Oper. Res., 17, 670-690, (1992) · Zbl 0766.90071
[30] Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization (2008). SIAM J. Optim. http://www.csie.ntu.edu.tw/ b97058/tseng/papers/apgm. (submitted) · Zbl 1245.90084
[31] Vũ, BC, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comput. Math., 38, 667-681, (2013) · Zbl 1284.47045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.