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

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

Abstract

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

CLC Number:

O221.2

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.

Figures/Tables 3

References 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]	Zilin TAN, Honglin LUO. A second-order splitting method with its application [J]. Operations Research Transactions, 2025, 29(4): 121-140.
[2]	Xinqing MENG, Wenxing ZAHNG. An accelerated method for solving a class of linear equality constrained convex optimization [J]. Operations Research Transactions, 2024, 28(1): 1-17.
[3]	Jing ZENG, Ruowen DING. Stability of solutions for a class of non-convex vector optimization problems with mapping differences [J]. Operations Research Transactions, 2023, 27(3): 121-128.
[4]	Jianwen PENG, Hongwang LEI. A class of inertial symmetric regularization alternating direction method of multipliers for nonconvex two-block optimization [J]. Operations Research Transactions, 2023, 27(3): 37-52.
[5]	Jiahao LYU, Honglin LUO, Zehua YANG, Jianwen PENG. A stochastic Bregman ADMM with its application in training sparse structure SVMs [J]. Operations Research Transactions, 2022, 26(2): 16-30.
[6]	Jia HU, Tiande GUO, Congying HAN. Mini-batch stochastic block coordinate descent algorithm [J]. Operations Research Transactions, 2022, 26(1): 1-22.
[7]	XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems [J]. Operations Research Transactions, 2021, 25(3): 74-86.
[8]	Hongwu LI, Min XIE, Rong ZHANG. A proximal gradient method for nonsmooth convex optimization problems [J]. Operations Research Transactions, 2021, 25(1): 61-72.
[9]	GUO Ke, WANG Tao, Zhang Youcai. Generalized viscosity approximation method and its application [J]. Operations Research Transactions, 2020, 24(3): 127-140.
[10]	JIAN Jinbao, LAO Yixian, CHAO Miantao, MA Guodong. ADMM-SQP algorithm for two blocks linear constrained nonconvex optimization [J]. Operations Research Transactions, 2018, 22(2): 79-92.
[11]	HE Bingsheng. My 20 years research on alternating directions method of multipliers [J]. Operations Research Transactions, 2018, 22(1): 1-31.
[12]	HE Simai, JIN Yujia, WANG Hua, GE Dongdong. A survey on online learning methods: Thompson sampling and others [J]. Operations Research Transactions, 2017, 21(4): 84-102.
[13]	ZHANG Yong, YE Wanzhou. An algorithm for elastic l_2-l_q regularization [J]. Operations Research Transactions, 2016, 20(4): 11-20.
[14]	WANG Siqi, XIE Zheng, DAI Li. A kind of inexact parallel splitting method for solving the fairest core in cooperative game [J]. Operations Research Transactions, 2016, 20(2): 105-112.
[15]	HE Bingsheng. Modified alternating directions method of multipliers for convex optimization with three separable functions [J]. Operations Research Transactions, 2015, 19(3): 57-70.

Convergence analysis of the inexact generalized alternating direction method of multipliers with indefinite proximal term

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 34

Related Articles 15

Recommended Articles

Metrics

Comments