[1]申远,孔玉倩,纪磊.一种新参数条件的线性化逐块交替方向乘子法[J].徐州工程学院学报(自然科学版),2020,(02):23-32.
 SHEN Yuan,KONG Yuqian,JI Lei.A New Linearized Blockwise Alternating Direction MultiplierMethod with Parameter Conditions[J].Journal of Xuzhou Institute of Technology(Natural Sciences Edition),2020,(02):23-32.
点击复制

一种新参数条件的线性化逐块交替方向乘子法()
分享到:

《徐州工程学院学报》(自然科学版)[ISSN:1674-358X/CN:32-1789/N]

卷:
期数:
2020年02期
页码:
23-32
栏目:
理论研究
出版日期:
2020-07-04

文章信息/Info

Title:
A New Linearized Blockwise Alternating Direction MultiplierMethod with Parameter Conditions
文章编号:
1674-358X(2020)02-0023-10
作者:
申远孔玉倩纪磊
(南京财经大学 应用数学学院,江苏 南京210023)
Author(s):
SHEN YuanKONG YuqianJI Lei
(School of Applied Mathematics,Nanjing University of Finance & Economics,Nanjing 210023,China)
关键词:
交替方向乘子法 逐块交替方向乘子法 线性化 多块
Keywords:
alternating direction multiplier method(ADMM) blockwise ADMM linearization multi-block
分类号:
O221.2; O224
文献标志码:
A
摘要:
交替方向乘子法(ADMM)是求解2块变量线性约束优化问题的一种有效算法,在多领域广泛应用.但是直接将此方法推广到多块变量的情况时,若无额外假设,算法不一定收敛.该文基于线性化逐块 ADMM 算法,放松了算法中邻近因子的取值范围,在保持子问题容易求解的前提下,使算法收敛速度加快,并得到实验验证.
Abstract:
Alternating direction multiplier method(ADMM)is an effective algorithm for solving linear constrained optimization problems of two variables,and is widely used in many fields.However,if this method is directly extended to the case of multi-block variables,the algorithm may not converge without additional assumptions.Based on the linearized block-by-block ADMM algorithm,this paper relaxes the value range of adjacent factors in the algorithm,and accelerates the convergence speed of the algorithm on the premise of keeping the subproblems easy to solve,which has experimentally verified.

参考文献/References:

[1] 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èmes de Dirichlet nonlinéaires[J].Re-vue Francaise Dautomatique,Informatique,Recherhe Operationnelle.Analyse Numerique,1975,9(2):41-76.
[2] GABAY D,MERCIER B.A dual algorithm for the solution of nonlinear variational problems via finite element approximations[J].Computers & Mathematics with Applications,1976,2(1):17-40.
[3] LIN F,JOVANOVIC M R,GEORGIOU T T.An ADMM algorithm for matrix completion of partially known state covariances[J].Decision & Control,2013:1684-1689.
[4] WANG Y L,YANG J F,YIN W T,et al.A new alternating minimization algorithm for total variation image reconstruction[J].SIAM Journal on Imaging Sciences,2008,1(3):248-272.
[5] SHEN Y,WANG H Y.New augmented Lagrangian-based proximal point algorithm for convex optimization with equality constraints[J].Journal Optimization Theory and Application,2016,171:251-261.
[6] BOYD S,PARIKH N,CHU E,et al.Distributed optimization and statistical learning via the alternating direction method of multipliers[J].Found Trends Mach Learning,2011,3(1):1-122.
[7] ECKSTEIN J,BERTSEKAS D.On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[J].Mathematical Programming,1992,55(1/2/3):293-318.
[8] HE B S,LIAO L Z,HAN D R,et al.A new inexact alternating directions method for monotone variational inequalities[J].Mathematical Programming,2002,92(1):103-118.
[9] YE C H,YUAN X M.A descent method for structured monotone variational inequalities[J].Optimization Methods & Software,2007,22(2):329-338.
[10] CHAN R H,TAO M,YUAN X M.Linearized alternating direction method of multipliersfor constrained linear least-squares problem[J].East Asian Journal on Applied Mathematics,2012,2(4):326-341.
[11] HE B S.A customized proximal point algorithm for convex minimization with linear constraints[J].Computational Optimization and Applications,2013,56(3):559-572.
[12] HE B S,YUAN X M.A strictly contractive Peaceman-Rachford splittingmethod for convex programming[J].Siam Journal on Optimization,2014,24,1011-1040.
[13] Zhang X Q,Peng J W.Linearized version of the generalized alternating direction method of multipliers for three-block separable convex minimization problem
[EB/OL].Optimization Online,(2017-09-26)
[2019-11-25].http://www.optimization-online.org/DB_HTML/2017/09/6225.html.
[14] SUN H C,TIAN M Y,SUN M.The symmetric ADMM with indefinite proximal regularization and its application[J]. Journal of Inequalities and Applications,2017,2017:172.
[15] CHEN C H,HE B S,YE Y Y,et al.The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent[J].Mathematical Programming,2016,155(1/2):57-79.
[16] HAN D R,YUAN X M.A note on the alternating direction method of multipliers[J].Journal of Optimization Theory & Applications,2012,155(1):227-238.
[17] HONG M Y,LUO Z Q.On the linear convergence of the alternating direction method of multipliers[J].Mathematical Programming,2017,162:165-199.
[18] CHEN C H,SHEN Y,YOU Y F.On the convergence analysis of the alternating direction method of multipliers with three blocks[J],Abstract & Applied Analysis,2013,2013(r-2):1-13.
[19] HE B S,TAO M,YUAN X M.Alternating direction method with Gaussian back substitution for separable convex programming[J].Siam Journal on Optimization,2012,22(2):313-340.
[20] LI X D,SUN D F,TOH K C.A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions[J].Mathematical Programming,2016,155:333-373.
[21] HAN D R,KONG W W,ZHANG W X.A partial splitting augmented Lagrangian method for low patch-rank image decomposition[J].Journal of Mathematical Imaging & Vision,2014,51:145-160.
[22] HE B S,TAO M,YUAN X M.A splitting method for separable convex programming[J].IMA Journal of Numerical Analysis,2015,35(1):394-426.
[23] HE B S,YUAN X M.Block-wise alternating direction method of multipliers for multipleblock convex programming and beyond[J].SMAI-Journal of computational mathematics,2015,1:145-174.
[24] HE B S,TAO M,XU M H,YUAN X M.An alternating direction-based contraction method for linearly constrained separable convex programming problems[J].Optimization,2013,62(4):573-596.
[25] HE B S,XU M H,YUAN X M.Block-wise ADMM with a relaxation factor for multiple-block convex programming[J].Journal of the Operations Research Society of China,2018,6:485-505.
[26] HE B S,HOU L S,YUAN X M.On full Jacobian Decomposition of the Augmented Lagrangian method for separable convex programming[J].Siam Journal on Optimization,2015,25(4):2274-2312.
[27] Bai J C,Zhang H C.A One-parameter family of middle proximal ADMM for constrained separable convex optimization
[EB/OL].Optimization Online,(2017-09-11)
[2019-11-27].http://www.optimization-online.org/DB_HTML/2017/11/6319.html.
[28] CHAO M T,CHENG C Z,LIANG D Y.A proximal block minimization method of multipliers with a substitution procedure[J].Optimization Methods & Software,2015,30(4):825-842.
[29] WANG K,HAN D R,XU L L.A parallel splitting method for separable convex programs[J].Journal of Optimization Theory & Applications,2013,159(1):138-158.
[30] HOU L S,HE H J,YANG J F.A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA[J].Computational Optimization & Applications,2016,63:273-303.
[31] WANG J J,SONG W.An algorithm twisted from generalized ADMM for multi-block separable convex minimization models[J].Journal of Computational & Applied Mathematics,2017,309:342-358.
[32] WU Z M,CAI X J,HAN D R.Linearized block-wise alternating direction method of multipliers for multiple-block convex programming[J].Journal of Industrial & Management Optimization,2018,14(3):833-855.
[33] CHANG X K,LIU S Y,ZHAO P J,et al.Convergent prediction-correction-based ADMM for multi-block separable convex programming[J].Journal of Computational & Applied Mathematics,2018,335:270-288.
[34] SUN M,SUN H C.Improved proximal ADMM with partially parallel splitting for multi-block separable convex programming[J].Journal of Applied Mathematics & Computing,2018,58(1/2):151-181.
[35] SUN M,SUN H C,WANG Y J.Two proximal splitting methods for multi-block separable programming with applications to stable principal component pursuit[J].Journal of Applied Mathematics & Computing,2017,56(1/2):411-438.

备注/Memo

备注/Memo:
收稿日期:2020-01-07基金项目:国家社会科学基金项目(19AZD018,19BGL205,17BTQ063); 江苏省社会科学基金项目(18GLA002)作者简介:申远(1982-),男,副教授,博士,硕士生导师,主要从事最优化理论与算法方面的研究.
更新日期/Last Update: 2020-07-04