A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem

Xiayang Zhang; Yuqian Kong; Shanshan Liu; Yuan Shen

doi:10.3934/jimo.2022008

Article Contents

2023, Volume 19, Issue 3: 1595-1610. Doi: 10.3934/jimo.2022008

This issue Previous Article Valuing equity-linked death benefits with a threshold expense structure under a regime-switching Lévy model Next Article Dynamic virtual cellular reconfiguration for capacity planning of market-oriented production systems

A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem

1.
Department of Mathematics and Physics, Nanjing Institute of Technology, Nanjing, 211167, China
2.
School of Applied Mathematics, Nanjing University of Finance & Economics, Nanjing, 210023, China
3.
Hefei 168 Middle School, Hefei, 230031, China

^*Corresponding author: Yuan Shen
^*Corresponding author: Yuan Shen

Received: January 31, 2021

Revised: July 31, 2021

Early access: January 2022

Published: March 2023

The first author is supported by the National Natural Science Foundation of China Grant 71571096 and Nanjing Institute of Technology Research Start-up Foundation Grant YKJ201738. The second author is supported by the National Social Science Foundation of China under Grants 19AZD018, 20BGL028, 19BGL205

Abstract Full Text(HTML) Figure(7) / Table(2) Related Papers Cited by

Abstract

The primal-dual hybrid gradient method and the primal-dual algorithm proposed by Chambolle and Pock are both efficient methods for solving saddle point problem. However, the convergence of both methods depends on some assumptions which can be too restrictive or impractical in real applications. In this paper, we propose a new parameter condition for the primal-dual hybrid gradient method. This improvement only requires either the primal or the dual objective function to be strongly convex. The relaxed parameter condition leads to convergence acceleration. Although counter-example shows that the PDHG method is not necessarily convergent with constant step size, it becomes convergent with our relaxed parameter condition. Preliminary experimental results show that PDHG method with our relaxed parameter condition is more efficient than several state-of-art methods.

Keywords:

Mathematics Subject Classification: Primary: 90C30, 65K05; Secondary: 65K15.

Citation:

FullText(HTML)

Figure 1. Comparison of parameter domain with different setting of $ \alpha $

Download: Full-size image PowerPoint slide

Figure 2. Results on LASSO problem with different sample size $ m $ and feature No. $ n $

Download: Full-size image PowerPoint slide

Figure 3. Results on LASSO problem with sparsity and balancing parameter

Download: Full-size image PowerPoint slide

Figure 4. From left to right, up to bottom: the original figure 'sunflower.png($ 900\times824 $)', noisy figure with additive Gaussian noise(Standard deviation = 0.05), figure recovered by PDHG method($ \lambda = 8 $) and figure recovered by PDHG-R($ \lambda = 8 $)

Download: Full-size image PowerPoint slide

Figure 5. From left to right, up to bottom: the original figure 'boat.png($ 512\times512 $)', noisy figure with additive Gaussian noise(Standard deviation = 0.05), figure recovered by PDHG method($ \lambda = 8 $) and figure recovered by PDHG-R($ \lambda = 8 $)

Download: Full-size image PowerPoint slide

Figure 6. Results of image denoising with different images and $ \lambda $

Download: Full-size image PowerPoint slide

Figure 7. Results of image denoising with different stepsize $ \tau $ and $ \sigma $

Download: Full-size image PowerPoint slide

Table 1. Results on LASSO problem with different sample size $ m $ and feature No. $ n $

	100$ \times $1000		100$ \times $10000
	Tol=$ 10^{-4} $	Tol=$ 10^{-6} $	Tol=$ 10^{-4} $	Tol=$ 10^{-6} $
PDHG	24	48	172	284
CP	24	39	140	254
CP-A	30	51	908	7993
FISTA	35	78	217	553
PDHG-R	23	36	124	202
	100$ \times $100000		10000$ \times $100000
	Tol=$ 10^{-4} $	Tol=$ 10^{-6} $	Tol=$ 10^{-4} $	Tol=$ 10^{-6} $
PDHG	1279	2264	12	44
CP	1181	1990	13	31
CP-A	3977	>10000	33	48
FISTA	639	1593	15	53
PDHG-R	990	1723	13	30

| Show Table

DownLoad: CSV

Table 2. Results on LASSO problem with sparsity and balancing parameter

	s=5		s=20
	Tol=$ 10^{-4} $	Tol=$ 10^{-6} $	Tol=$ 10^{-4} $	Tol=$ 10^{-6} $
PDHG	118	312	161	279
CP	157	249	149	236
CP-A	86	131	533	3450
FISTA	149	298	142	447
PDHG-R	142	225	114	207
	$ \beta $=0.1		$ \beta $=0.5
	Tol=$ 10^{-4} $	Tol=$ 10^{-6} $	Tol=$ 10^{-4} $	Tol=$ 10^{-6} $
PDHG	193	307	180	290
CP	185	278	166	218
CP-A	>10000	>10000	87	138
FISTA	313	755	121	212
PDHG-R	150	249	137	197

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in Linear and Non-Linear Programming, With contributions by H. B. Chenery, S. M. Johnson, S. Karlin, T. Marschak, R. M. Solow. Stanford Mathematical Studies in the Social Science, Vol. II. Stanford University Press, Stanford, Calif., 1958.
[2]	S. Bonettini and V. Ruggiero, On the convergence of primal-dual hybrid gradient algorithms for total variation image restoration, J. Math. Imaging Vision, 44 (2012), 236-253. doi: 10.1007/s10851-011-0324-9.
[3]	S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via ADMM, Found. Trends Mach. Learn., 3 (2010), 1-122.
[4]	J. Cai, E. J. Candés and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Opti., 20 (2010), 1956-1982. doi: 10.1137/080738970.
[5]	J. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for compressed sensing, Math. Comput., 78 (2009), 1515-1536. doi: 10.1090/S0025-5718-08-02189-3.
[6]	J. Cai, S. Osher and Z. Shen, Linearized Bregman iteration for frame based image deblurring, SIAM J. Imaging Sci., 2 (2009), 226-252. doi: 10.1137/080733371.
[7]	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.
[8]	A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vison, 20 (2004), 89-97.
[9]	A. Chambolle and T. Pock, A first-order primal-dual algorithms for convex problem with applications to imaging, J. Math. Imaging Vision, 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.
[10]	A. Chambolle and T. Pock, On the ergodic convergence rates of a first order primal dual algorithm, Math. Program., 159 (2016), 253-287. doi: 10.1007/s10107-015-0957-3.
[11]	R. Chan, S. Ma and J. Yang, Inertial primal dual algorithms for structured convex optimization, SIAM J. Imag. Sci., 8 (2015), 2239-2267.
[12]	T. Chan, G. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20 (1999), 1964-1977. doi: 10.1137/S1064827596299767.
[13]	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.
[14]	E. Esser, X. Zhang and T. Chan, A general framework for a class of first order primal-dual algorithms for TV minimization, SIAM J. Imaging Sci., 3 (2010), 1015-1046. doi: 10.1137/09076934X.
[15]	F. Facchinei and J. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Series in Operations Research, Springer Verlag, New York, 2003.
[16]	T. Goldstein, M. Li and X. Yuan, Adaptive primal-dual splitting methods for statistical learning and image processing, Adv. Neural Inform. Process. Syst., (2015), 2089–2097.
[17]	T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343. doi: 10.1137/080725891.
[18]	B. He, Y. You and X. Yuan, On the convergence of primal-dual hybrid gradient algorithm, SIAM J. Imag. Sci., 7 (2014), 2526-2537. doi: 10.1137/140963467.
[19]	B. He and X. Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective, SIAM J. Imag. Sci., 5 (2012), 119-149. doi: 10.1137/100814494.
[20]	B. He and X. Yuan, On the $O(1/n)$ convergence rate of Douglas-Rachford alternating direction method, SIAM J. Numer. Anal., 50 (2012), 700-709. doi: 10.1137/110836936.
[21]	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.
[22]	M. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appli., 4 (1969), 303-320. doi: 10.1007/BF00927673.
[23]	N. Higham, Computing the nearest correlation matrix –-A problem from finance, IMA J. Numer. Anal., 22 (2002), 329-343. doi: 10.1093/imanum/22.3.329.
[24]	Y. Nesterov, Gradient methods for minimizing composite objective function, Math. Program., 140 (2013), 125-161. doi: 10.1007/s10107-012-0629-5.
[25]	J. Pesquet and N. Pustelnik, A parallel inertial proximal optimization method, Pac. J. Optim., 8 (2012), 273-306.
[26]	M. Powell, A method for nonlinear constraints in minimization problems, In Optimization edited by R. Fletcher, Academic Press, (1969), 283–298.
[27]	L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.
[28]	Y. Shen, Q. Li and J. Wu, A variable step-size primal-dual algorithm based on proximal point algorithm (in Chinese), Math. Numer. Sinica., 40 (2018), 85-95.
[29]	R. Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B, 58 (1996), 267-288. doi: 10.1111/j.2517-6161.1996.tb02080.x.
[30]	T. Valkonen, Inertial, corrected, primal-dual proximal splitting, SIAM J. Optim., 30 (2020), 1391-1420. doi: 10.1137/18M1182851.
[31]	Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1 (2008), 248-272. doi: 10.1137/080724265.
[32]	P. Weiss, L. Blanc-Feraud and G. Aubert, Efficient schemes for total variation minimization under constraints in image processing, SIAM J. Sci. Comput., 31 (2009), 2047-2080. doi: 10.1137/070696143.
[33]	B. Zhang, Z. Zhu and S. Wang, A simple primal-dual method for total variation image restoration, J. Vis. Commun. Image R., 38 (2016), 814-823. doi: 10.1016/j.jvcir.2016.04.025.
[34]	H. Zhang, J. Cai, L. Cheng and J. Zhu, Strongly convex programming for exact matrix completion and robust principal component analysis, Inver. Prob. Imaging, 6 (2012), 357-372. doi: 10.3934/ipi.2012.6.357.
[35]	X. Zhang, M. Burger and S. Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46 (2011), 20-46. doi: 10.1007/s10915-010-9408-8.
[36]	M. Zhu and T. Chan, An Efficient Primal-dual Hybrid Gradient Algorithm for Total Variation Image Restoration, CAM Report 08-34, UCLA, USA, 2008.