American Institute of Mathematical Sciences

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

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

Xin Yang , Nan Wang and  Lingling Xu ,

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.

Keywords: Convex programming, parallel computing, separable structure.
Mathematics Subject Classification: 92B05, 93C95, 34H05, 65L03.
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

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as 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 $
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 Options

Download as excel

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
Table Options

Download as excel

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]

Julian Chaidez, Michael Hutchings. Computing Reeb dynamics on four-dimensional convex polytopes. Journal of Computational Dynamics, 2021, 8 (4) : 403-445. doi: 10.3934/jcd.2021016
[8]

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
[9]

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
[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]

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
[12]

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
[13]

Xiaojin Zheng, Zhongyi Jiang. Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2331-2343. doi: 10.3934/jimo.2020071
[14]

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
[15]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2021, 8 (1) : 61-67. doi: 10.3934/jdg.2021001
[16]

Tobias H. Colding and Bruce Kleiner. Singularity structure in mean curvature flow of mean-convex sets. Electronic Research Announcements, 2003, 9: 121-124.

[17]

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
[18]

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
[19]

Silvia Faggian. Boundary control problems with convex cost and dynamic programming in infinite dimension part II: Existence for HJB. Discrete & Continuous Dynamical Systems, 2005, 12 (2) : 323-346. doi: 10.3934/dcds.2005.12.323
[20]

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

 Impact Factor: 

Tools

Metrics

  • PDF downloads (196)
  • HTML views (210)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy