交替方向乘子法（ADMM）

佚名 5年前 (2019-02-25) 随笔 1290人围观抢沙发百度已收录

交替方向乘子法（ADMM）

参考1

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

参考2

经典的ADMM算法适用于求解如下2-block的凸优化问题（交替方向乘子法（ADMM）随笔第6张是最优值，令交替方向乘子法（ADMM）随笔第7张表示一组最优解）：

交替方向乘子法（ADMM）随笔第8张

Block指我们可以将决策域分块，分成两组变量，交替方向乘子法（ADMM）随笔第9张这里面交替方向乘子法（ADMM）随笔第10张交替方向乘子法（ADMM）随笔第11张都是凸的。分成2-block是因为3-block及以上的问题性质会差一点，分析起来不太好说清楚（虽然实际当中基本上几个block都可以用，一般都会收敛...）。

那么我们这里就可以写出这个凸优化问题的增广拉格朗日函数（augmented Lagrangian function）：

交替方向乘子法（ADMM）随笔第12张

注意到这个增广的意思就是在原来的拉格朗日函数后面加了个平方的正则项（系数交替方向乘子法（ADMM）随笔第13张），这个主要是为了不需要交替方向乘子法（ADMM）随笔第14张一定要是严格凸（strictly convex）/值域有限（只要是一般的凸函数就行了）然后也能保证收敛性。然后我们对交替方向乘子法（ADMM）随笔第15张用dual ascent（对偶上升法），或者也就是拉格朗日乘子法就知道可以有这样一个算法形式：

交替方向乘子法（ADMM）随笔第16张

其实dual ascent原理非常简单，本质上来说就是primal variable迭代方向取拉格朗日函数对primal variable的次微分，dual variable迭代方向取拉格朗日函数对dual variable的次微分（这里的话就是交替方向乘子法（ADMM）随笔第17张）。这也是所谓拉格朗日乘子法的一般思路（method of multipliers）。当然这边还有一些细节，比如对偶变量迭代步长选了交替方向乘子法（ADMM）随笔第18张。所以如果你想从基础打起的话，可以从比如S. Boyd and L. Vandenberghe的凸优化书第五章看起。

那么ADMM，也就是所谓“交替方向”的乘子法就是在原基础上（交替方向乘子法（ADMM）随笔第19张一起迭代）改成交替方向乘子法（ADMM）随笔第20张单独交替迭代（如果有更多block也是类似）。即，我们的ADMM算法为

交替方向乘子法（ADMM）随笔第21张

本节最后，我们指出ADMM算法形式的另一种等价形式。如果定义所谓的残差（residual）为交替方向乘子法（ADMM）随笔第22张，那么注意到再定义交替方向乘子法（ADMM）随笔第23张作为所谓scaled dual variable，我们有交替方向乘子法（ADMM）随笔第24张即我们可以改写ADMM算法形式为