No Access

General Inexact Primal-Dual Hybrid Gradient Methods for Saddle-Point Problems and Convergence Analysis

Research Center of Risk Management and Emergency, Decision Making, School of Management Science and Engineering, Nanjing University of Information Science and Technology, Nanjing 210044, P. R. China

E-mail Address: wuzm@nuist.edu.cn

Search for more papers by this author

and

Min Li

School of Management and Engineering, Nanjing University, Nanjing 210093, P. R. China

E-mail Address: limin@nju.edu.cn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0217595921500445Cited by:3 (Source: Crossref)

Abstract

In this paper, we focus on the primal-dual hybrid gradient (PDHG) method, which is being widely used to solve a broad spectrum of saddle-point problems. Despite of its wide applications in different areas, the study of inexact versions of PDHG still seems to be in its infancy. We investigate how to design implementable inexactness criteria for solving the subproblems in PDHG scheme so that the convergence of an inexact PDHG can be guaranteed. We propose two specific inexactness criteria and accordingly some inexact PDHG methods for saddle-point problems. The convergence of both inexact PDHG methods is rigorously proved, and their convergence rates are estimated under different scenarios. Moreover, some numerical results on image restoration problems are reported to illustrate the efficiency of the proposed methods.

Keywords:

AMSC: 90C25, 90C33, 65K05

References

Arrow, KJ, L Hurwicz and H Uzawa (1958). Studies in linear and nonlinear programming. In Stanford Mathematical Studies in the Social Science, Chenery, HB, SM Johnson, S Karlin, T Marschak and RM Solow (Eds.), Vol. II. Stanford: Stanford University Press. Google Scholar
Bonettini, S and V Ruggiero (2012). On the convergence of primal-dual hybrid gradient algorithms for total variation image restoration. Journal of Mathematical Imaging and Vision, 44, 236–253. Crossref, Web of Science, Google Scholar
Chambolle, A and T Pock (2011). A first-order primal-dual algorithm for convex problem with applications to imaging. Journal of Mathematical Imaging and Vision, 40(1), 120–145. Crossref, Web of Science, Google Scholar
Condat, L (2013). A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. Journal of Optimization Theory and Applications, 158, 460–479. Crossref, Web of Science, Google Scholar
Dai, Y and R Fletcher (2005). Projected Barzilai-Borwein methods for large-scale box constrained quadratic programming. Numerische Mathematik, 100(1), 21–47. Crossref, Web of Science, Google Scholar
Deng, W, MJ Lai, ZM Peng and WT Yin (2014). Parallel multi-block ADMM with $o (1 / k)$ $o (1 / k)$ convergence. Journal of Scientific Computing, 71, 712–736. Crossref, Web of Science, Google Scholar
Douglas, J and HH Rachford (1956). On the numerical solution of the heat conduction problem in 2 and 3 space variables. Transactions of the American Mathematical Society, 82, 421–439. Crossref, Google Scholar
Eckstein, J and W Yao (2017). Approximate ADMM algorithms derived from Lagrangian splitting. Computational Optimization and Applications, 68(2), 363–405. Crossref, Web of Science, Google Scholar
Eckstein, J and W Yao (2018). Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM. Mathematical Programming, 170(2), 417–444. Crossref, Web of Science, Google Scholar
Esser, E, X Zhang and TF Chan (2010). A general framework for a class of first order primal-dual algorithms for TV minimization. SIAM Journal on Imaging Sciences, 3, 1015–1046. Crossref, Web of Science, Google Scholar
Glowinski, R and A Marrocco (1975). Approximation par éléments finis d’ordre un et résolution par pénalisation-dualité d’une classe de problèmes non linéaires. R.A.I.R.O., R2, 41–76. Google Scholar
Goldstein, T, M Li and XM Yuan (2015). Adaptive primal-dual splitting methods for statistical learning and image processing. Advances in Neural Information Processing Systems, 28, 2089–2097. Google Scholar
He, BS, F Ma and XM Yuan (2017). An algorithmic framework of generalized primal-dual hybrid gradient methods for saddle point problems. Journal of Mathematical Imaging and Vision, 58, 279–293. Crossref, Web of Science, Google Scholar
He, BS, YF You and XM Yuan (2012). On the convergence of primal-dual hybrid gradient algorithm. SIAM Journal on Imaging Sciences, 7, 2526–2537. Crossref, Web of Science, Google Scholar
He, BS and XM Yuan (2012). Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective. SIAM Journal on Imaging Sciences, 5, 119–149. Crossref, Web of Science, Google Scholar
Jiang, F, XJ Cai, ZM Wu and DR Han (2021a). Approximate first-order primal-dual algorithms for saddle point problems. Mathematics of Computation, 90, 1227–1262. Crossref, Web of Science, Google Scholar
Jiang, F, ZM Wu, XJ Cai and HC Zhang (2021b). A first-order inexact primal-dual algorithm for a class of convex-concave saddle point problems. Numerical Algorithms, 88, 1109–1136. Crossref, Web of Science, Google Scholar
Korpelevič, GM (1976). An extragradient method for finding saddle points and for other problems. Èkonomika i Matematicheskie Metody, 12(4), 747–756. Google Scholar
Lions, PL and B Mercier (1979). Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16, 964–979. Crossref, Web of Science, Google Scholar
Martinet, B (1970). Regularisation, d’inéquations variationelles par approximations succesives. Revue Française d’informatique et de Recherche Opérationnelle, 4, 154–159. Google Scholar
Popov, LD (1980). A modification of the Arrow-Hurwitz method of search for saddle points. Zametki, 28(5), 777–784. Google Scholar
Rasch, J and A Chambolle (2020). Inexact first-order primal-dual algorithms. Computational Optimization and Applications, 76(2), 381–430. Crossref, Web of Science, Google Scholar
Rudin, L, S Osher and E Fatemi (1992). Nonlinear total variation based noise removal algorithms. Physica D, 60, 227–238. Crossref, Web of Science, Google Scholar
Shefi, R (2015). Rate of convergence analysis for convex nonsmooth optimization algorithms. PhD Thesis, Tel Aviv University, Israel. Google Scholar
Tian, WY and XM Yuan (2016). Linearized primal-dual methods for linear inverse problems with total variation regularization and finite element discretization. Inverse Problems, 32(11), 115011. Crossref, Web of Science, Google Scholar
Weiss, P, L Blanc-Feraud and G Aubert (2009). Efficient schemes for total variation minimization under constraints in image processing. SIAM Journal on Scientific Computing, 31(3), 2047–2080. Crossref, Web of Science, Google Scholar
Yin, W, S Osher, D Goldfarb and J Darbon (2008). Bregman iterative algorithms for $ℓ_{1}$ $ℓ_{1}$ -minimization with applications to compressed sensing. SIAM Journal on Imaging Sciences, 1(1), 143–168. Crossref, Web of Science, Google Scholar
Zhang, X, M Burger and S Osher (2010). A unified primal-dual algorithm framework based on Bregman iteration. Journal of Scientific Computing, 46(1), 20–46. Crossref, Web of Science, Google Scholar
Zhu, M and TF Chan (2008). An efficient primal-dual hybrid gradient algorithm for total variation image restoration. CAM Report, 8–34. Google Scholar