• PDF
• Cite
• Share
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
• Figures(3)

Tables(2)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint