A distributed Douglas-Rachford splitting method for solving linear constrained multi-block weakly convex problems

Leyu Hu; Jiaxin Xie; Xingju Cai; Deren Han

doi:10.3934/ipi.2024048

Article Contents

2025, Volume 19, Issue 4: 632-659. Doi: 10.3934/ipi.2024048

This issue Previous Article Next Article Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem

A distributed Douglas-Rachford splitting method for solving linear constrained multi-block weakly convex problems

1.
LMIB of the Ministry of Education, School of Mathematical Sciences, Beihang University, Beijing, 100191, China
2.
School of Mathematical Sciences, Nanjing Normal University, Nanjing, 210023, China

^*Corresponding author: Deren Han
^*Corresponding author: Deren Han

Received: November 2023

Revised: September 2024

Early access: November 29, 2024

Published online: November 29, 2024

The study was supported by the Ministry of Science and Technology of China (No. 2021YFA1003600), and by National Natural Science Foundation of China (12126608, 12126603, 12471290).

Abstract / Introduction Full Text(HTML) Figure(10) / Table(1) Related Papers Cited by

Abstract

In recent years, a distributed Douglas-Rachford splitting method (DDRSM) has been proposed to tackle multi-block separable convex optimization problems. This algorithm offers relatively easier subproblems and greater efficiency for large-scale problems compared to various augmented-Lagrangian-based parallel algorithms. Building upon this, we explore the extension of DDRSM to weakly convex cases. By assuming weak convexity of the objective function and introducing an error bound assumption, we demonstrate the linear convergence rate of DDRSM. Some promising numerical experiments involving compressed sensing and robust alignment of structures across images (RASL) show that DDRSM has advantages over augmented-Lagrangian-based algorithms, even in weakly convex scenarios.

Keywords:

Multi-block problems,
weakly convex,
parallel algorithm,
distributed Douglas-Rachford splitting method,
error bound,
linear convergence rate.

Mathematics Subject Classification: 90C26, 90C30, 65K10, 94A08.

Citation:

Full Text(HTML)

Figure 1. PSNR by CPU-time for different sizes of problems

Download: Full-size image PowerPoint slide

Figure 2. input images

Download: Full-size image PowerPoint slide

Figure 3. Digit 3 averaged image for both models by both algorithms

Download: Full-size image PowerPoint slide

Figure 4. Aligned digit 3 images under convex model

Download: Full-size image PowerPoint slide

Figure 5. Aligned digit 3 images under nonconvex model

Download: Full-size image PowerPoint slide

Figure 6. Charts for dummy face example

Download: Full-size image PowerPoint slide

Figure 7. Aligned images under convex model

Download: Full-size image PowerPoint slide

Figure 8. Aligned images under nonconvex model

Download: Full-size image PowerPoint slide

Figure 9. Aligned images adjusted by sparse error under convex model

Download: Full-size image PowerPoint slide

Figure 10. Aligned images adjusted by sparse error under nonconvex model

Download: Full-size image PowerPoint slide

Table 1. Performance comparison between DDRSM and ADMM under nonconvex settings

	Problem Setting		Performance Metrics
Algorithm	$ (m,n) $	Sparsity	PSNR	CPU Time	Iterations
DDRSM	$ (1500,1000) $	0.02	62.79	0.4178s	23
ADMM	$ (1500,1000) $	0.02	62.78	0.6105s	57
DDRSM	$ (3000,1000) $	0.02	63.46	0.7983s	23
ADMM	$ (3000,1000) $	0.02	63.46	0.9376s	52
DDRSM	$ (1500,1000) $	0.06	67.53	0.4330s	25
ADMM	$ (1500,1000) $	0.06	67.63	0.5607s	60
DDRSM	$ (1500,1000) $	0.12	62.29	0.6892s	40
ADMM	$ (1500,1000) $	0.12	62.28	0.6121s	63

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	X. J. Cai, D. R. Han and X. M. Yuan, On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function, Computational Optimization and Applications, 66 (2017), 39-73. doi: 10.1007/s10589-016-9860-y.
[2]	N. Chatzipanagiotis and M. M. Zavlanos, On the convergence of a distributed augmented Lagrangian method for nonconvex optimization, IEEE Transactions on Automatic Control, 62 (2017), 4405-4420. doi: 10.1109/TAC.2017.2658438.
[3]	C. H. Chen, B. S. He, Y. Y. Ye and X. M. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Mathematical Programming, 155 (2016), 57-79. doi: 10.1007/s10107-014-0826-5.
[4]	G. Chen and M. Teboulle, A proximal-based decomposition method for convex minimization problems, Mathematical Programming, 64 (1994), 81-101. doi: 10.1007/BF01582566.
[5]	Y. M. Chen, W. W. Hager, M. Yashtini, X. J. Ye, et al., Bregman operator splitting with variable stepsize for total variation image reconstruction, Computational Optimization and Applications, 54 (2013), 317-342. doi: 10.1007/s10589-012-9519-2.
[6]	W. Deng, M. J. Lai, Z. M. Peng and W. T. Yin, Parallel multi-block ADMM with $o(1/k)$ convergence, Journal of Scientific Computing, 71 (2017), 712-736. doi: 10.1007/s10915-016-0318-2.
[7]	F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003. doi: 10.1007/b97543.
[8]	Q. Fan, J. M. Zurada and W. Wu, Convergence of online gradient method for feedforward neural networks with smoothing ${L}_{1/2}$ regularization penalty, Neurocomputing, 131 (2014), 208-216. doi: 10.1016/j.neucom.2013.10.023.
[9]	K. Guo and D. R. Han, A note on the Douglas–Rachford splitting method for optimization problems involving hypoconvex functions, Journal of Global Optimization, 72 (2018), 431-441. doi: 10.1007/s10898-018-0660-z.
[10]	K. Guo, D. R. Han, D. Z. Wang and T. T. Wu, Convergence of ADMM for multi-block nonconvex separable optimization models, Frontiers of Mathematics in China, 12 (2017), 1139-1162. doi: 10.1007/s11464-017-0631-6.
[11]	K. Guo, D. R. Han and X. M. Yuan, Convergence analysis of Douglas–Rachford splitting method for "strongly+ weakly" convex programming, SIAM Journal on Numerical Analysis, 55 (2017), 1549-1577. doi: 10.1137/16M1078604.
[12]	D. R. Han, H. J. He and L. L. Xu, A proximal parallel splitting method for minimizing sum of convex functions with linear constraints, Journal of Computational and Applied Mathematics, 256 (2014), 36-51. doi: 10.1016/j.cam.2013.07.010.
[13]	D. R. Han, X. M. Yuan and W. X. Zhang, An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing, Mathematics of Computation, 83 (2014), 2263-2291. doi: 10.1090/S0025-5718-2014-02829-9.
[14]	B. S. He, X. L. Fu and Z. K. Jiang, Proximal-point algorithm using a linear proximal term, Journal of Optimization Theory and Applications, 141 (2009), 299-319. doi: 10.1007/s10957-008-9493-0.
[15]	B. S. He, L. S. Hou and X. M. Yuan, On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, SIAM Journal on Optimization, 25 (2015), 2274-2312. doi: 10.1137/130922793.
[16]	B. S. He, M. Tao and X. M. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization, 22 (2012), 313-340. doi: 10.1137/110822347.
[17]	H. J. He and D. R. Han, A distributed Douglas–Rachford splitting method for multi-block convex minimization problems, Advances in Computational Mathematics, 42 (2016), 27-53. doi: 10.1007/s10444-015-9408-1.
[18]	M. R. Hestenes, Multiplier and gradient methods, Journal of Optimization Theory and Applications, 4 (1969), 303-320. doi: 10.1007/BF00927673.
[19]	L. Y. Hu, W. X. Zhang, X. J. Cai and D. R. Han, A parallel operator splitting algorithm for solving constrained total-variation Retinex, Inverse Problems and Imaging, 14 (2020), 1135-1156. doi: 10.3934/ipi.2020058.
[20]	Z. H. Jia, X. Gao, X. J. Cai and D. R. Han, Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems, Journal of Optimization Theory and Applications, 188 (2021), 1-25. doi: 10.1007/s10957-020-01782-y.
[21]	Y. N. Jiang, D. R. Han and X. J. Cai, An efficient partial parallel method with scaling step size strategy for three-block convex optimization problems, Mathematical Methods of Operations Research, 96 (2022), 383-419. doi: 10.1007/s00186-022-00796-8.
[22]	G. Y. Li and T. K. Pong, Global convergence of splitting methods for nonconvex composite optimization, SIAM Journal on Optimization, 25 (2015), 2434-2460. doi: 10.1137/140998135.
[23]	G. Y. Li and T. K. Pong, Douglas–Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems, Mathematical Programming, 159 (2016), 371-401. doi: 10.1007/s10107-015-0963-5.
[24]	M. Li and Z. M. Wu, Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems, Journal of Optimization Theory and Applications, 183 (2019), 535-565. doi: 10.1007/s10957-019-01564-1.
[25]	L. Liu, Z. F. Pang and Y. P. Duan, A novel variational model for Retinex in presence of severe noises, Proceedings of the IEEE International Conference on Image Processing, Beijing, China, 2017, 3490–3494. doi: 10.1109/ICIP.2017.8296931.
[26]	L. Liu, Z. F. Pang and Y. P. Duan, Retinex based on exponent-type total variation scheme, Inverse Problems and Imaging, 12 (2018), 1199-1217. doi: 10.3934/ipi.2018050.
[27]	Z. Q. Luo and P. Tseng, On the linear convergence of descent methods for convex essentially smooth minimization, SIAM Journal on Control and Optimization, 30 (1992), 408-425. doi: 10.1137/0330025.
[28]	Z. Q. Luo and P. Tseng, Error bounds and convergence analysis of feasible descent methods: A general approach, Annals of Operations Research, 46 (1993), 157-178. doi: 10.1007/BF02096261.
[29]	M. M. Mäkelä and P. Neittaanmäki, Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control, World Scientific Publishing Co., Inc., River Edge, NJ, 1992. doi: 10.1142/1493.
[30]	Y. G. Peng, A. Ganesh, J. Wright, W. L. Xu, et al., RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Transactions on Pattern Analysis and Machine Intelligence, 34 (2012), 2233-2246. doi: 10.1109/TPAMI.2011.282.
[31]	R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.
[32]	M. Tao and X. M. Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM Journal on Optimization, 21 (2011), 57-81. doi: 10.1137/100781894.
[33]	A. Themelis and P. Patrinos, Douglas–Rachford splitting and ADMM for nonconvex optimization: Tight convergence results, SIAM Journal on Optimization, 30 (2020), 149-181. doi: 10.1137/18M1163993.
[34]	P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Mathematical Programming, 117 (2009), 387-423. doi: 10.1007/s10107-007-0170-0.
[35]	F. H. Wang, Z. B. Xu and H. K. Xu, Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems, Science China. Information Sciences, 61 (2018), 122101. doi: 10.1007/s11432-017-9367-6.
[36]	Y. Wang, Z. F. Pang, Y. P. Duan and K. Chen, Image Retinex based on the nonconvex TV-type regularization, Inverse Problems and Imaging, 15 (2020), 1381-1407. doi: 10.3934/ipi.2020050.
[37]	J. B. Wei, Y. K. Huang, K. Lu and L. Z. Wang, Nonlocal low-rank-based compressed sensing for remote sensing image reconstruction, IEEE Geoscience and Remote Sensing Letters, 13 (2016), 1557-1561. doi: 10.1109/LGRS.2016.2595863.
[38]	W. Wu, Q. Fan, J. M. Zurada, J. Wang, D. Yang and Y. Liu, Batch gradient method with smoothing ${L}_{1/2}$ regularization for training of feedforward neural networks, Neural Networks, 50 (2014), 72-78. doi: 10.1016/j.neunet.2013.11.006.
[39]	J. Xu, Y. K. Hou, D. W. Ren, L. Liu, et al., Star: A structure and texture aware Retinex model, IEEE Transactions on Image Processing, 29 (2020), 5022-5037. doi: 10.1109/TIP.2020.2974060.
[40]	Z. Xu, X. Chang, F. Xu and H. Zhang, ${L}_{1/2}$ regularization: A thresholding representation theory and a fast solver, IEEE Transactions on Neural Networks and Learning Systems, 23 (2012), 1013-1027. doi: 10.1109/TNNLS.2012.2197412.
[41]	L. Yang, T. K. Pong and X. J. Chen, Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction, SIAM Journal on Imaging Sciences, 10 (2017), 74-110. doi: 10.1137/15M1027528.
[42]	M. Yashtini, Multi-block nonconvex nonsmooth proximal ADMM: Convergence and rates under Kurdyka–Łojasiewicz property, Journal of Optimization Theory and Applications, 190 (2021), 966-998. doi: 10.1007/s10957-021-01919-7.
[43]	J. S. Zeng, S. B. Lin, Y. Wang and Z. B. Xu, ${L}_{1/2}$ regularization: Convergence of iterative half thresholding algorithm, IEEE Transactions on Signal Processing, 62 (2014), 2317-2329. doi: 10.1109/TSP.2014.2309076.
[44]	X. J. Zhang, M. R. Bai and M. K. Ng, Nonconvex-TV based image restoration with impulse noise removal, SIAM Journal on Imaging Sciences, 10 (2017), 1627-1667. doi: 10.1137/16M1076034.
[45]	C. Zhao, J. Zhang, S. W. Ma and W. Gao, Nonconvex $L_p$ nuclear norm based ADMM framework for compressed sensing, Proceedings of the Data Compression Conference, Snowbird, UT, USA, 2016,161-170. doi: 10.1109/DCC.2016.104.