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

（2）停止准则

对于ADMM的能到到optimal的条件此处就不做赘述了，与基本的primal和dual feasibility的条件差不多，即各primal variable的偏导和约束条件为0，从最优条件中可以得到所谓的对偶残差（dualresiduals）和初始残差（primal residuals）形式：

sk+1rk+1=ρATB(zk+1−zk)(dualresiduals)=Axk+1+Bzk+1−c(primalresiduals)

相对而言，此处更难把握的其实是停止准则，因为收敛速度问题，要想获得一个还过得去可以拿来用的参数解，那么判断迭代停止还是比较重要的。经典分布式计算模型实际应用中，一般都根据primalresiduals和dual residuals足够小来停止迭代，阈值包含了绝对容忍度（absolutetolerance）和相对容忍度（relativetolerance），设置还是非常灵活和难把握的（貌似网上有不少人吐槽这个停止准则的不靠谱- -！），具体形式如下：

∥sk∥2≤ϵdual∥rk∥2≤ϵpri=n√ϵabs+ϵrel∥ATyk∥2=p√ϵabs+ϵrelmax{∥Axk∥2,∥Bzk∥,∥c∥2}

上面的p√和n√分别是维度和样本量。一般而言，相对停止阈值ϵrel=10−3或者10−4，绝对阈值的选取要根据变量取值范围来选取（咋选的呢？没说额，具体比例都不给说--！）

另外一些细节问题，比如原来惩罚参数ρ是不变的，一些文献也做了一些可变的惩罚参数，目的是为了降低对于惩罚参数初始值的依赖性。不过变动的ρ会导致ADMM的收敛性证明比较困难，因此实际中假设经过一系列迭代后ρ也稳定，边可直接用固定的惩罚参数ρ了。还有其他问题，诸如x与z迭代顺序问题，实际操作下有所有不同，这些不是特别重要之处，可以忽略。其他与ADMM比较相关算法的有dualADMM算法，distributed ADMM算法，还有整合了ADMM与proximal method ofmultiplier的算法

2.3 ADMM一般形式与部分具体应用当构造了ADMM算法中的f,g,A,B后，便可直接应用该算法了。我们会经常遇到如下三种一般形式的问题

二次目标优化项（quadratic objective terms）； 可分的目标函数和约束（separable objectiveand constraints）； 光滑目标函数项（smooth objective terms）。

为下面讨论的方便，下面仅写出x-update的形式，根据ADMM简化形式，z-update对称更新即可：

x+=argminx(f(x)+(ρ/2)∥Ax−v∥22),v=−Bz+c−u

上述更新x时候z和u都定下来，是个常数，z更新时后相同。

Proximity Operator（近邻算子）

上述形式有种特殊情况：当A=I时，即约束条件没有x的线性组合形式，只是对于x的可行区域进行限制。这种问题相当常见，目前统计学习也有不少类似的高维优化问题。此时x-update如下

x+=argminx(f(x)+(ρ/2)∥x−v∥22),v=−Bz+c−u

上述右边可以写成v的函数proxf,ρ(v)被称作带惩罚ρ的f的proximity operator（通常称作proximalminimization，近邻最小化），在变分分析中，还被称作f的Moreau-Yosida正则化。如果f形式很简单，可以写出x-update的解析解，比如f是非空的凸包C上的示性函数，那么x-update就可以直接写成投影形式

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