On the global linear convergence of the ADMM with multi-block variables. submitted

The alternating direction method of multipliers (ADMM) has been widely used for solving struc-tured convex optimization problems. In particular, the ADMM can solve convex programs that minimize the sum of N convex functions with N-block variables linked by some linear constraints. While the convergence of the ADMM for N = 2 was well established in the literature, it remained an open problem for a long time whether or not the ADMM for N ≥ 3 is still convergent. Recently, it was shown in [3] that without further conditions the ADMM for N ≥ 3 may actually fail to converge. In this paper, we show that under some easily verifiable and reasonable conditions the global linear convergence of the ADMM when N ≥ 3 can still be assured, which is important since the ADMM is a popular method for solving large scale multi-block optimization models and is known to perform very well in practice even when N ≥ 3. Our study aims to offer an explanation for this phenomenon