一种加速的广义交替方向乘子法

An Accelerated Generalized Alternating Direction Method of Multipliers

针对一类特殊的凸优化问题,原始交替方向乘子法收敛较慢,为改善算法的收敛速度,一种加速交替方向乘子法被提出,但是该算法可能会使对偶变量更新步长变得很小,影响算法效果.基于此,本文提出一种加速的广义交替方向乘子法,通过应用Chambolle和Pock提出的惩罚参数更新规则,证明了所提算法在一定假设条件下的全局收敛性以及建立起了在遍历情况下的最坏Ο(1/n^2)收敛率.

The convergence rate of the original alternating direction method of multipliers is slower for a class of special convex optimization problems.In order to improve the convergence rate of the algorithm,recently,an accelerated alternating direction method of multipliers has been proposed,but the algorithm may make the dual variable update step becomes too small and affects the algorithm effect.Based on this,an accelerated generalized alternating direction method of multipliers is proposed in this paper.We applying a rule proposed recently by Chambolle and Pock to iteratively update the penalty parameter and show that the global convergence of the iterative sequence generated by the proposed algorithm,and the worst-case Ο(1/n^2) convergence rate in the ergodic sense is established.