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

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_2$ 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.

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

参考文献

[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.
[2] Candès E J, Recht B. Exact matrix completion via convex optimization [J]. Communications of the ACM, 2012, 55(6): 111-119.
[3] Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit [J]. SIAM Review, 2001, 43(1): 129-159.
[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.
[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.
[6] Tibshirani R J. Regression shrinkage and selection via the Lasso [J]. Journal of the Royal Statistical Society: Series B, 1996, 58: 267-288.
[7] Yuan X. Alternating direction method for covariance selection models [J]. Journal of Scientific Computing, 2012, 51(2): 261-273.
[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.
[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 française 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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[23] Tao M. Convergence study of indefinite proximal ADMM with a relaxation factor [J]. Computational Optimization and Applications, 2020, 77(1): 91-123.
[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.
[26] Eckstein J, Silva P J. A practical relative error criterion for augmented Lagrangians [J]. Mathematical Programming, 2013, 141(1-2): 319-348.
[27] Eckstein J, Yao W. Approximate ADMM algorithms derived from Lagrangian splitting [J]. Computational Optimization and Application, 2017, 68(2): 363-405.
[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.
[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.
[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.
[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.
[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.
[33] Rudin L I, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms [J]. Physica D: Nonlinear Phenomena, 1992, 60: 259-268.
[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.