Figure 1.
The relation between iteration times and stop criteria of four algorithms with different $ n $
-
Previous Article
The research on the properties of Fourier matrix and bent function
- NACO Home
- This Issue
-
Next Article
Survey of derivative-free optimization
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 |
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:
Xin Yang, Nan Wang, Lingling Xu. A parallel Gauss-Seidel method for convex problems with separable structure. Numerical Algebra, Control and 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. |
| [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. |
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. |
| [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. |
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 |
|||||
| Iter. | Obj. | Iter. | Obj. | Iter. | Obj. | ||||
| 90 | 3.6410 | 239 | 3.6405 | 110 | 3.6381 | 3.6406 | |||
| 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 | |||
| 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 | |||
| 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 | |||
| 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 | |||
| 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 |
|||||
| Iter. | Obj. | Iter. | Obj. | Iter. | Obj. | ||||
| 90 | 3.6410 | 239 | 3.6405 | 110 | 3.6381 | 3.6406 | |||
| 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 | |||
| 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 | |||
| 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 | |||
| 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 | |||
| 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 | |||
| 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]