An alternating direction method of multipliers with a worst-case $O(1/n^2)$ convergence rate

Abstract:

The alternating direction method of multipliers (ADMM) is being widely used for various convex programming models with separable structures arising in many scientific computing areas. The ADMM’s worst-case $O(1/n)$ convergence rate measured by the iteration complexity has been established in the literature when its penalty parameter is a constant, where $n$ is the iteration counter. Research on ADMM’s worst-case $O(1/n^2)$ convergence rate, however, is still in its infancy. In this paper, we suggest applying a rule proposed recently by Chambolle and Pock to iteratively update the penalty parameter and show that the ADMM with this adaptive penalty parameter has a worst-case $O(1/n^2)$ convergence rate in the ergodic sense. Without a strong convexity requirement on the objective function, our assumptions on the model are mild and can be satisfied by some representative applications. We test the least absolute shrinkage and selection operator (LASSO) model and numerically verify the significant acceleration effectiveness of the faster ADMM with a worst-case $O(1/n^2)$ convergence rate. Moreover, the faster ADMM is more favorable than the ADMM with a constant penalty parameter, as the former is much less sensitive to the initial value of the penalty parameter and can sometimes produce very high-accuracy solutions.