非凸多分块优化的Bregman ADMM的收敛率研究

Research on the Convergence Rate of Bregman ADMM for Nonconvex Multiblock Optimization

Wang等提出了求解带线性约束的多块可分非凸优化问题的带Bregman距离的交替方向乘子法(Bregman ADMM),并证明了其收敛性.该文将进一步研究求解带线性约束的多块可分非凸优化问题的Bregman ADMM的收敛率,以及算法产生的迭代点列有界的充分条件.在效益函数的Kurdyka-Lojasiewicz (KL)性质下,该文建立了值和迭代的收敛速率,证明了与目标函数相关的各种KL指数值可获得Bregman ADMM的三种不同收敛速度.更确切地说,该文证明了如下结果:如果效益函数的KL指数θ=0,那么由Bregman ADMM生成的序列经过有限次迭代后收敛;如果θ∈(0,1/2),那么Bregman ADMM是线性收敛的;如果θ∈(1/2,1),那么Bregman ADMM是次线性收敛的.

Wang et al proposed the alternating direction method of multipliers with Bregman distance(Bregman ADMM)for solving multi-block separable nonconvex optimization problems with linear con-straints,and proved its convergence.In this paper,we will further study the convergence rate of Bregman ADMM for solving multi-block separable nonconvex optimization problems with linear constraints,and the sufficient conditions for the boundedness of the iterative point sequence generated by the algorith-m.Under the Kurdyka-Lojasiewicz property of benefit function,this paper establish the convergence rates for the values and iterates,and we show that various values of KL-exponent associated with the objective function can obtain Bregman ADMM with three different convergence rates.More precisely,this paper proves the following results:if the(KE)exponent of the benefit function=O,then the sequence generated by Bregman ADMM converges in a finite numbers of iterations;if θ∈(0,1/2),then Bregman ADMM is linearly convergent;if θ∈(0,1/2),then Bregman ADMM is sublinear convergent.