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

• 作 者: YeYingyu;
• 机 构: Stanford University
• 出 处: 第八届工业与应用数学国际大会
• 发表日期: 2015年期

　　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.