Article Contents
Article Contents

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

• *Corresponding author

This paper is supported by NSFC 11971238

• 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.

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

 Citation:

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

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

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

 Problem Algorithm 1 JADMM BWLADMM Real $\|x^*\|_1$ Iter. Obj. Iter. Obj. Iter. Obj. 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

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

 Problem n Algorithm 1 PPPCSA JADMM BWLADMM 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
•  [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.

Figures(3)

Tables(2)