On the O(1/t) convergence rate of Ye–Yuan’s modified alternating direction method of multipliers

摘要

The alternating direction method of multipliers (ADMM) is known to be a classic and efficient method for constrained optimization problem with two blocks of variables, and its empirical efficiency has been well illustrated in various fields. Specially, for improving its speed performance, Ye and Yuan suggested to do an additional extension with an optimal step size on the variables after each iteration of the primary ADMM. Indeed, the numerical experiments indicate that this modified ADMM improves the speed performance of the ADMM by around 40% without changing the algorithmic framework much. Recently, the O(1/t) convergence rate of the primary ADMM is established. Inspired by its idea, in this paper, we show that this improved ADMM also has O(1/t) convergence rate. The reason that larger γ yields better speed performance is also investigated and explained.