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

x+=argminx(f(x)+(ρ/2)∥x−v∥22)=ΠC(v)

投影与惩罚参数ρ无关。若f是非负象限Rn+的投影，则直接有x+=(v)+。

下面再谈谈上述提到的三种一般形式的优化问题。

（1）Quadratic Objective Terms

假设f是如下（凸）的二次函数

f(x)=12xTPx+qTx+r

P是对称的半正定矩阵P∈Sn+。这种形式问题也包含了f是线性或者常数的特殊情况。若P+ρATA可逆，那么x-update步求个导即有如下的显示解，是v的仿射函数

x+=(P+ρATA)−1(ρATv−q)

因此在x-minnimiztion步只需要做两个矩阵运算即可，求逆与乘积，选用合适的线性运算库即可以得到不错的计算性能。当然还可以利用一些矩阵分解技巧，这个要看矩阵大小和稀疏程度。因为对于Fx=g，可以将F=F1F2⋯Fk，然后Fizi=zi−1,z1=F−11g,x=zk，这样会更节省计算时间。其他矩阵计算技巧，基本都是如何对矩阵求解，利用矩阵的稀疏性、缓存分解等来提高性能。此处不赘述，有个很重要的求逆的定理很有用：

(P+ρATA)−1=P−1−ρP−1AT(I+ρAP−1AT)−1AP−1

如果对于上述二次函数受限于某仿射集x-update步就更复杂些，如

f(x)=12xTPx+qTx+rdormf={x∥Fx=g}

x-update还有个重要的KKT方程可用：

(P+ρIFFT0)(xk+1v)+(q−ρ(zk−uk)−g)=0

（2）Smooth Objective Terms

当f光滑时，那么求导即成为可能了。对于一些非线性优化问题，包含梯度算法等方法的L-BFGS算法可以用。对于该算法有些小技巧如下：

早终止（early termination）：当f(x)+(ρ/2)|Ax−v|22梯度很小时，早点终止迭代，否则后面就很慢了。热启动（warm start）：即启动迭代时，利用之前迭代过的值带入即可。

（3）Separable objective and constraints可分函数和约束对于并行计算和分布式计算来说是一个好消息。如果ATA是分块的对角阵，那么约束中|Ax|22也是可分的，则扩增的拉格朗日函数Lρ也是可分的。（注意，此处是指函数中的参数可分成小子块，而不是说数据可分。）下面有一个很重要的例子，即softthresholding（针对l1+l2问题）:

当f(x)=λ|x|1,λ>0，并且A=I时，那么x-update就变成了

x+=argminx(λ∥xi∥+(ρ/2)∥x−v∥22)

这种形式很常见在目前的高维统计中，虽然第一项在0处不可导，但是也有解析解，被称作软阈值（softthresholding），也被称作压缩算子（shrinkage operator）。

x+i=Sλ/ρ(vi),→Sk(a)=⎧⎩⎨⎪⎪a−k0,a+k,a>k|a|≤ka<−k→Sk(a)=(1−k|a|)+a

在优化领域，软阈值被称作是ℓ1-norm问题的近邻算子（proximity operator）。

3. 一些具体优化应用3.1受约束的凸优化问题 一般的受约束的凸优化问题可以写成如下形式

mins.tf(x)x∈C

此类问题可以写成ADMM形式

mins.tf(x)+g(z)x−z=0⟹Lρ(x,z,u)=f(x)+g(z)+(ρ/2)∥x−z+u∥22

其中的g函数即C的示性函数，上述是scaled形式，那么具体算法就是

xk+1zk+1uk+1=argmin(f(x)+(ρ/2)∥x−zk+uk∥22)=ΠC(xk+1+uk)=uk+xk+1−zk+1

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