从等式约束的最小化问题说起

《从等式约束的最小化问题说起》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、从等式约束的最小化问题说起：                                                                                        上面问题的拉格朗日表达式为：                                              也就是前面的最小化问题可以写为：                                              minxmaxyL(x,y) 。它对应的对偶问题为：                                      

2、       maxy minxL(x,y) 。下面是用来求解此对偶问题的对偶上升迭代方法：                                    这个方法在满足一些比较强的假设下可以证明收敛。 为了弱化对偶上升方法的强假设性，一些研究者在上世纪60年代提出使用扩展拉格朗日表达式（augmentedLagrangian）代替原来的拉格朗日表达式：                                  其中ρ>0。对应上面的对偶上升方法，得到下面的乘子法（methodofmultipliers）：                        

3、                              注意，乘子法里把第二个式子里的αk改成了扩展拉格朗日表达式中引入的ρ。这不是一个随意行为，而是有理论依据的。利用L(x,y)可以导出上面最小化问题对应的原始和对偶可行性条件分别为（∂L∂y=0，∂L∂x=0）：                                               既然xk+1 最小化 Lρ(x,yk)，有：                                        上面最后一个等式就是利用了yk+1=yk+ρ(Axk+1−b)。从上面可知，这种yk+1

4、的取法使得(xk+1,yk+1)满足对偶可行条件∂L∂x=0。而原始可行条件在迭代过程中逐渐成立。 乘子法弱化了对偶上升法的收敛条件，但由于在x-minimization步引入了二次项而导致无法把x分开进行求解（详见[1])。而接下来要讲的AlternatingDirectionMethodofMultipliers(ADMM)就是期望结合乘子法的弱条件的收敛性以及对偶上升法的可分解求解性。ADMM求解以下形式的最小化问题：                                              其对应的扩展拉格朗日表达式为：             

5、        ADMM包括以下迭代步骤：                                        ADMM其实和乘子法很像，只是乘子法里把x和z放一块求解，而ADMM是分开求解，类似迭代一步的Gauss-Seidel方法。其中(3.4)中的推导类似于乘子法，只是使用了zk+1最小化Lρ(xk+1,z,yk)：                                       其中用到了z对应的对偶可行性式子：                                                   ∂L∂z=∇g(z)+BTy

6、=0 定义新变量u=1ρy，那么(3.2-3.4)中的迭代可以变为以下形式：                           在真正求解时通常会使用所谓的over-relaxation方法，也即在z和u中使用下面的表达式代替其中的Axk+1：                                         αkAxk+1−(1−αk)(Bzk−c)，其中αk为relaxation因子。有实验表明αk∈[1.5,1.8]可以改进收敛性([2])。 下面让我们看看ADMM怎么被用来求解大型的机器学习模型。所谓的大型，要不就是样本数太多，或者样本的维数太高

7、。下面我们只考虑第一种情况，关于第二种情况感兴趣的读者可以参见最后的参考文献[1,2]。样本数太多无法一次全部导入内存，常见的处理方式是使用分布式系统，把样本分块，使得每块样本能导入到一台机器的内存中。当然，我们要的是一个最终模型，它的训练过程利用了所有的样本数据。常见的机器学习模型如下：                                    minimize x∑Jj=1fj(x)+g(x)，其中x为模型参数，fj(x)对应第j个样本的损失函数，而g(x)为惩罚系数，如g(x)=

8、

9、x

10、

11、1。 假设把J个样本分成N份，每