非凸优化中交替方向乘子法的收敛性研究

doi:10.15960/j.cnki.issn.1007-6093.2026.03.006

摘要/Abstract

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

关键词: 多块交替方向乘子法, 非凸优化, 收敛性分析

Abstract: 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.

Key words: multi-block ADMM, non-convex optimization, convergence analysis

中图分类号:

O221

王庆阳, 袁梓航, 杨嘉玟, 孔翔玉, 陈彩华. 非凸优化中交替方向乘子法的收敛性研究[J]. 运筹学学报（中英文）, 2026, 30(3): 99-115.

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.

[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.

非凸优化中交替方向乘子法的收敛性研究

On the convergence of the alternating direction method of multipliers for non-convex optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 14

编辑推荐

Metrics

本文评价

[1]	贾泽慧, 李丹丹, 肖玉娇, 岳素云. 一种基于方差缩减的联邦对称交替方向乘子法[J]. 运筹学学报（中英文）, 2026, 30(3): 116-132.
[2]	金柱石, 甘涛, 徐玲玲. 基于Peaceman-Rachford分裂的广义纳什均衡问题的分布式算法[J]. 运筹学学报（中英文）, 2026, 30(3): 73-98.
[3]	魏佳祯, 边伟. 共识优化算法的研究进展综述[J]. 运筹学学报（中英文）, 2026, 30(1): 1-23.
[4]	谭子琳, 罗洪林. 二阶分裂算法及其应用[J]. 运筹学学报（中英文）, 2025, 29(4): 121-140.
[5]	曾静, 丁若文. 一类带映射差的非凸向量优化问题解的稳定性[J]. 运筹学学报, 2023, 27(3): 121-128.
[6]	彭建文, 雷宏旺. 非凸两分块优化问题的一类惯性对称正则化交替方向乘子法[J]. 运筹学学报, 2023, 27(3): 37-52.
[7]	吕袈豪, 罗洪林, 杨泽华, 彭建文. 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用[J]. 运筹学学报, 2022, 26(2): 16-30.
[8]	胡佳, 郭田德, 韩丛英. 小批量随机块坐标下降算法[J]. 运筹学学报, 2022, 26(1): 1-22.
[9]	徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.
[10]	陈彩华. 多块交替方向乘子法不收敛反例的几点注记[J]. 运筹学学报, 2019, 23(3): 135-140.
[11]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79-92.
[12]	张勇, 叶万洲. 一种求解弹性l_2-l_q正则化问题的算法[J]. 运筹学学报, 2016, 20(4): 11-20.
[13]	党亚峥, 薛中会. 凸可行问题的平行近似次梯度投影算法[J]. 运筹学学报, 2015, 19(1): 117-124.
[14]	钱小燕, 施庆生, 刘浩, 石岿然. 大规模无约束优化的一族有限存储LBFGS类算法[J]. 运筹学学报, 2011, 15(3): 9-18.