Title: On Convergence of the Multi-Block Alternating Direction Method of Multipliers


Speaker: Yinyu Ye

Date: August 12
Time: 11:10 - 12:10
Room: Ballroom B

Chair: Yaxiang Yuan


Abstract: The alternating direction method of multipliers (ADMM), after a long “silent” period, has recently witnessed a “renaissance” in many application domains, such as signal and imagine processing, statistics analysis, machine learning, engineering computation, etc. The convergence of ADMM was established 40 years ago when two blocks of variables are alternatively updated. It is computationally beneficial to extend the ADMM directly to the case of a multi-block convex minimization problem. However, whether or not the ADMM is convergent was open until very recently. In this survey paper, we summarize recent approaches and results in this pursuit. Mainly, we illustrate an example to show that the direct extension of ADMM is not necessarily convergent with three or more blocks. On the positive side, we present the result that, if in each iteration one randomly and independently permutes the updating order of variable blocks followed by the standard Lagrangian multiplier update, then ADMM will converge in expectation when solving certain convex optimization problems.

Return

Key Features:
Awarding ceremony of ICIAM prizes
Invited lectures
Prize lectures
Industrial Minisymposia
Contributed Minisymposia
Poster sessions
Embedded and satellite meetings
Public outreach sessions
Exhibits