Optimization Online


On Glowinski's Open Question of Alternating Direction Method of Multipliers

Tao Min(taom***at***nju.edu.cn)
Yuan Xiaoming (xmyuan***at***hkbu.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 )


Download: [PDF]

Entry Submitted: 06/17/2017
Entry Accepted: 06/17/2017
Entry Last Modified: 06/17/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society