Abstract:

We focus on the convergence analysis of the extended linearized alternating directionmethod of multipliers(L-ADMM)for solving convex minimization problems with three or more separable blocks in the objective functions. Previous convergence analysis of the L-ADMM needs to reduce the multi-block convex minimization problems to two blocks by grouping the variables. Moreover, there has been no rate of convergence analysis for the L-ADMM. In this paper, we construct a counter example to show the failure of convergence of the extended L-ADMM. We prove the convergence and establish the sublinear convergence rate of the extended L-ADMM under the assumptions that the proximal gradient step sizes are smaller than certain values, and any two coefficient matrices in linear constraints are orthogonal.

Key words: Separable convex minimization ·, Alternating direction method of multipliers ·, Linearization ·, Sublinear convergence