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

imal）等价于最大化对偶函数（dual），两者会同时达到optimal。这种转化可以将原来很多的参数约束条件变得少了很多，以利于做优化。具体表述如下：

mins.t.f(x)Ax=b⟹L(x,y)=f(x)+yT(Ax−b)⟹对偶函数（下界）g(y)=infxL(x,y)

在强对偶性的假设下，primal和dual问题同时达到最优。

x⋆=argminxL(x,y⋆)

因此，若对偶函数g(y)可导，便可以利用梯度上升法，交替更新参数，使得同时收敛到最优。迭代如下：

xk+1:yk+1:=argminxL(x,yk)(x-最小化步)=yk+αk∇g(y)=yk+αk(Axk+1−b)(对偶变量更新，αk是步长)

当g不可微的时候也可以将其转化下，成为一个所谓的subgradient的方法，虽然看起来不错，简单证明下即可知道xk和yk同时可达到optimal，但是上述条件要求很苛刻：f(x)要求严格凸，并且要求α选择有比较合适。一般应用中都不会满足（比如f(x)是一个非零的仿射函数），因此dualascent不会直接应用。

1.2 Dual Decomposition 虽然dualascent方法有缺陷，要求有些严格，但是他有一个非常好的性质，当目标函数f是可分的（separable）时候（参数抑或feature可分），整个问题可以拆解成多个子参数问题，分块优化后汇集起来整体更新。这样非常有利于并行化处理。形式化阐述如下：

mins.t.f(x)=∑i=1Nfi(xi),xi∈Rni,x∈RnAx=∑i=1NAixi=b,(对A矩阵按列切分开)⟹L(x,y)=∑i=1NLi(xi,y)=∑i=1N(fi(xi)+yTAixi−1NyTb)

因此可以看到其实下面在迭代优化时，x-minimization步即可以拆分为多个子问题的并行优化，对偶变量更新不变这对于feature特别多时还是很有用的。

xk+1i:yk+1:=argminxLi(xi,yk)(多个xi并行最小化步)=yk+αk∇g(y)=yk+αk(Axk+1−b)(汇集整体的x，然后对偶变量更新)

对偶分解是非常经典的优化方法，可追溯到1960年代。但是这种想法对后面的分布式优化方法影响较大，比如近期的graph-structure优化问题。

1.3 Augmented Lagrangians and the Method of Multipliers 从上面可以看到dualascent方法对于目标函数要求比较苛刻，为了放松假设条件，同时比较好优化，于是就有了AugmentedLagrangians方法，目的就是放松对于f(x)严格凸的假设和其他一些条件，同时还能使得算法更加稳健。

Lρ(x,y)=f(x)+yT(Ax−b)+ρ2∥Ax−b∥22⟹mins.t.f(x)+ρ2∥Ax−b∥22Ax=b

从上面可以看到该问题等价于最初的问题，因为只要是可行解对目标函数就没有影响。但是加了后面的(ρ/2)∥Ax−b∥22惩罚项的好处是使得对偶函数gρ(y)=infxLρ(x,y)在更一般的条件下可导。计算过程与之前的dualascent基本一样，除了最小化x时候加了扩增项。

xk+1yk+1=argminxLρ(x,yk)=yk+ρ(Axk+1−b)

上述也称作method ofmultipliers，可能也是因为更新对偶变量y时步长由原来变化的αk转为固定的ρ了吧。该算法在即使f(x)不是严格凸或者取值为+∞情况都可以成立，适用面更广。同样可以简单证明primal变量x和对偶变量y可以同时达到最优。

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