Article Contents
Article Contents

# On the linear convergence of the general first order primal-dual algorithm

The research of the first author was supported by National Natural Science Foundation of China (NSFC) at Grant No. 11901294 and Natural Science Foundation of Jiangsu Province at Grant No. BK20190429. The research of the second author was supported by National Natural Science Foundation of China (NSFC) at Grants No. 11625105 and No. 11926358

• In this paper, we consider the general first order primal-dual algorithm, which covers several recent popular algorithms such as the one proposed in [Chambolle, A. and Pock T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40 (2011) 120-145] as a special case. Under suitable conditions, we prove its global convergence and analyze its linear rate of convergence. As compared to the results in the literature, we derive the corresponding results for the general case and under weaker conditions. Furthermore, the global linear rate of the linearized primal-dual algorithm is established in the same analytical framework.

Mathematics Subject Classification: Primary: 90C47, 90C33; Secondary: 65K05.

 Citation:

• Figure 1.  From left to right: the original images, the degraded images and the restored images by Algorithm 1

Figure 2.  Evolution of SNRs, and Relative error (Rer) defined by (22) with respect to iterations. Left: for House. Right: for Lena

Figure 3.  Sensitivity analysis on parameters $\tau$ of Algorithm 1 for matrix correlation problems

Table 1.  Parameters Setting

 Parameters Values $(1/r,1/s,\tau)$ $(0.05, 3, -0.2)$ $(1/r,1/s,\tau)$ $(0.01, 15, 0)$ $(1/r,1/s,\tau)$ $(0.012, 12.5, 0.4)$ $(1/r,1/s,\tau)$ $(0.012, 12.5, 0.8)$ $(1/r,1/s,\tau)$ $(0.01, 12.5, 1)$ $(1/r,1/s,\tau)$ $(0.012, 12.5, 1.2)$
•  [1] K. Arrow, L. Hurwicz and H. Uzawa, Studies in linear and non-linear programming, in Stanford Mathematical Studies in the Social Sciences, II, Vol. 2, Stanford University Press, Stanford, Calif., 1958. [2] X. Cai, D. Han and L. Xu, An improved first-order primal-dual algorithm with a new correction step, J. Global Optim., 57 (2013), 1419-1428.  doi: 10.1007/s10898-012-9999-8. [3] 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-145.  doi: 10.1007/s10851-010-0251-1. [4] A. Chambolle and T. Pock, On the ergodic convergence rates of a first-order primal-dual algorithm, Math. Program. Ser. A, 159 (2016), 253-287.  doi: 10.1007/s10107-015-0957-3. [5] Y. Chen, G. Lan and Y. Ouyang, Optimal primal-dual methods for a class of saddle point problems, SIAM J. Optim., 24 (2014), 1779-1814.  doi: 10.1137/130919362. [6] E. Esser, X. Zhang and T. 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), 1015-1046.  doi: 10.1137/09076934X. [7] Y. Gao and D. Sun, Calibrating least squares semidefinite programming with equality and inequality constraints, SIAM J. Matrix Anal. Appl., 31 (2009), 1432-1457.  doi: 10.1137/080727075. [8] G. Gu, B. He and X. Yuan, Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: A unified approach, Comput. Optim. Appl., 59 (2014), 135-161.  doi: 10.1007/s10589-013-9616-x. [9] D. Han, D. Sun and L. Zhang, Linear rate convergence of the alternating direction method of multipliers for convex composite programming, Math. Oper. Res., 43 (2018), 622-637.  doi: 10.1287/moor.2017.0875. [10] D. Han, W. Xu and H. Yang, An operator splitting method for variational inequalities with partially unknown mappings, Numer. Math., 111 (2008), 207-237.  doi: 10.1007/s00211-008-0181-7. [11] D. Han and X. Yuan, Local linear convergence of the alternating direction method of multipliers for quadratic programs, SIAM J. Numer. Anal., 51 (2013), 3446-3457.  doi: 10.1137/120886753. [12] B. He, F. Ma and X. Yuan, An algorithmic framework of generalized primal-dual hybrid gradient methods for saddle point problems, J. Math. Imaging Vision, 58 (2017), 279-293.  doi: 10.1007/s10851-017-0709-5. [13] B. He, Y. You and X. Yuan, On the convergence of primal-dual hybrid gradient algorithm, SIAM J. Imaging Sci., 7 (2014), 2526-2537.  doi: 10.1137/140963467. [14] B. He and X. Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective, SIAM J. Imaging Sci., 5 (2012), 119-149.  doi: 10.1137/100814494. [15] B. He, M. Xu and X. Yuan, Solving large-scale least squares semidefinite programming by alternating direction methods, SIAM J. Matrix Anal. Appl., 32 (2011), 136-152.  doi: 10.1137/090768813. [16] H. He, J. Desai and K. Wang, A primal-dual prediction-correction algorithm for saddle point optimization, J. Global Optim., 66 (2016), 573-583.  doi: 10.1007/s10898-016-0437-1. [17] F. Jiang, X. Cai, Z. Wu and D. Han, Approximate first-order primal-dual algorithms for saddle point problems, Math. Comput., 90 (2021), 1227-1262.  doi: 10.1090/mcom/3610. [18] Y. Malitsky and T. Pock, A first-order primal-dual algorithm with linesearch, SIAM J. Optim., 28 (2018), 411-432.  doi: 10.1137/16M1092015. [19] A. Nemirovski, Prox-method with rate of convergence ${O}(1/t)$ for variational inequalities with Lipschitz continuous monotone operator and smooth convex-concave saddle point problems, SIAM J. Optim., 15 (2004), 229-251.  doi: 10.1137/S1052623403425629. [20] Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Applied Optimization, Kluwer Academic Publishers, Boston, MA, 2004. doi: 10.1007/978-1-4419-8853-9. [21] J. Rasch and A. Chambolle, Inexact first-order primal-dual algorithms, Comput. Optim. Appl., 76 (2020), 381-430.  doi: 10.1007/s10589-020-00186-y. [22] W. Tian and X. Yuan, Linearized primal-dual methods for linear inverse problems with total variation regularization and finite element discretization, Inverse Problems, 32 (2016), 115011. doi: 10.1088/0266-5611/32/11/115011. [23] T. Valkonen, Preconditioned proximal point methods and notions of partial subregularity, J. Convex Anal., 28 (2021), 251-278. [24] K. Wang and H. He, A double extrapolation primal-dual algorithm for saddle point problems, J. Sci. Comput., 85 (2020), 1-30.  doi: 10.1007/s10915-020-01330-w. [25] W. Yang and D. Han, Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems, SIAM J. Numer. Anal., 54 (2016), 625-640.  doi: 10.1137/140974237. [26] X. Zheng and K. Ng, Metric subregularity of piecewise linear multifunctions and applications to piecewise linear multiobjective optimization, SIAM J. Optim., 24 (2014), 154-174.  doi: 10.1137/120889502. [27] M. Zhu and T. Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, CAM Reports, UCLA, Los Angeles, CA, 2008, 08-34.

Figures(3)

Tables(1)