On the Optimal Step-size Selection for the Alternating Direction Method of Multipliers*

The alternating direction method of multipliers is a powerful technique for structured large-scale optimization that has recently found applications in a variety of fields including networked optimization, estimation, compressed sensing and multi-agent systems. While applications of this technique have received a lot of attention, there is a lack of theoretical support for how to set the algorithm parameters, and its step-size is typically tuned experimentally. In this paper we consider three different formulations of the algorithm and present explicit expressions for the step-size that minimizes the convergence rate. We also compare our method with one of the existing step-size selection techniques for consensus applications.