放松邻近步长的线性化逐块交替方向乘子法
|
摘要
交替方向乘子法(ADMM)是求解线性约束凸优化问题的算法之一,其只有在两块变量时才有收敛性保证.为处理多块问题可将多块变量分为两组,组间采用Gauss-Seidel格式(及时利用新信息),组内采用Jacobi格式(使用老的信息),该算法的子问题求解较为困难.韩德仁等对子问题目标函数线性化并增加邻近点项来简化计算,但该算法的邻近点项因子选取受每组变量约束矩阵的最大特征值限制,使得收敛速度较慢,现提出新参数条件的线性化逐块ADMM算法,改进韩德仁等算法中的邻近因子,在保持每步计算量不变的前提下使算法收敛速度大大加快.
AlternatingDirection Method of Multipliers(ADMM)is one of the algorithms for solving convex optimization problems with linear constraints.Its convergence is guaranteed only when there are two block variables.In order to deal with multi-block problems,multi-block variables can be divided into two groups.Gauss-Seidel fashion is used between groups(using new information in time)and Jacobi format is used within groups(using old information).It is difficult to solve the sub-problems of the algorithm.Henderen et al.simplify the calculation by linearizing the objective function of the sub-problem and adding the proximal point terms.However,the selection of the proximal point terms of the algorithm is limited by the maximum eigenvalue of the constraint matrix of each group of variables,which makes the convergence speed slow.A blockwise ADMM algorithm with relaxed parameter conditions is proposed to improve the proximal factors in the algorithm such as Han Deren et al.The convergence speed of the algorithm is greatly accelerated while the amount of computation per step remains unchanged.
AlternatingDirection Method of Multipliers(ADMM)is one of the algorithms for solving convex optimization problems with linear constraints.Its convergence is guaranteed only when there are two block variables.In order to deal with multi-block problems,multi-block variables can be divided into two groups.Gauss-Seidel fashion is used between groups(using new information in time)and Jacobi format is used within groups(using old information).It is difficult to solve the sub-problems of the algorithm.Henderen et al.simplify the calculation by linearizing the objective function of the sub-problem and adding the proximal point terms.However,the selection of the proximal point terms of the algorithm is limited by the maximum eigenvalue of the constraint matrix of each group of variables,which makes the convergence speed slow.A blockwise ADMM algorithm with relaxed parameter conditions is proposed to improve the proximal factors in the algorithm such as Han Deren et al.The convergence speed of the algorithm is greatly accelerated while the amount of computation per step remains unchanged.
引文
[1]ChenCH,HeBS,YeYY and YuanXM,The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent[J].Mathematical Programming,2016,155(1~2):57~79
[2]Chen L,Sun D and Toh K C,An Efficient Inexact Symmetric Gauss-Seidel Based Majorized ADMM for High-Dimensional Convex Composite Conic Programming[J].Mathematical Programming,2017,161(1-2):237~270
[3]HeBS,XuMH and YuanXM,Block-Wise ADMM with a Relaxation Factor for Multiple-Block Convex Programming[J].Journal of the Operations Research Society of China,2018,6(4):485~505
[4]BaiJCand ZhangHC,A One-Parameter Family of Middle Proximal ADMM for Constrained Separable Convex Optimization,manuscript,2018
[5]HeBS,Tao M and YuanXM,A splitting method for separable convex programming[J].Institute of Mathematics and its Applications Journalof Numerical Analysis,2015,35(1):394~426
[6]申远,夏书育,纪磊.一种新参数条件的线性化逐块交替方向乘子法[J].扬州大学学报,审稿中,2018
[2]Chen L,Sun D and Toh K C,An Efficient Inexact Symmetric Gauss-Seidel Based Majorized ADMM for High-Dimensional Convex Composite Conic Programming[J].Mathematical Programming,2017,161(1-2):237~270
[3]HeBS,XuMH and YuanXM,Block-Wise ADMM with a Relaxation Factor for Multiple-Block Convex Programming[J].Journal of the Operations Research Society of China,2018,6(4):485~505
[4]BaiJCand ZhangHC,A One-Parameter Family of Middle Proximal ADMM for Constrained Separable Convex Optimization,manuscript,2018
[5]HeBS,Tao M and YuanXM,A splitting method for separable convex programming[J].Institute of Mathematics and its Applications Journalof Numerical Analysis,2015,35(1):394~426
[6]申远,夏书育,纪磊.一种新参数条件的线性化逐块交替方向乘子法[J].扬州大学学报,审稿中,2018