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

Lasso：f(x)=12|Ax−b|22，于是利用ADMM算法，x-update的解析解就是xk+1=(ATA+ρI)−1(ATb+ρ(zk−uk))；于是x-update看起来是个岭回归了，因此ADMM对于lasso可以看做迭代的使用岭回归。至于矩阵求逆那些，利用之前的矩阵小技巧解决。Generalized lasso：这个问题可能不是那么为众人所熟悉，他是Tibs的儿子搞出来的框罗类似fusedlasso这种事先定义好的线性变化的惩罚项的模型，损失函数是平方损失，而惩罚变成了一个特殊的参数线性组合

min12∥Ax−b∥22+λ∥Fx∥1⟹1d fusedlasso,A=IFij=⎧⎩⎨⎪⎪1−10j=i+1j=iotherwise

⟹min12∥x−b∥22+λ∑i=1n−1|xi+1−xi|⟹A=I,F二阶差分矩阵，则被称作L1 trendfiltering

若将上述这种写成ADMM形式，同样可以放到ADMM算法框架中解决

mins.t.12∥Ax−b∥22+λ∥z∥1Fx−z=0⟹xk+1zk+1uk+1=(ATA+ρFTF)−1(ATb+ρFT(zk−uk))=S1/ρ(Axk+1−b+uk)=uk+Fxk+1−zk+1−b

Group lasso：graph lasso问题应用比较广，对不同组的参数同时进行惩罚，进行一组组参数的挑选，故曰grouplasso。不同于lasso，其正则项变成了∑Ni=1|xi|2,xi∈Rni，lasso其实是grouplasso的一种特殊形式。正则项并不是完全可分的。此时只是z-update变成了block的软阈值形式

zk+1i=Sλ/rho(xk+1i+uk),i=1,…,N⟹Sk(a)=(1−k∥a∥2)+a,S(0)=0

这种形式还可以扩展到group间有重合的情况，即化成N可能存在重合的组Gi⊆1,…,n。一般来说这种问题会非常难解决，但是对于ADMM算法只需要换下形式就很直接（x,z互换，会变成后面非常重要的一致性优化问题（consensusoptimization），局部xi与全局真解z子集z^i的对应。）

mins.t.12∥Az−b∥22+λ∑i=1N∥xi∥2,xi∈R|Gi|xi−z^i=0,i=1,…,N

Sparse Gaussian graphmodel：对于稀疏高斯图，熟悉该问题的人知道这其实是lasso的图上的推广，损失函数写成似然函数的负数即可l(x)=tr(SX)−logdetX,X∈Sn++。于是原来向量的操作就变成了矩阵操作，ADMM算法也有点变化：

Xk+1Zk+1Uk+1=argminX(tr(SX)−logdetX+ρ2∥X−Zk+Uk∥F)=argminZ(λ∥Z∥1+ρ2∥Xk+1−Z+Uk∥F)=Uk+Xk+1−Zk+1

上述算法继续化简，对于z-update做逐个元素软阈值操作即可Zk+1ij=Sλ/ρ(XK+1ij+Ukij)。对于x-update也类似操作，直接求导一阶导为0，移项后对对称矩阵做特征值分解即可

ρX−X−1=ρ(Zk−Uk)−S=QΛQT,QQT=I,Λ=diag(λ1,…,λn)→ρX^−X^−1=Λ,X^=QTXQ

由于Λ是对角阵，对于每个对角元素来说，上述问题就是解一个二次方程，解方程后，再将X^变化成X即可

X^ii=λi+λ2i+4ρ−−−−−−√2ρ⟹X=QX^QT

总之，上述跟ℓ1相关的问题，基本都可以纳入ADMM框架，并且可以快速求解。

4. Consensus and Sharing本节讲述的两个优化问题，是非常常见的优化问题，也非常重要，我认为是ADMM算法通往并行和分布式计算的一个途径：consensus和sharing，即一致性优化问题与共享优化问题。

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