分布式计算python_经典分布式计算模型_并行分布式计算(2)

2. Alternating Direction Method of Multipliers(ADMM)2.1 ADMM算法概述为了整合dual ascent可分解性与methodmultiplers优秀的收敛性质，人们就又提出了改进形式的优化ADMM。目的就是想能分解原函数和扩增函数，以便于在对f更一般的假设条件下并行优化。ADMM从名字可以看到是在原来Methodof Multipliers加了个AlternatingDirection，可以大概猜想到应该是又想引入新变量，然后交叉换方向来交替优化。形式如下：

mins.t.f(x)+g(z)Ax+Bz=c⟹Lρ(x,z,y)=f(x)+g(z)+yT(Ax+Bz−c)+(ρ/2)∥Ax+Bz−c∥22

从上面形式确实可以看出，他的思想确实就是想把primal变量、目标函数拆分，但是不再像dualascent方法那样，将拆分开的xi都看做是x的一部分，后面融合的时候还需要融合在一起，而是最先开始就将拆开的变量分别看做是不同的变量x和z，同时约束条件也如此处理，这样的好处就是后面不需要一起融合x和z，保证了前面优化过程的可分解性。于是ADMM的优化就变成了如下序贯型迭代（这正是被称作alternatingdirection的缘故）：

xk+1zk+1yk+1=argminxLρ(x,zk,yk)=argminzLρ(xk+1,z,yk)=yk+ρ(Axk+1+Bzk+1−c)

后面我们可以看到这种拆分思想非常适合统计学习中的ℓ1-norm等问题：loss +regulazition（注意：一定要保证z分解出来，ADMM借助的就是用一个z变量来简化问题，不管他是约束还是其他形式也罢，需要构造一个z出来，后体到细节问题我们会有更深的体会）。

为了简化形式，ADMM有一个scaledform形式，其实就是对对偶变量做了scaled处理。先定义每一步更新的残差为r=Ax+Bz−c，于是稍加计算

yT(Ax+Bz−c)+(ρ/2)∥Ax+Bz−c∥22=yTr+(ρ/2)∥r∥22=(ρ/2)∥r+(1/ρ)y∥22−(1/2ρ)∥y∥22=(ρ/2)∥r+u∥22−(ρ/2)∥u∥22

此处u=(1/ρ)y称为scaled dualvariable，并令每一步迭代的残差为rk=Axk+Bzk−c，以及累计残差uk=u0+∑kj=1rj，于是ADMM形式就可以简化为如下形式

xk+1zk+1uk+1=argminxLρ(x,zk,yk)=argmin(f(x)+(ρ/2)∥Ax+Bzk−c+uk∥22)=argminzLρ(xk+1,z,yk)=argmin(g(z)+(ρ/2)∥Axk+1+Bz−c+uk∥)=uk+ρ(Axk+1+Bzk+1−c)

写成这种形式有利于后面简化优化问题，当然可以不作任何处理。

2.2 ADMM算法性质和评价 （1）收敛性

关于收敛性，需要有两个假设条件：

f和g分别是扩展的实数函数Rn(Rm)→R⋃+∞，且是closed、proper和convex的；扩增的lagrangian函数L0有一个鞍点（saddle point）；对于约束中的矩阵A,B都不需要满秩。

在此两个假设下，可以保证残差、目标函数、对偶变量的收敛性。

Note：实际应用而言，ADMM收敛速度是很慢的，类似于共轭梯度方法。迭代数十次后只可以得到一个acceptable的结果，与快速的高精度算法（Newton法，内点法等）相比收敛就慢很多了。因此实际应用的时候，其实会将ADMM与其他高精度算法结合起来，这样从一个acceptable的结果变得在预期时间内可以达到较高收敛精度。不过一般在应用问题中，高精度的参数解对于预测效果没有很大的提高，因此实际应用中，短时间内一个acceptable的结果基本就可以直接应用预测了。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-34812-2.html