我和乘子交替方向法20年

摘要

1997年,交通网络分析方面的问题把作者引进乘子交替方向法(ADMM)的研究领域.近10年来,原本用来求解变分不等式的ADMM在优化计算中被广泛采用,影响越来越大.这里总结了20年来我们在ADMM方面的工作,特别是近10年ADMM在凸优化分裂收缩算法方面的进展.梳理主要结果,说清来龙去脉.文章利用变分不等式的形式研究凸优化的ADMM类算法,论及的所有方法都能纳入一个简单的预测-校正统一框架.在统一框架下证明算法的收缩性质特别简单.通读,有利于了解ADMM类算法的概貌.仔细阅读,也许就掌握了根据实际问题需要构造分裂算法的基本技巧.也要清醒地看到,ADMM类算法源自增广拉格朗日乘子法(ALM)和邻近点(PPA)算法,它只是便于利用问题的可分离结构,并没有消除ALM和PPA等一阶算法固有的缺点.%My research on ADMM dates back to 1997 when I considered the problems from traffic network analysis.Over the last 10 years,the ADMM based on variational inequalities is widely used in optimization.This paper summarizes our research on ADMM over the last 20 years,particularly,the developments in splitting and contraction methods based on ADMM for convex optimization over the last 10 years.We list the main results as well as the motivations.Our analysis is based on the variational inequalities.All methods mentioned fall in a simple unified prediction-correction framework,in which the convergence analysis is quite simple.A through reading will acquaint you with the ADMM,while a more carefully reading may make you familiar with the tricks on con structing splitting methods according to the problem you met.We should notice that the ADMM originates from ALM and PPA,which are good at utilizing the splitting structure.However,it also inherits the intrinsic shortcomings of these first order methods.