  


On Glowinski's Open Question of Alternating Direction Method of Multipliers
Tao Min(taomnju.edu.cn) 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 sparsitydriven 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/2017 Modify/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  