Abstract
The alternating direction method of multipliers (ADMM) is one of the most successful and powerful methods for separable minimization optimization. Based on the idea of symmetric ADMM in two-block optimization, we add an updating formula for the Lagrange multiplier without restricting its position for multi-block one. Then, combining with the Bregman distance, in this work, a Bregman-style partially symmetric ADMM is presented for nonconvex multi-block optimization with linear constraints, and the Lagrange multiplier is updated twice with different relaxation factors in the iteration scheme. Under the suitable conditions, the global convergence, strong convergence and convergence rate of the presented method are analyzed and obtained. Finally, some preliminary numerical results are reported to support the correctness of the theoretical assertions, and these show that the presented method is numerically effective.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Attouch, H., Bolte, J. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program., 116: 5–16 (2009)
Attouch, H., Bolte, J., Redont, P., Soubeyran, A. Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res., 35: 438–457 (2010)
Bolte, J., Sabach, S., Teboulle, M. Proximal alternating linearized minimization or nonconvex and nonsmooth problems. Math. Program., 146(1–2): 459–494 (2014)
Candès E., Li X., Ma, Y., Wright, J. Robust principal component analysis? J. ACM, 58(3): 1–37 (2011)
Chen, C. Some notes on the divergence example for multi-block alternating direction method of multipliers (in Chinese). Oper. Res. Trans., 23(3): 135–140 (2019)
Chen, C., He B., Ye, Y., Yuan, X. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program., 155(1–2): 57–79 (2016)
Douglas, J., Rachford, H.H. On the numerical solution of heat conduction problems in two or three space variables. Trans. Am. Math. Soc., 82: 421–439 (1956)
Gabay, D. Chapter IX applications of the method of multipliers to variational inequalities. Stud. Math. Appl., 15: 299–331 (1983)
Guo, K., Han, D., Wang, D., Wu, T. Convergence of ADMM for multi-block nonconvex separable optimization models. Front. Math. China, 12(5): 1139–1162 (2017)
Han, D., Yuan, X. A note on the alternating direction method of multipliers. J. Optim. Theory Appl., 155(1): 227–238 (2012)
He, B., Tao, M., Yuan, X. Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim., 22(2): 313–340 (2012)
He, B., Yuan, X. Linearized alternating direction method with Gaussian back substitution for separable convex programming. Numer. Algebr. Control Optim., 3(2): 247–260 (2013)
Hestenes, M. Multiplier and gradient methods. J. Optim. Theory Appl., 4: 303–320 (1969).
Li G., Pong, T. Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim., 25: 2434–2460 (2015)
Lions, P.L. Mercier, B. Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal., 16: 964–979 (1979)
Liu, P., Jian, J., Xu, J., Ma, G. A linear approximation Bregman-type Peaceman-Rachford splitting method for nonconvex nonseparable optimization. Acta. Math. Sin. Chin. Ser., 66(01): 75–94 (2023)
Jian, J., Liu, P., Jiang, X. A partially symmetric regularized alternating direction method of multipliers for nonconvex multi-block optimization. Acta. Math. Sin. Chin. Ser., 64(06): 1005–1026 (2021)
Nesterov, Y. Introduction Lectures on Convex Optimization: a Basic Course. Springer Science & Business Media, New York, 2004
Peaceman, D.W., Rachford, Jr. H.H. The numerical solution of parabolic and elliptic differential equations. J. Soc. Indust. Appl. Math., 3: 28–41 (1955)
Powell, M. A Method for Nonlinear Constraints in Minimization Problems. In: Fletcher, R. (ed.) Optimization, pp. 283–298. Academic Press, London, 1969
Rockafellar, R. T., Wets, R. Variational Analysis. Springer Science & Business Media, Berlin, 2009
Scheinberg, K., Ma, S., Goldfarb, D. Sparse inverse covariance selection via alternating linearization methods. Adv. Neural Inform. Proc. Sys., 2101–2109 (2010)
Wang, H., Banerjee, A. Bregman alternating direction method of multipliers. Proc. Adv. Neural Inform. Proc. Sys., 2816–2824 (2014)
Wang, F., Cao, W., Xu, Z. Convergence of multi-block Bregman ADMM for nonconvex composite problems. Sci. China Inform. Sci., 61(12): 122101 (2018)
Wang, F., Xu, Z., Xu, H. Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems. arXiv:1410.8625 (2014)
Xu, J., Chao, M. An inertial Bregman generalized alternating direction method of multipliers for nonconvex optimization. J. Appl. Math. Comput., 68: 1–27 (2022)
Xu, Z., Chang, X., Xu, F., Zhang, H. L1/2 regularization: A thresholding representation theory and a fast solver. IEEE T. Neur. Net. Lear., 23(7): 1013–1027 (2012)
Yang, L., Pong, T.K., Chen, X. Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction. SIAM J. Imaging Sci., 10(1): 74–110 (2017)
Zeng, J., Fang, J., Xu, Z. Sparse SAR imaging based on L1/2 regularization. Sci. China F., 55: 1755–1775 (2012)
Zeng, J., Xu, Z., Zhang, B., Hong, W., Wu, Y. Accelerated L1/2 regularization based SAR imaging via BCR and reduced Newton skills. Signal Process., 93: 1831–1844 (2013)
Zhang, C., Song, Y., Cai, X., Han, D. An extended proximal ADMM algorithm for three-block nonconvex optimization problems. J. Comput. Appl. Math., 398: 113681 (2021)
Zhang, C., Yang, Y., Wang, Z., Chen, Y. A linearized alternating direction method of multipliers for a special three-block nonconvex optimization problem of background/foreground extraction. IEEE Access, 8: 198886–198899 (2020)
Zhu, M, Mihic, K, Ye, Y. On a randomized multi-block ADMM for solving selected machine learning problems. arXiv:1907.01995 (2019)
Acknowledgments
The authors wish to thank the Editor-in-Chief and the two anonymous referees for their very professional reviews and quite useful suggestions, which greatly helped us to improve the original version of this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is supported by the National Natural Science Foundation of China (No. 12171106) and the Natural Science Foundation of Guangxi Province (No. 2020GXNSFDA238017).
Rights and permissions
About this article
Cite this article
Liu, Pj., Jian, Jb. & Ma, Gd. A Bregman-style Partially Symmetric Alternating Direction Method of Multipliers for Nonconvex Multi-block Optimization. Acta Math. Appl. Sin. Engl. Ser. 39, 354–380 (2023). https://doi.org/10.1007/s10255-023-1048-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-023-1048-5
Keywords
- nonconvex optimization
- multi-block optimization
- alternating direction method with multipliers
- Kurdyka-Łojasiewicz property
- convergence rate