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

则上述x−min就变成了一个具体的受约束的优化问题。比如对于经典的二次规划问题(QP)

mins.t12xTPx+qTxAx=b,x≥0

写成ADMM形式

mins.tf(x)+g(z)x−z=0⟹f(x)g(z)=12xTPx+qTx,dormf={x|Ax=b}=I(ΠRn+(z))

即受约束的区域就是{x∣x≥0}，g是向非负象限投影的示性函数。而x-update就变成了之前在Quadratic ObjectiveTerms中谈到的f(x)有仿射集定义域的优化问题，根据KKT条件即可写出来x-update更新的形式，参见2.3节。

如果上述对x限制不是限制x≥0上，而是一个锥约束（conicconstraint）x∈K，那么x-update不变，继续上述KKT方程，而只需要变一下z-update，将向Rn+投影改成向K投影。比如将上述约束改成{Ax=b,x∈§n+}，即x属于半正定空间，那么向(S^n_{+})投影就变成了一个半正定问题，利用特征值分解可以完成。这种受约束的凸优化问题的形式化对后续许多问题，特别是我们很关注的ℓ1-norm问题很重要，基本上都是转化成这种形式来直接应用ADMM算法，所以这里要好好把握其核心思想和形式。

虽然我对优化不在行，但是感觉优化问题还是挺有意思的，下面是一个经典问题，即找到两个非空凸包的交集中的一点。该算法都可以追溯到1930年代的Neumann交替投影算法（alternatingprojections algorithm）：

xk+1zk+1=ΠC(zk)=ΠD(xk+1)

ΠC,ΠD分别是两个集合的欧式空间投影。写成ADMM形式就是

xk+1zk+1uk+1=ΠC(zk−uk)=ΠD(xk+1+uk)=uk+xk+1−zk+1

上述问题还可推广至找到N个非空凸包交集中一个点的问题，这样其实在x步是可以并行来做的，于是就有

xk+1izk+1uk+1i=ΠAi(zk−uki)=1N∑i=1N(xk+1i+uki)=uki+xk+1i−zk+1⟹ui收敛均趋向于0,zk+1=x¯k+1xk+1iuk+1i=ΠAi(x¯k−uki)=uki+(xk+1i−x¯k+1)

3.2 ℓ1-norm问题高维统计理论的发展，如果要追溯起来我觉得可以从Lasso解法算起，类似的思想在往前追可能是Huber相关的工作。是对于lasso问题，由于当年大家还没搞清楚lasso和boosting之间关系，对于sparsity性质不了解，谁也不知道如何很好地解决这个问题。直到后面Efron提出了LARS算法，对两者的路径解相似性做了很好的阐述，于是后面关于变量选择，关于basis-pursuit，compressedsensing，sparse graphical models等各种新问题的产生，随后各种优化算法也随之涌现出来，诸如GradientProjection， Proximal methods，ADMM (Alternating Direction Method ofMultipliers)， (Split) Bregman methods，Nesterov’smethod。不过要能够部署ℓ1-norm的解决方案，那么这些算法中ADMM可能是首选。此处ℓ1-norm问题并不仅仅指Lasso问题，包含了多种ℓ1-norm类型问题。下面均介绍下。

之所以说ADMM适合机器学习和统计学习的优化问题，因为大部分机器学习问题基本都是“损失函数+正则项”形式，这种分法恰好可以套用到ADMM的框架f(x)+g(z)。因此结合ADMM框架基本可以解决很多已有的问题，以及利用ℓ1-norm构造的新的优化问题。下面将先介绍非分布式计算的版本，后面会单开一节来介绍如何分布式计算。

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