交替方向乘子法(ADMM)是一种有效且被广泛采用的一阶算法,用于求解各类复合优化问题。然而,目前关于ADMM在非凸情形下的收敛条件过于严格,从而限制了其在实际中的适用性。本文的主要贡献是放宽了现有关于多块近端ADMM (PADMM)在非凸优化问题上的收敛条件。现有结果通常要求存在一个光滑的目标项且其对应的系数矩阵为行满秩;而我们只要求存在若干光滑目标项,其对应系数矩阵拼接后的矩阵是行满秩的。在放宽后的条件下,我们证明了PADMM的收敛性并给出了其收敛率。进一步地,对于放宽的行满秩条件不成立的更一般的情况,我们提出了一种将原问题等价转换的方法,使转换后的问题满足所需的行满秩条件,从而可以应用PADMM进行求解。
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.
[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.
北大中文核心期刊