非精确广义不定邻近交替方向乘子法的收敛性分析

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

摘要/Abstract

摘要：

交替方向乘子法(ADMM)及其变种广泛应用于求解实际问题, 但其有效性极大地依赖于子问题的求解。本文提出一类求解带线性约束可分凸优化问题的非精确广义不定邻近ADMM, 其中一个子问题运用基于相对误差的非精确准则近似求解, 该准则只涉及简单的调节参数; 另一个子问题引入不定邻近项。新算法继承了相对误差非精确准则和不定邻近项的优势, 能有效提高适用性和求解效率。基于变分不等式框架, 分析了算法的收敛性。通过求解图像恢复问题, 验证了新算法的有效性。

关键词: 凸优化, 广义交替方向乘子法, 非精确, 相对误差准则, 不定邻近项

Abstract:

It is well known that alternating direction method of multipliers (ADMM) and its variants are of the popular methods in solving many practical problems. However, the efficiency of ADMM based methods largely relies on the solvability of the involving subproblems. In this paper, we propose an inexact generalized proximal ADMM with optimal indefinite proximal term to solve the separable convex minimization problem with linear constraints. The relative-error criterion with only one constant belonging in [0, 1) is introduced to solve one of subproblems approximately, and the other subproblem is solved by introducing an optimal indefinite proximal term. The proposed method inherits the advantages of both the relative error criterion and the indefinite proximal term. Based on the variational inequality framework, the convergence of the developed method is rigorously conducted. Some numerical experiments on TV-$\ell $₂ image restoration problem are conducted to illustrate the efficiency of the new method.

Key words: convex optimization, generalized alternating direction method of multipliers, inexact, relative error criterion, indefinite proximal term

中图分类号:

O221.2

宋瑞, 王依冉, 吴中明. 非精确广义不定邻近交替方向乘子法的收敛性分析[J]. 运筹学学报（中英文）, 2025, 29(4): 175-190.

Rui SONG, Yiran WANG, Zhongming WU. Convergence analysis of the inexact generalized alternating direction method of multipliers with indefinite proximal term[J]. Operations Research Transactions, 2025, 29(4): 175-190.

图/表 3

参考文献 34

1	Beck A , Teboulle M . A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2 (1): 183- 202. doi: 10.1137/080716542
2	Candès E J , Recht B . Exact matrix completion via convex optimization[J]. Communications of the ACM, 2012, 55 (6): 111- 119. doi: 10.1145/2184319.2184343
3	Chen S S , Donoho D L , Saunders M A . Atomic decomposition by basis pursuit[J]. SIAM Review, 2001, 43 (1): 129- 159. doi: 10.1137/S003614450037906X
4	Recht B , Fazel M , Parrilo P A . Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J]. SIAM Review, 2010, 52 (3): 471- 501. doi: 10.1137/070697835
5	Tao M , Yuan X . Recovering low-rank and sparse components of matrices from incomplete and noisy observations[J]. SIAM Journal on Optimization, 2011, 21 (1): 57- 81. doi: 10.1137/100781894
6	Tibshirani R J . Regression shrinkage and selection via the Lasso[J]. Journal of the Royal Statistical Society: Series B, 1996, 58, 267- 288. doi: 10.1111/j.2517-6161.1996.tb02080.x
7	Yuan X . Alternating direction method for covariance selection models[J]. Journal of Scientific Computing, 2012, 51 (2): 261- 273. doi: 10.1007/s10915-011-9507-1
8	Gabay D , Mercier B . A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J]. Computers and Mathematics with Applications, 1976, 2 (1): 17- 40. doi: 10.1016/0898-1221(76)90003-1
9	Glowinski R , Marrocco A . Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires[J]. Revue Francaise D'automatique, Informatique, Recherche Opérationnelle. Analyse Numérique, 1975, 9, 41- 76.
10	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.
11	Eckstein J , Wang Y . Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives[J]. Pacific Journal of Optimization, 2015, 11 (4): 619- 644.
12	Glowinski R . On alternating direction methods of multipliers: A historical perspective[J]. Modeling, Simulation and Optimization for Science and Technology, 2014, 34, 59- 82.
13	Gu Y, Jiang B, Han D. A semi-proximal-based strictly contractive Peaceman-Rachford splitting method[EB/OL]. [2022-10-21]. arXiv: 1506.02221
14	Han D . A survey on some recent developments of alternating direction method of multipliers[J]. Journal of the Operations Research Society of China, 2022, 10 (1): 1- 52. doi: 10.1007/s40305-021-00368-3
15	Li X , Mo L , Yuan X , et al. Linearized alternating direction method of multipliers for sparse group and fused Lasso models[J]. Computational Statistics and Data Analysis, 2014, 79, 203- 221. doi: 10.1016/j.csda.2014.05.017
16	Yang J , Yuan X . Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization[J]. Mathematics of Computation, 2013, 82 (281): 301- 329.
17	Han D , Sun D , Zhang L . Linear rate convergence of the alternating direction method of multipliers for convex composite programming[J]. Mathematics of Operations Research, 2018, 43 (2): 622- 637. doi: 10.1287/moor.2017.0875
18	He B , Ma F , Yuan X . Optimal linearized alternating direction method of multipliers for convex programming[J]. Computational Optimization and Applications, 2020, 75 (2): 361- 388. doi: 10.1007/s10589-019-00152-3
19	Li M , Sun D , Toh K C . A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization[J]. SIAM Journal on Optimization, 2016, 26 (2): 922- 950. doi: 10.1137/140999025
20	Gao B , Ma F . Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization[J]. Journal of Optimization Theory and Applications, 2018, 176 (1): 178- 204. doi: 10.1007/s10957-017-1207-z
21	Jiang F , Wu Z , Cai X . Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization[J]. Journal of Industrial and Management Optimization, 2020, 16 (2): 835- 856. doi: 10.3934/jimo.2018181
22	Chen J , Wang Y , He H , et al. Convergence analysis of positive-indefinite proximal ADMM with a Glowinski's relaxation factor[J]. Numerical Algorithms, 2020, 83 (4): 1415- 1440. doi: 10.1007/s11075-019-00731-9
23	Tao M . Convergence study of indefinite proximal ADMM with a relaxation factor[J]. Computational Optimization and Applications, 2020, 77 (1): 91- 123. doi: 10.1007/s10589-020-00206-x
24	Eckstein J , Bertsekas D P . On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[J]. Mathematical Programming, 1992, 55 (3): 293- 318.
25	He B , Liao L , Han D , et al. A new inexact alternating directions method for monotone variational inequalities[J]. Mathematical Programming, 2002, 92, 103- 118. doi: 10.1007/s101070100280
26	Eckstein J , Silva P J . A practical relative error criterion for augmented Lagrangians[J]. Mathematical Programming, 2013, 141 (1-2): 319- 348. doi: 10.1007/s10107-012-0528-9
27	Eckstein J , Yao W . Approximate ADMM algorithms derived from Lagrangian splitting[J]. Computational Optimization and Application, 2017, 68 (2): 363- 405. doi: 10.1007/s10589-017-9911-z
28	Eckstein J , Yao W . Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM[J]. Mathematical Programming, 2018, 170 (2): 417- 444. doi: 10.1007/s10107-017-1160-5
29	Alves M M , Marcavillaca R T . On inexact relative-error hybrid proximal extragradient, forward-backward and Tseng's modified forward-backward methods with inertial effects[J]. Set-Valued and Variational Analysis, 2020, 28 (2): 301- 325. doi: 10.1007/s11228-019-00510-7
30	Jiang F , Cai X , Wu Z , et al. Approximate first-order primal-dual algorithms for saddle point problems[J]. Mathematics of Computation, 2021, 90 (329): 1227- 1262. doi: 10.1090/mcom/3610
31	Jiang F , Wu Z . An inexact symmetric ADMM algorithm with indefinite proximal term for sparse signal recovery and image restoration problems[J]. Journal of Computational and Applied Mathematics, 2023, 417, 114628. doi: 10.1016/j.cam.2022.114628
32	Xie J , Liao A , Yang X . An inexact alternating direction method of multipliers with relative error criteria[J]. Optimization Letters, 2017, 11 (3): 583- 596. doi: 10.1007/s11590-016-1021-9
33	Rudin L I , Osher S , Fatemi E . Nonlinear total variation based noise removal algorithms[J]. Physica D: Nonlinear Phenomena, 1992, 60, 259- 268. doi: 10.1016/0167-2789(92)90242-F
34	He H , Han D , Li Z . Some projection methods with the bb step sizes for variational inequalities[J]. Journal of Computational and Applied Mathematics, 2012, 236, 2590- 2604. doi: 10.1016/j.cam.2011.12.017

		$ \tau=\frac{3.01+\alpha}{4} $				$ \tau=1 $
	$ \alpha $	Iter.	Initer.	Time/s	SNR	Iter.	Initer.	Time/s	SNR
House	$ -0.3 $	23	1 833	5.70	24.72	26	2 192	6.43	24.72
	$ 0 $	18	1 750	5.26	24.72	22	1 935	5.53	24.72
	$ 0.3 $	16	1 689	4.62	24.72	19	1 858	5.14	24.72
Man	$ -0.3 $	20	2 304	16.61	16.61	24	2 552	19.14	16.61
	$ 0 $	18	2 240	15.30	16.61	22	2 354	16.77	16.61
	$ 0.3 $	17	1 926	13.52	16.61	18	2 148	14.53	16.61

[1]	谭子琳, 罗洪林. 二阶分裂算法及其应用[J]. 运筹学学报（中英文）, 2025, 29(4): 121-140.
[2]	孟辛晴, 张文星. 求解一类线性等式约束凸优化问题的加速方法[J]. 运筹学学报（中英文）, 2024, 28(1): 1-17.
[3]	曾静, 丁若文. 一类带映射差的非凸向量优化问题解的稳定性[J]. 运筹学学报, 2023, 27(3): 121-128.
[4]	彭建文, 雷宏旺. 非凸两分块优化问题的一类惯性对称正则化交替方向乘子法[J]. 运筹学学报, 2023, 27(3): 37-52.
[5]	吕袈豪, 罗洪林, 杨泽华, 彭建文. 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用[J]. 运筹学学报, 2022, 26(2): 16-30.
[6]	胡佳, 郭田德, 韩丛英. 小批量随机块坐标下降算法[J]. 运筹学学报, 2022, 26(1): 1-22.
[7]	徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.
[8]	李红武, 谢敏, 张榕. 一类非光滑凸优化问题的邻近梯度算法[J]. 运筹学学报, 2021, 25(1): 61-72.
[9]	郭科, 王涛, 张有才. 广义黏性逼近方法及其应用[J]. 运筹学学报, 2020, 24(3): 127-140.
[10]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79-92.
[11]	何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31.
[12]	何斯迈, 金羽佳, 王华, 葛冬冬. 在线学习方法综述: 汤普森抽样和其他方法[J]. 运筹学学报, 2017, 21(4): 84-102.
[13]	张勇, 叶万洲. 一种求解弹性l_2-l_q正则化问题的算法[J]. 运筹学学报, 2016, 20(4): 11-20.
[14]	王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, 2016, 20(2): 105-112.
[15]	何炳生. 修正乘子交替方向法求解三个可分离算子的凸优化[J]. 运筹学学报, 2015, 19(3): 57-70.