• Previous Article
    A unified analysis for scheduling problems with variable processing times
  • JIMO Home
  • This Issue
  • Next Article
    Pricing, carbon emission reduction and recycling decisions in a closed-loop supply chain under uncertain environment
doi: 10.3934/jimo.2021134
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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 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 & Management Optimization, 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.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[23]

T. Valkonen, Preconditioned proximal point methods and notions of partial subregularity, J. Convex Anal., 28 (2021), 251-278.   Google Scholar

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

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

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

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

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.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[23]

T. Valkonen, Preconditioned proximal point methods and notions of partial subregularity, J. Convex Anal., 28 (2021), 251-278.   Google Scholar

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

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

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

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

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]

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

[2]

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 & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[3]

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

[4]

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

[5]

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 & Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190

[6]

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

[7]

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 & Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153

[8]

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

[9]

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

[10]

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

[11]

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 & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[12]

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

[13]

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 & Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053

[14]

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 & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91

[15]

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

[16]

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

[17]

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

[18]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723

[19]

Pierre Frankel. Alternating proximal algorithm with costs-to-move, dual description and application to PDE's. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 545-557. doi: 10.3934/dcdss.2012.5.545

[20]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

2020 Impact Factor: 1.801

Article outline

Figures and Tables

[Back to Top]