The alternating direction method of multipliers (ADMM) was proposed by Glowinski and Marrocco in 1975; and it has been widely used in a broad spectrum of areas, especially in some sparsity-driven application domains. In 1982, Fortin and Glowinski suggested to enlarge the range of the step size for updating the dual variable in ADMM from $1$ to $(0,\frac{1+\sqrt{5}}{2})$; and this strategy immediately accelerates the convergence of ADMM for most of its applications. Meanwhile, Glowinski raised the question of whether or not the range can be further enlarged to $(0,2)$; this question remains open with nearly no progress in the past decades. In this paper, we answer this question affirmatively for the case where both the functions in the objective are quadratic. Glowinski's open question is thus partially answered. We further establish the global linear convergence of the ADMM with the step size range $(0,2)$ for the quadratic programming case under a condition that turns out to be tight.
Article
View On Glowinski's Open Question of Alternating Direction Method of Multipliers