# American Institute of Mathematical Sciences

December  2020, 10(4): 557-570. doi: 10.3934/naco.2020051

## 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

Received  March 2020 Revised  September 2020 Published  September 2020

Fund Project: 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.

Citation: Xin Yang, Nan Wang, Lingling Xu. A parallel Gauss-Seidel method for convex problems with separable structure. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 557-570. doi: 10.3934/naco.2020051
##### 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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.   Google Scholar [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.  Google Scholar [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.  Google Scholar

show all references

##### 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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.   Google Scholar [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.  Google Scholar [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.  Google Scholar
The relation between iteration times and stop criteria of four algorithms with different $n$
The results of Algorithm 1, JADMM and BWLADMM with different $N$
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
 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
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
 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] Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283 [2] Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247 [3] Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial & Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052 [4] Rong Liu, Feng-Qin Zhang, Yuming Chen. Optimal contraception control for a nonlinear population model with size structure and a separable mortality. Discrete & Continuous Dynamical Systems - B, 2016, 21 (10) : 3603-3618. doi: 10.3934/dcdsb.2016112 [5] Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023 [6] Jean-Luc Akian, Radjesvarane Alexandre, Salma Bougacha. A Gaussian beam approach for computing Wigner measures in convex domains. Kinetic & Related Models, 2011, 4 (3) : 589-631. doi: 10.3934/krm.2011.4.589 [7] Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing. Journal of Industrial & Management Optimization, 2014, 10 (1) : 113-129. doi: 10.3934/jimo.2014.10.113 [8] Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115 [9] Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243 [10] Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial & Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767 [11] Xiaojin Zheng, Zhongyi Jiang. Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020071 [12] Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357 [13] Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349 [14] Tobias H. Colding and Bruce Kleiner. Singularity structure in mean curvature flow of mean-convex sets. Electronic Research Announcements, 2003, 9: 121-124. [15] Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064 [16] Jinchuan Zhou, Changyu Wang, Naihua Xiu, Soonyi Wu. First-order optimality conditions for convex semi-infinite min-max programming with noncompact sets. Journal of Industrial & Management Optimization, 2009, 5 (4) : 851-866. doi: 10.3934/jimo.2009.5.851 [17] Silvia Faggian. Boundary control problems with convex cost and dynamic programming in infinite dimension part II: Existence for HJB. Discrete & Continuous Dynamical Systems - A, 2005, 12 (2) : 323-346. doi: 10.3934/dcds.2005.12.323 [18] Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305 [19] Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078 [20] Gunther Dirr, Hiroshi Ito, Anders Rantzer, Björn S. Rüffer. Separable Lyapunov functions for monotone systems: Constructions and limitations. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2497-2526. doi: 10.3934/dcdsb.2015.20.2497

Impact Factor:

## Tools

Article outline

Figures and Tables