September  2022, 18(5): 3749-3770. doi: 10.3934/jimo.2021134

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

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)

Received  March 2021 Revised  May 2021 Published  September 2022 Early access  August 2021

Fund Project: 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.

Citation: Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial and Management Optimization, 2022, 18 (5) : 3749-3770. doi: 10.3934/jimo.2021134
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. CaiD. 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. ChenG. 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. EsserX. 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. GuB. 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. HanD. 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. HanW. 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. HeF. 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. HeY. 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. HeM. 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. HeJ. 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. JiangX. CaiZ. 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.

show all references

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. CaiD. 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. ChenG. 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. EsserX. 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. GuB. 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. HanD. 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. HanW. 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. HeF. 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. HeY. 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. HeM. 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. HeJ. 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. JiangX. CaiZ. 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.

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

Xiayang Zhang, Yuqian Kong, Shanshan Liu, Yuan Shen. A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022008

[2]

Guoyong Gu, Junfeng Yang. A unified and tight linear convergence analysis of the relaxed proximal point algorithm. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022107

[3]

Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027

[4]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[5]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[6]

Ram U. Verma. On the generalized proximal point algorithm with applications to inclusion problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 381-390. doi: 10.3934/jimo.2009.5.381

[7]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190

[8]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[9]

Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial and Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153

[10]

Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems and Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031

[11]

Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073

[12]

Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure and Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791

[13]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[14]

Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial and Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569

[15]

Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053

[16]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91

[17]

Pilar Bayer, Dionís Remón. A reduction point algorithm for cocompact Fuchsian groups and applications. Advances in Mathematics of Communications, 2014, 8 (2) : 223-239. doi: 10.3934/amc.2014.8.223

[18]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011

[19]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103

[20]

Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003

2021 Impact Factor: 1.411

Article outline

Figures and Tables

[Back to Top]