The alternating direction method of multipliers (ADMM) is an effective and widely used first-order method for solving composite problems. Nonetheless, existing convergence conditions on ADMM in non-convex settings are too restrictive, limiting ADMM's practical applicability. The main contribution of this paper is the relaxation of existing convergence results of the multi-block proximal ADMM (PADMM) for non-convex optimization problems. Whereas existing results require that there exists a smooth objective term and the associated coefficient matrix has full row rank, we only assume the existence of some smooth terms such that the concatenation of their coefficient matrices is full row rank. Under the weakened conditions, we establish the convergence of PADMM and characterize its convergence rate. Furthermore, for more general cases where the relaxed condition does not hold, we propose a method to equivalently reformulate the original problem such that it satisfies the required full row rank condition and PADMM can be applied.
WANG Qingyang
,
YUAN Zihang
,
YANG Jiawen
,
KONG Xiangyu
,
CHEN Caihua
. On the convergence of the alternating direction method of multipliers for non-convex optimization[J]. Operations Research Transactions, 2026
, 30(3)
: 99
-115
.
DOI: 10.15960/j.cnki.issn.1007-6093.2026.03.006
[1] Wu X, Yang Z, Stoica P, et al. Maximum likelihood line spectral estimation in the signal domain: a rank-constrained structured matrix recovery approach [J]. IEEE Transactions on Signal Processing, 2022, 70: 4156-4169.
[2] Wu X, Yang Z, Xu Z. Multichannel frequency estimation in challenging scenarios via structured matrix embedding and recovery (StruMER) [J]. IEEE Transactions on Signal Processing, 2023, 71: 3242-3256.
[3] Wen Z, Yang C, Liu X, et al. Alternating direction methods for classical and ptychographic phase retrieval [J]. Inverse Problems, 2012, 28(11): 115010.
[4] Liavas A P, Sidiropoulos N D. Parallel algorithms for constrained tensor factorization via alternating direction method of multipliers [J]. IEEE Transactions on Signal Processing, 2015, 63(20): 5450-5463.
[5] Glowinski R, Marroco A. Sur l’approximation, paréléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de probl`emes de Dirichlet non linéaires [J]. Revue fra?caise d’automatique, informatique, recherche opérationnelle. Analyse numérique, 1975, 9(R2): 41-76.
[6] Bertsekas D, Tsitsiklis J. Parallel and distributed computation: numerical methods [M]. Nashua: Athena Scientific, 1997.
[7] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers [J]. Foundations and Trends in Machine learning, 2011, 3(1): 1-122.
[8] Davis D, Yin W. Convergence rate analysis of several splitting schemes [M]//Glowinski R, Osher S J, Yin W. (eds.) Splitting methods in communication, imaging, science, and engineering, Cham: Springer, 2017: 115-163.
[9] He B, Yuan X. On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method [J]. SIAM Journal on Numerical Analysis, 2012, 50(2): 700-709.
[10] Monteiro R D, Svaiter B F. Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers [J]. SIAM Journal on Optimization, 2013, 23(1): 475-507.
[11] Chen C, He B, Ye Y, et al. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent [J]. Mathematical Programming, 2016, 155(1): 57-79.
[12] He B, Hou L, Yuan X. On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming [J]. SIAM Journal on Optimization, 2015, 25(4): 2274-2312.
[13] He B, Tao M, Yuan X. Alternating direction method with Gaussian back substitution for separable convex programming [J]. SIAM Journal on Optimization, 2012, 22(2): 313-340.
[14] Deng W, Lai M J, Peng Z, et al. Parallel multi-block ADMM with O(1/k) convergence [J]. Journal of Scientific Computing, 2017, 71(2): 712-736.
[15] Wang Y, Yin W, Zeng J. Global convergence of ADMM in nonconvex nonsmooth optimization [J]. Journal of Scientific Computing, 2019, 78(1): 29-63.
[16] Wang F, Xu Z, Xu H K. Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems [PP/OL]. (2014-12-05)[2025-11-05]. https://arxiv.org/abs/1410.8625.
[17] Li G, Pong T K. Global convergence of splitting methods for nonconvex composite optimization [J]. SIAM Journal on Optimization, 2015, 25(4): 2434-2460.
[18] Hong M, Luo Z Q, Razaviyayn M. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems [J]. SIAM Journal on Optimization, 2016, 26(1): 337-364.
[19] Rockafellar R T, Wets R J. Variational analysis [M]. Berlin: Springer, 1998.
[20] Xu Y, Yin W. A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion [J]. SIAM Journal on imaging sciences, 2013, 6(3): 1758-1789.
[21] Attouch H, Bolte J, Redont P, et al. Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Lojasiewicz inequality [J]. Mathematics of Operations Research, 2010, 35(2): 438-457.
[22] Bolte J, Daniilidis A, Ley O, et al. Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity [J]. Transactions of the American Mathematical Society, 2010, 362(6): 3319-3363.
[23] Bolte J, Daniilidis A, Lewis A. The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems [J]. SIAM Journal on Optimization, 2007, 17(4): 1205-1223.
[24] Jiang S, Zhang J, Chen C, et al. Smoothing partial exact penalty splitting method for mathematical programs with equilibrium constraints [J]. Journal of Global Optimization, 2018, 70(1): 223-236.
