Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization

Fan Jiang; Zhongming Wu; Xingju Cai

doi:10.3934/jimo.2018181

Article Contents

2020, Volume 16, Issue 2: 835-856. Doi: 10.3934/jimo.2018181

This issue Previous Article Continuous-time mean-variance asset-liability management with stochastic interest rates and inflation risks Next Article An iterated greedy algorithm with variable neighborhood descent for the planning of specialized diagnostic services in a segmented healthcare system

Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization

1.
School of Mathematical Sciences, Jiangsu Key Labratory for NSLSCS, Nanjing Normal University, Nanjing 210023, China
2.
School of Economics and Management, Southeast University, Nanjing, 210096, China

Received: December 31, 2017

Revised: June 30, 2018

Early access: December 2018

Published: February 2020

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

Abstract

We consider the generalized alternating direction method of multipliers (ADMM) for linearly constrained convex optimization. Many problems derived from practical applications have showed that usually one of the subproblems in the generalized ADMM is hard to solve, thus a special proximal term is added. In the literature, the proximal term can be indefinite which plays a vital role in accelerating numerical performance. In this paper, we are devoted to deriving the optimal lower bound of the proximal parameter and result in the generalized ADMM with optimal indefinite proximal term. The global convergence and the $ O(1/t) $ convergence rate measured by the iteration complexity of the proposed method are proved. Moreover, some preliminary numerical experiments on LASSO and total variation-based denoising problems are presented to demonstrate the efficiency of the proposed method and the advantage of the optimal lower bound.

Keywords:

Generalized alternating direction method of multipliers,
convex programming,
convergence rate,
indefinite proximal term,
optimal range.

Mathematics Subject Classification: Primary: 90C25, 65K05, 49M27.

Citation:

Full Text(HTML)

Figure 1. Sensitivity test on the factor $r$ when $\beta = 1$

Download: Full-size image PowerPoint slide

Figure 2. Sensitivity test on the factor $r$ when $\beta = 5$

Download: Full-size image PowerPoint slide

Table 1. Numerical results for LASSO

		$r=0.3$						$r=-0.3$
$n$	$m$	PG-ADMM		PID-SADMM		IPG-ADMM		PG-ADMM		PID-SADMM		IPG-ADMM
$n$	$m$	Iter.	CPU(s)	Iter.	CPU(s)	Iter.	CPU(s)	Iter.	CPU(s)	Iter.	CPU(s)	Iter.	CPU(s)
200	500	65.5	0.04	55.1	0.03	53.9	0.03	66.5	0.04	51.3	0.03	45.0	0.03
300	800	68.0	0.35	57.2	0.29	55.7	0.28	69.0	0.35	53.3	0.27	46.6	0.24
300	1000	91.1	0.66	76.9	0.55	75.0	0.54	92.0	0.66	71.0	0.51	62.0	0.46
500	1500	80.1	1.79	67.3	1.49	65.9	1.46	81.3	1.80	62.8	1.39	55.0	1.22
500	2000	108.0	3.34	90.7	2.82	88.6	2.77	108.3	3.38	83.6	2.60	73.1	2.27
800	2500	85.8	5.40	72.1	4.56	70.5	4.43	87.0	5.47	67.0	4.21	58.7	3.73
1000	3000	79.0	7.42	66.3	6.22	64.8	6.17	80.2	7.54	61.9	5.84	54.1	5.12
1500	5000	92.8	22.22	77.9	18.61	76.2	18.24	93.9	22.51	72.3	17.37	63.4	15.22

| Show Table

DownLoad: CSV

Table 2. Numerical results for TV denoising model

	$r=0.3$						$r=-0.3$
$n$	PG-ADMM		PID-SADMM		IPG-ADMM		PG-ADMM		PID-SADMM		IPG-ADMM
$n$	Iter.	CPU(s)	Iter.	CPU(s)	Iter.	CPU(s)	Iter.	CPU(s)	Iter.	CPU(s)	Iter.	CPU(s)
500	278.0	0.03	260.7	0.03	258.7	0.03	401.5	0.05	356.6	0.04	339.9	0.04
1000	325.9	0.06	297.4	0.05	294.6	0.05	464.8	0.08	422.0	0.08	402.3	0.07
2000	414.9	0.12	380.8	0.11	376.7	0.11	585.3	0.17	533.2	0.16	497.9	0.15
3000	449.5	0.20	423.9	0.19	418.9	0.19	683.8	0.31	602.7	0.27	573.6	0.26
5000	488.7	0.33	456.0	0.30	452.3	0.30	730.0	0.48	662.7	0.44	621.7	0.41
6000	488.1	0.38	456.0	0.35	452.1	0.35	720.7	0.56	642.0	0.50	612.7	0.47
8000	598.3	0.59	558.2	0.54	553.9	0.54	869.5	0.85	774.7	0.75	729.9	0.72
10000	609.6	0.72	561.9	0.66	556.7	0.66	877.0	1.03	791.0	0.93	748.7	0.88

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	A. Beck and M. Teboulle , A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009) , 183-202. doi: 10.1137/080716542.
	S. Boyd , N. Parikh , E. Chu , B. Peleato and J. Eckstein , Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends® Mach. Learn., 3 (2011) , 1-122.
	E. J. Candès and B. Recht , Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009) , 717-772. doi: 10.1007/s10208-009-9045-5.
	S. Chen , D. Donoho and M. Saunders , Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20 (1998) , 33-61. doi: 10.1137/S1064827596304010.
	P. L. Combettes and J. C. Pesquet , A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery, IEEE J-STSP., 1 (2008) , 564-574.
	P. L. Combettes and J. C. Pesquet , Proximal splitting methods in signal processing. In Fixed-point algorithms for inverse problems in science and engineering, Springer New York, 49 (2011) , 185-212. doi: 10.1007/978-1-4419-9569-8_10.
	P. L. Combettes and V. R. Wajs , Signal recovery by proximal forwardbackward splitting, SIAM J. Multiscale Model. Simul., 4 (2005) , 1168-1200. doi: 10.1137/050626090.
	J. Eckstein and D. P. Bertsekas , On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992) , 293-318. doi: 10.1007/BF01581204.
	J. Eckstein and Y. Wang , Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives, Pac. J. Optim., 11 (2015) , 619-644.
	M. J. Fadili and J. L. Starck , Monotone operator splitting for optimization problems in sparse recovery, IEEE ICIP., (2009) , 1461-1464.
	E. X. Fang , B. S. He , H. Liu and X. M. Yuan , Generalized alternating direction method of multipliers: new theoretical insights and applications, Math. Prog. Comp., 7 (2015) , 149-187. doi: 10.1007/s12532-015-0078-2.
	M. A. T. Figueiredo and J. M. Bioucas-Dias , Restoration of poissonian images using alternating direction optimization, IEEE T. Image Process., 19 (2010) , 3133-3145. doi: 10.1109/TIP.2010.2053941.
	D. Gabay and B. Mercier , A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976) , 17-40.
	B. Gao and F. Ma, Symmetric ADMM with positive-indefinite proximal regularization for linearly constrained convex optimization, Avaliable on http://www.optimization-online.org (2016).
	R. Glowinski , On alternating direction methods of multipliers: A historical perspective, Model. Simul. Optim. Sci. Technol. Comput. Methods Appl. Sci., 34 (2014) , 59-82. doi: 10.1007/978-94-017-9054-3_4.
	R. Glowinski and A. Marrocco , Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires, Revue Fr. Autom. Inf. Rech. Opér., Anal. Numér., 9 (1975) , 41-76.
	Y. Gu, B. Jiang and D. R. Han, A semi-proximal-based strictly contractive Peaceman-Rachford splitting method, Avaliable on http://www.optimization-online.org (2015).
	B. S. He , A new method for a class of linear variational inequalities, Math. Program., 66 (1994) , 137-144. doi: 10.1007/BF01581141.
	B. S. He , PPA-like contraction methods for convex optimization: A framework using variational inequality approach, J. Oper. Res. Soc. China, 3 (2015) , 391-420. doi: 10.1007/s40305-015-0108-9.
	B. S. He , H. Liu , Z. R. Wang and X. M. Yuan , A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM J. Optim., 24 (2014) , 1011-1040. doi: 10.1137/13090849X.
	B. S. He, F. Ma and X. M. Yuan, Linearized alternating direction method of multipliers via positive-indefinite proximal regularization for convex programming, Avaliable on http://www.optimization-online.org (2016).
	B. S. He, F. Ma and X. M. Yuan, Optimal linearized alternating direction method of multipliers for convex programming, Avaliable on http://www.optimization-online.org (2017).
	B. S. He and X. M. Yuan, Improving an ADMM-like splitting method via positive-indefinite proximal regularization for three-block separable convex minimization, Avaliable on http://www.optimization-online.org (2016).
	B. S. He, F. Ma and X. M. Yuan, Positive-indefnite proximal augmented Lagrangian method and its application to full Jacobian splitting for multi-block separable convex minimization problems, Avaliable on http://www.optimization-online.org (2016).
	B. S. He and H. Yang , Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities, Oper. Res. Lett., 23 (1998) , 151-161. doi: 10.1016/S0167-6377(98)00044-3.
	B. S. He and X. M. Yuan , On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numer. Math., 130 (2015) , 567-577. doi: 10.1007/s00211-014-0673-6.
	M. Li , X. X. Li and X. M. Yuan , Convergence analysis of the generalized alternating direction method of multipliers with logarithmic-quadratic proximal regularization, J. Optim. Theory Appl., 164 (2015) , 218-233. doi: 10.1007/s10957-014-0567-x.
	M. Li , D. F. Sun and K. C. Toh , A majorized ADMM with indefinite proximal term for linearly constrained convex composite optimization, SIAM J. Optim., 26 (2016) , 922-950. doi: 10.1137/140999025.
	X. X. Li , L. L. Mo , X. M. Yuan and J. Z. Zhang , Linearized alternating direction method of multipliers for sparse group and fused LASSO models, Comput. Statist. Data Anal., 79 (2014) , 203-221. doi: 10.1016/j.csda.2014.05.017.
	X. X. Li and X. M. Yuan , A proximal strictly contractive Peaceman-Rachford splitting method for convex programming with applications to imaging, SIAM J. Imaging Sci., 8 (2015) , 1332-1365. doi: 10.1137/14099509X.
	B. Recht , M. Fazel and P. A. Parrilo , Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52 (2010) , 471-501. doi: 10.1137/070697835.
	L. I. Rudin , S. Osher and E. Fatemi , Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992) , 259-268. doi: 10.1016/0167-2789(92)90242-F.
	G. Steidl and T. Teuber , Removing multiplicative noise by Douglas-Rachford splitting methods, J. Math. Imaging Vis., 36 (2010) , 168-184. doi: 10.1007/s10851-009-0179-5.
	M. Tao and X. M. Yuan , Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim., 21 (2011) , 57-81. doi: 10.1137/100781894.
	R. J. Tibshirani , Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B, 58 (1996) , 267-288.
	J. F. Yang and X. M. Yuan , Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization, Math. Comp., 82 (2013) , 301-329. doi: 10.1090/S0025-5718-2012-02598-1.
	X. M. Yuan , Alternating direction method for covariance selection models, J. Sci. Comput., 51 (2012) , 261-273. doi: 10.1007/s10915-011-9507-1.
	W. X. Zhang , X. J. Cai and Z. H. Jia , A proximal alternating linearization method for minimizing the sum of two convex functions, Sci. China Math., 58 (2015) , 1-20. doi: 10.1007/s11425-015-4986-4.