\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

  • *Corresponding author

    *Corresponding author

This paper is supported by NSFC 11971238

Abstract Full Text(HTML) Figure(3) / Table(2) Related Papers Cited by
  • 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:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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 $

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

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV
  • [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. ChenB. HeX. 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. CaiD. 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. DengM. LaiZ. 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. HeM. 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. HeM. 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. HeL. 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. HanX. 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. HanX. YuanW. 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. WuX. 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)

SHARE

Article Metrics

HTML views(303) PDF downloads(294) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return