Convergence study on the symmetric version of admm with larger step sizes

Abstract

© 2016 Society for Industrial and Applied Mathematics. The alternating direction method of multipliers (ADMM), also well known as a special split Bregman algorithm in imaging, is being popularly used in many areas including the image processing field. One useful modification is the symmetric version of the original ADMM, which updates the Lagrange multiplier twice at each iteration and thus the variables are treated in a symmetric manner. The symmetric version of ADMM, however, is not necessarily convergent. It was recently found that the convergence of symmetric ADMM can be suficiently ensured if both the step sizes for updating the Lagrange multiplier are shrunk conservatively. Despite the theoretical significance in ensuring convergence, however, smaller step sizes should be strongly avoided in practice. On the contrary, we actually have the desire of seeking larger step sizes whenever possible in order to accelerate the numerical performance. Another technique leading to numerical acceleration of ADMM is enlarging its step size by a constant originally proposed by Fortin and Glowinski. These two numerically favorable techniques are commonly but usually separately used in ADMM literature, and intuitively they seem to be incompatible in combination with the symmetric ADMM due to the conflict between the theoretical role in ensuring the convergence with smaller step sizes and the empirical necessity in accelerating numerical performance with larger step sizes. It is thus open whether the ADMM scheme in combination with these two techniques simultaneously is convergent. We answer this question affirmatively in this paper and rigorously show the convergence of the symmetric version of ADMM with step sizes that can be enlarged by Fortin and Glowinski's constant. We thus move forward to the counterintuitive understanding that shrinking both the step sizes is not necessary for the symmetric ADMM. We conduct the convergence analysis by specifying a step size domain that can ensure the convergence of symmetric ADMM; some known results in the ADMM literature turn out to be special cases of our discussion. Since the step sizes can be enlarged by constants that are problem-independent and the strategy is applicable to the general iterative scheme when the generic setting of the model is considered, our theoretical study provides an easily implementable strategy to accelerate the ADMM numerically which can be immediately applied to a variety of applications including some standard image processing tasks.