×

Non-stationary first-order primal-dual algorithms with faster convergence rates. (English) Zbl 1451.90126

Summary: In this paper, we propose two novel non-stationary first-order primal-dual algorithms to solve non-smooth composite convex optimization problems. Unlike existing primal-dual schemes where the parameters are often fixed, our methods use predefined and dynamic sequences for parameters. We prove that our first algorithm can achieve an \(\mathcal{O}\left(1/k\right)\) convergence rate on the primal-dual gap, and primal and dual objective residuals, where \(k\) is the iteration counter. Our rate is on the non-ergodic (i.e., the last iterate) sequence of the primal problem and on the ergodic (i.e., the averaging) sequence of the dual problem, which we call the semi-ergodic rate. By modifying the step-size update rule, this rate can be boosted even faster on the primal objective residual. When the problem is strongly convex, we develop a second primal-dual algorithm that exhibits an \(\mathcal{O}\left(1/k^2\right)\) convergence rate on the same three types of guarantees. Again by modifying the step-size update rule, this rate becomes faster on the primal objective residual. Our primal-dual algorithms are the first ones to achieve such fast convergence rate guarantees under mild assumptions compared to existing works, to the best of our knowledge. As byproducts, we apply our algorithms to solve constrained convex optimization problems and prove the same convergence rates on both the objective residuals and the feasibility violation. We still obtain at least \(\mathcal{O}\left(1/k^2\right)\) rates even when the problem is “semi-strongly” convex. We verify our theoretical results via two well-known numerical examples.

MSC:

90C25 Convex programming
90C06 Large-scale problems in mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Software:

Mosek; UNLocBoX
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] H. Attouch and J. Peypouquet, The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than \(1/k^2\), SIAM J. Optim., 26 (2016), pp. 1824-1834, https://doi.org/10.1137/15M1046095. · Zbl 1346.49048
[2] H. H. Bauschke and P. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., Springer-Verlag, Cham, 2017. · Zbl 1359.26003
[3] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183-202, https://doi.org/10.1137/080716542. · Zbl 1175.94009
[4] R. 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), pp. 2011-2036, https://doi.org/10.1137/12088255X. · Zbl 1314.47102
[5] R. Boţ, E. 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), pp. 251-279. · Zbl 1312.47081
[6] 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), pp. 551-568. · Zbl 1302.65142
[7] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2011), pp. 1-122. · Zbl 1229.90122
[8] L. M. Bricen͂o-Arias and P. L. Combettes, A monotone + skew splitting model for composite monotone inclusions in duality, SIAM J. Optim., 21 (2011), pp. 1230-1250, https://doi.org/10.1137/10081602X. · Zbl 1239.47053
[9] A. Chambolle, M. J. Ehrhardt, P. Richtárik, and C.-B. Schönlieb, Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications, SIAM J. Optim., 28 (2018), pp. 2783-2808, https://doi.org/10.1137/17M1134834. · Zbl 06951767
[10] A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40 (2011), pp. 120-145. · Zbl 1255.68217
[11] A. Chambolle and T. Pock, An introduction to continuous optimization for imaging, Acta Numer., 25 (2016), pp. 161-319. · Zbl 1343.65064
[12] A. Chambolle and T. Pock, On the ergodic convergence rates of a first-order primal-dual algorithm, Math. Program., 159 (2016), pp. 253-287. · Zbl 1350.49035
[13] P. Chen, J. Huang, and X. Zhang, A primal-dual fixed point algorithm for minimization of the sum of three convex separable functions, Fixed Point Theory Appl., 2016 (2016), 54. · Zbl 1505.90094
[14] Y. Chen, G. Lan, and Y. Ouyang, Optimal primal-dual methods for a class of saddle-point problems, SIAM J. Optim., 24 (2014), pp. 1779-1814, https://doi.org/10.1137/130919362. · Zbl 1329.90090
[15] P. L. Combettes and J.-C. Pesquet, Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, New York, 2011, pp. 185-212. · Zbl 1242.90160
[16] P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4 (2005), pp. 1168-1200, https://doi.org/10.1137/050626090. · Zbl 1179.94031
[17] 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), pp. 307-330. · Zbl 1284.47043
[18] L. Condat, A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl., 158 (2013), pp. 460-479. · Zbl 1272.90110
[19] D. Davis, Convergence rate analysis of primal-dual splitting schemes, SIAM J. Optim., 25 (2015), pp. 1912-1943, https://doi.org/10.1137/151003076. · Zbl 1323.47069
[20] D. Davis, Convergence rate analysis of the forward-Douglas-Rachford splitting scheme, SIAM J. Optim., 25 (2015), pp. 1760-1786, https://doi.org/10.1137/140992291. · Zbl 1325.65081
[21] D. Davis and W. Yin, Convergence rate analysis of several splitting schemes, in Splitting Methods in Communication, Imaging, Science, and Engineering, R. Glowinski, S. J. Osher, and W. Yin, eds., Springer, New York, 2016, pp. 115-163. · Zbl 1372.65168
[22] D. Davis and W. Yin, Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions, Math. Oper. Res., 42 (2017), pp. 577-896. · Zbl 1379.65035
[23] D. Davis and W. Yin, A three-operator splitting scheme and its optimization applications, Set-Valued Var. Anal., 25 (2017), pp. 829-858. · Zbl 1464.47041
[24] C. Dünner, S. Forte, M. Takáč, and M. Jaggi, Primal-dual rates and certificates, in Proceedings of the 33rd International Conference on Machine Learning (ICML), New York, NY, 2016, pp. 783-792.
[25] J. Eckstein and D. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), pp. 293-318. · Zbl 0765.90073
[26] E. Esser, X. Zhang, and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci., 3 (2010), pp. 1015-1046, https://doi.org/10.1137/09076934X. · Zbl 1206.90117
[27] J. E. Esser, Primal-dual algorithm for convex models and applications to image restoration, registration and nonlocal inpainting, Ph.D. thesis, University of California, Los Angeles, Los Angeles, CA, 2010.
[28] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. 1-2, Springer-Verlag, New York, 2003. · Zbl 1062.90001
[29] R. Glowinski, S. Osher, and W. Yin, Splitting Methods in Communication, Imaging, Science, and Engineering, Springer, New York, 2017. · Zbl 1362.65002
[30] T. Goldstein, M. Li, and X. Yuan, Adaptive primal-dual splitting methods for statistical learning and image processing, in Advances in Neural Information Processing Systems (Montreal, Canada, 2015), NeurIPS, San Diego, CA, 2015, pp. 2080-2088.
[31] T. Goldstein, B. O’Donoghue, S. Setzer, and R. Baraniuk, Fast alternating direction optimization methods, SIAM J. Imaging Sci., 7 (2014), pp. 1588-1623, https://doi.org/10.1137/120896219. · Zbl 1314.49019
[32] E. Y. Hamedani and N. S. Aybat, A Primal-Dual Algorithm for General Convex-Concave Saddle Point Problems, preprint, https://arxiv.org/abs/1803.01401, 2018.
[33] B. He and X. Yuan, Convergence analysis of primal-dual algorithms for saddle-point problem: From contraction perspective, SIAM J. Imaging Sci., 5 (2012), pp. 119-149, https://doi.org/10.1137/100814494. · Zbl 1250.90066
[34] Y. He and R. D. C. Monteiro, An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems, SIAM J. Optim., 26 (2016), pp. 29-56, https://doi.org/10.1137/14096757X. · Zbl 1329.90179
[35] L. T. K. Hien, R. Zhao, and W. B. Haskell, An Inexact Primal-Dual Smoothing Framework for Large-Scale Non-Bilinear Saddle Point Problems, preprint, https://arxiv.org/abs/1711.03669, 2017.
[36] H. Li and Z. Lin, Accelerated alternating direction method of multipliers: An optimal \(\mathcal{O}(1/k)\) nonergodic analysis, J. Sci. Comput., 79 (2019), pp. 671-699. · Zbl 1419.90085
[37] J. Liang, J. Fadili, and G. Peyré, Local convergence properties of Douglas-Rachford and alternating direction method of multipliers, J. Optim. Theory Appl., 172 (2017), pp. 874-913. · Zbl 1362.65065
[38] P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), pp. 964-979, https://doi.org/10.1137/0716071. · Zbl 0426.65050
[39] Y. Malitsky and T. Pock, A first-order primal-dual algorithm with linesearch, SIAM J. Optim., 28 (2018), pp. 411-432, https://doi.org/10.1137/16M1092015. · Zbl 1390.49033
[40] R. D. C. Monteiro and B. F. Svaiter, On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean, SIAM J. Optim., 20 (2010), pp. 2755-2787, https://doi.org/10.1137/090753127. · Zbl 1230.90200
[41] R. D. C. Monteiro and B. F. Svaiter, Complexity of variants of Tseng’s modified F-B splitting and Korpelevich’s methods for hemivariational inequalities with applications to saddle-point and convex optimization problems, SIAM J. Optim., 21 (2011), pp. 1688-1720, https://doi.org/10.1137/100801652. · Zbl 1245.90155
[42] R. D. C. Monteiro and B. F. Svaiter, Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers, SIAM J. Optim., 23 (2013), pp. 475-507, https://doi.org/10.1137/110849468. · Zbl 1267.90181
[43] MOSEK-ApS, The MOSEK Optimization Toolbox for MATLAB Manual, Version \textup9.0, 2019, http://docs.mosek.com/9.0/toolbox/index.html.
[44] I. Necoara and A. Patrascu, Iteration complexity analysis of dual first-order methods for conic convex programming, Optim. Methods Softw., 31 (2016), pp. 645-678. · Zbl 1342.90135
[45] I. Necoara, A. Patrascu, and F. Glineur, Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming, Optim. Methods Softw., 34 (2019), pp. 305-335. · Zbl 1407.90256
[46] A. Nemirovski, Prox-method with rate of convergence \(\mathcal{O}(1/t)\) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optim, 15 (2004), pp. 229-251, https://doi.org/10.1137/S1052623403425629. · Zbl 1106.90059
[47] Y. Nesterov, A method for unconstrained convex minimization problem with the rate of convergence \(\mathcal{O}(1/k^2)\), Dokl. Akad. Nauk. USSR, 269 (1983), pp. 543-547.
[48] Y. Nesterov, Excessive gap technique in nonsmooth convex minimization, SIAM J. Optim., 16 (2005), pp. 235-249, https://doi.org/10.1137/S1052623403422285. · Zbl 1096.90026
[49] Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program., 103 (2005), pp. 127-152. · Zbl 1079.90102
[50] D. O’Connor and L. Vandenberghe, Primal-dual decomposition by operator splitting and applications to image deblurring, SIAM J. Imaging Sci., 7 (2014), pp. 1724-1754, https://doi.org/10.1137/13094671X. · Zbl 1309.65069
[51] D. O’Connor and L. Vandenberghe, On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting, Math. Program., 179 (2020), pp. 85-108. · Zbl 1498.90156
[52] Y. Ouyang, Y. Chen, G. Lan, and E. Pasiliao, Jr., An accelerated linearized alternating direction method of multipliers, SIAM J. Imaging Sci., 8 (2015), pp. 644-681, https://doi.org/10.1137/14095697X. · Zbl 1321.90105
[53] T. Pock, D. Cremers, H. Bischof, and A. Chambolle, An algorithm for minimizing the Mumford-Shah functional, in Proceedings of the 12th IEEE International Conference on Computer Vision, IEEE, Washington, DC, 2009, pp. 1133-1140.
[54] J. E. Spingarn, Partial inverse of a monotone operator, Appl. Math. Optim., 10 (1983), pp. 247-265. · Zbl 0524.90072
[55] Q. Tran-Dinh, Proximal alternating penalty algorithms for constrained convex optimization, Comput. Optim. Appl., 72 (2019), pp. 1-43. · Zbl 1418.90199
[56] Q. Tran-Dinh, A. Alacaoglu, O. Fercoq, and V. Cevher, An adaptive primal-dual framework for nonsmooth convex minimization, Math. Program. Comput. 12 (2020), pp. 451-491. · Zbl 1452.90246
[57] Q. Tran-Dinh, O. Fercoq, and V. Cevher, A smooth primal-dual optimization framework for nonsmooth composite convex minimization, SIAM J. Optim., 28 (2018), pp. 96-134, https://doi.org/10.1137/16M1093094. · Zbl 1386.90109
[58] Q. Tran-Dinh, C. Savorgnan, and M. Diehl, Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems, Compt. Optim. Appl., 55 (2013), pp. 75-111. · Zbl 1295.90048
[59] P. Tseng, Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming, Math. Program., 48 (1990), pp. 249-263. · Zbl 0725.90079
[60] P. Tseng, On accelerated proximal gradient methods for convex-concave optimization, SIAM J. Optim., submitted (2008).
[61] T. Valkonen, Inertial, corrected, primal-dual proximal splitting, SIAM J. Optim., 30 (2020), pp. 1391-1420. · Zbl 1484.65138
[62] C. B. Vu, A splitting algorithm for dual monotone inclusions involving co-coercive operators, Adv. Comput. Math., 38 (2013), pp. 667-681. · Zbl 1284.47045
[63] B. E. Woodworth and N. Srebro, Tight complexity bounds for optimizing composite objectives, in Advances in Neural Information Processing Systems (NIPS) (Barcelona, Spain, 2016), NeurIPS, San Diego, CA, 2016, pp. 3639-3647.
[64] Y. Xu, Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming, SIAM J. Optim., 27 (2017), pp. 1459-1484, https://doi.org/10.1137/16M1082305. · Zbl 1373.90111
[65] M. Yan, A new primal-dual algorithm for minimizing the sum of three functions with a linear operator, J. Sci. Comput., 76 (2018), pp. 1698-1717. · Zbl 1415.65142
[66] W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for \(\ell_{\textup{1}} \)-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), pp. 143-168, https://doi.org/10.1137/070703983. · Zbl 1203.90153
[67] X. Zhang, M. Burger, and S. Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46 (2011), pp. 20-46. · Zbl 1227.65052
[68] M. Zhu and T. Chan, An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration, UCLA CAM Technical Report 08-34, UCLA, Los Angeles, CA, 2008.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.