- On Glowinski's Open Question of Alternating Direction Method of Multipliers Tao Min(taomnju.edu.cn) Yuan Xiaoming (xmyuanhkbu.edu.hk) Abstract: 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. Keywords: Alternating direction method of multipliers, Glowinski's open question, quadratic programming, step size, linear convergence Category 1: Applications -- OR and Management Sciences Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF]Entry Submitted: 06/17/2017Entry Accepted: 06/17/2017Entry Last Modified: 06/17/2017Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.