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

Kai Wang; Deren Han

doi:10.3934/jimo.2021134

Article Contents

2022, Volume 18, Issue 5: 3749-3770. Doi: 10.3934/jimo.2021134

This issue Previous Article Steepest-descent block-iterative methods for a finite family of quasi-nonexpansive mappings Next Article Direct optimal control for time-delay systems via a lifted multiple shooting algorithm

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

Kai Wang^1, and
Deren Han^2, ,

1.
School of Science, Nanjing University of Science and Technology, Xiaolingwei 200, Nanjing, 210094, China
2.
School of Mathematical Sciences, Beijing Advanced Innovation Center for Big Data and Brain Computing (BDBC), Beihang University, Beijing, 100191, China

^* Corresponding author: Deren Han (handr@buaa.edu.cn)
^* Corresponding author: Deren Han (handr@buaa.edu.cn)

Received: March 2021

Revised: May 2021

Early access: August 2021

Published: November 2022

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

Abstract Full Text(HTML) Figure(3) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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) $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

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