A parallel Gauss-Seidel method for convex problems with separable structure

Xin Yang; Nan Wang; Lingling Xu

doi:10.3934/naco.2020051

Article Contents

2020, Volume 10, Issue 4: 557-570. Doi: 10.3934/naco.2020051

This issue Previous Article Survey of derivative-free optimization Next Article The research on the properties of Fourier matrix and bent function

A parallel Gauss-Seidel method for convex problems with separable structure

Jiangsu Provincial Key Laboratory for NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing, China

*Corresponding author
*Corresponding author

Received: March 2020

Revised: September 2020

Published: September 2020

This paper is supported by NSFC 11971238

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

Abstract

The convergence of direct ADMM is not guaranteed when used to solve multi-block separable convex optimization problems. In this paper, we propose a Gauss-Seidel method which can be calculated in parallel while solving subproblems. First we divide the variables into different groups. In the inner group, we use Gauss-Seidel method solving the subproblem. Among the different groups, Jacobi-like method is used. The effectiveness of the algorithm is proved by some numerical experiments.

Keywords:

Mathematics Subject Classification: 92B05, 93C95, 34H05, 65L03.

Citation:

FullText(HTML)

Figure 1. The relation between iteration times and stop criteria of four algorithms with different $ n $

Download: Full-size image PowerPoint slide

Figure 2. The results of Algorithm 1, JADMM and BWLADMM with different $ N $

Download: Full-size image PowerPoint slide

Figure 3. The comparison of Algorithm 1, JADMM, BWLADMM and DPGSM

Download: Full-size image PowerPoint slide

Table 1. The results of Algorithm 1, JADMM and BWLADMM with different scales of $ A $

Problem	Algorithm 1		JADMM		BWLADMM		Real $ \\|x^*\\|_1 $
Problem	Iter.	Obj.	Iter.	Obj.	Iter.	Obj.	Real $ \\|x^*\\|_1 $
	90	3.6410	239	3.6405	110	3.6381	3.6406
$ m $=20, $ n $=100	111	4.4316	263	4.4299	135	4.4310	4.4325
	196	3.7944	346	3.7957	198	3.7950	3.7948
	158	8.2603	335	8.2617	170	8.2603	8.2641
$ m $=40, $ n $=200	198	7.2109	253	7.2104	222	7.2109	7.2093
	277	8.3752	439	8.3811	343	8.3763	8.4107
	223	16.6467	336	16.6479	235	16.6454	16.6350
$ m $=80, $ n $=400	304	12.5305	631	12.5343	320	12.5316	13.0210
	349	17.1994	519	17.1929	364	17.1981	17.1707
	240	20.3980	364	20.4009	265	20.3978	20.3860
$ m $=100, $ n $=500	319	16.7817	508	16.7750	325	16.7714	16.8788
	388	17.9074	651	17.9105	450	17.9112	18.0729
	356	42.4486	482	42.4570	364	42.4554	42.5606
$ m $=200, $ n $=1000	358	45.2504	523	45.2505	372	45.2531	45.3523
	411	36.1374	495	36.1408	432	36.1393	36.2120

| Show Table

DownLoad: CSV

Table 2. The results of four algorithms with different $ n $

Problem n	Algorithm 1		PPPCSA		JADMM		BWLADMM
Problem n	Iter.	Obj.	Iter.	Obj.	Iter.	Obj.	Iter.	Obj.
20	15	-8.6100e+03	49	-8.6100e+03	19	-8.6100e+03	20	-8.6100e+03
100	16	-1.0150e+06	54	-1.0150e+06	21	-1.0150e+06	22	-1.0150e+06
500	20	-1.2538e+08	59	-1.2538e+08	22	-1.2538e+08	24	-1.2538e+08
1000	22	-1.0015e+09	61	-1.0015e+09	23	-1.0015e+09	25	-1.0015e+09

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	F. Bai and L. Xu, A partially parallel prediction-correction splitting method for convex optimization problems with separable structure, J. Oper. Res. Soc. China, 5 (2017), 529-544. doi: 10.1007/s40305-017-0163-5.
[2]	C. Chen, B. He, X. Yuan and Y. Ye, The direct extension of ADMM for multi-block convex minimization problem is not necessarily convergent, Math. Program., 155 (2016), 57-79. doi: 10.1007/s10107-014-0826-5.
[3]	X. Cai, D. Han and X. Yuan, On the convergence of the direct extension of ADMM for three- block separable convex minimization models with one strongly convex function, Comput. Optim. Appl., 66 (2017), 39-73. doi: 10.1007/s10589-016-9860-y.
[4]	W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers,, J Sci. Comput., 66 (2016), 889-916. doi: 10.1007/s10915-015-0048-x.
[5]	W. Deng, M. Lai, Z. Peng and W. Yin, Parallel multi-block admm with $o(1/ k)$ convergence, J. Sci. Comput., 71 (2017), 712-736. doi: 10.1007/s10915-016-0318-2.
[6]	J. Eckstein and D. 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.
[7]	B. He, Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities, Comput. Optim. Appl., 42 (2009), 195-212. doi: 10.1007/s10589-007-9109-x.
[8]	B. He, M. Tao and X. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim., 22 (2012), 313-340. doi: 10.1137/110822347.
[9]	B. He, M. Tao and X. Yuan, A splitting method for separable convex programming, IMA J. Numer. Anal., 35 (2015), 394-426. doi: 10.1093/imanum/drt060.
[10]	B. He, L. Hou and X. Yuan, On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, SIAM J. Optim., 25 (2015), 2274-2312. doi: 10.1137/130922793.
[11]	D. Han, X. Yuan and W. Zhang, An augmented-Lagrangian-based parallel splitting method for separable convex minimization with applications to image processing, Math. Comput., 83 (2014), 2263-2291. doi: 10.1090/S0025-5718-2014-02829-9.
[12]	D. Han, X. Yuan, W. Zhang and X. Cai, An ADM-based splitting method for separable convex programming, Comput. Optim. Appl., 54 (2013), 343-369. doi: 10.1007/s10589-012-9510-y.
[13]	X. Gao and S. Zhang, First-order algorithms for convex optimization with nonseparable objective and coupled constraints, J. Oper. Res. Soc. China, 5 (2016), 1-29. doi: 10.1007/s40305-016-0131-5.
[14]	D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finiteelement approximations, Comput. Math. Appl., 2 (1976), 17-40.
[15]	R. Glowinski and A. Marrocco, Sur l'approximation par éléments nis d'ordre un, et la résolution par pénalisation-dualité d'une classe de problémes de Dirichlet nonlinéaires, J. Equine. Vet. Sci., 2 (1975), 41-76. doi: 10.1051/m2an/197509R200411.
[16]	Z. Wu, X. Cai and D. Han, Linearized block-wise alternating direction method of multipliers for multiple-block convex programming, Journal of Industrial and Management Optimization, 14 (2018), 833-855. doi: 10.3934/jimo.2017078.