ALM和ADMM算法：从数值优化到凸优化

mypro334

本文参考公众号“运筹or帷幄”中文章，作者从数值优化和凸优化两个角度对两种算法进行了介绍，在此进行一个系统整理，以便后续学习。之前未曾接触过两个算法，只是看论文时看到了ADMM，想简单入门，因此知识比较基础，理解也比较粗浅，只是基于公众号文章的简单笔记整理。
本文思路为：先从数值优化的角度对两种算法进行初步理解，再从凸优化的角度进行再探，原文链接如下：
需要补充的知识点：

1.从对偶上升法看增强拉格朗日
2.坐标下降中的结尾部分飞灵：凸优化入门2：“运筹OR帷幄”凸优化（10）笔记总结
3.ADPMM（其中涉及到近端梯度法的理解，在凸优化（3）中有所涉及）
4.ADMM的并行应用

一、光滑优化与罚项法


1.光滑优化

光滑优化本质是解决如下问题：



图1 光滑优化

其中 f,c_{i} 均足够光滑。所以在一般的光滑优化里，对于约束和目标函数都没有很明显的形式限制，换句话说这是一个非常一般化的问题

2.罚项法

罚项法的本质是通过罚项来转化优化问题，如对于图1中的光滑优化问题，只需构造如下的函数



图2 罚项法求解

其中 [y]^{-}=max(-y,0) 。即对于不等式约束，只有对应值为负时才会有惩罚，而对于等式约束，只要其非零，就会产生惩罚，可以理解为一旦有“脱轨”的情况产生，就会产生惩罚。这样的处理就使一个有约束问题转化为了无约束问题。
下面的定理说明了该方法的可行性



图3 定理1

如何理解该定理呢？图2中的 \mu 本质上就是惩罚的力度（可以理解为LASSO里的 \lambda ），定理1的含义为，当该惩罚力度为无穷大时（ \mu_{k}\rightarrow \infty ）,求解出的x就是原始带约束问题（图1）的解（即函数的局部极小值点）。
但是该惩罚存在着一定的问题：
（1）即使我们最终做到了梯度趋于0，也就是算法收敛，我们也不一定能够保证收敛到一个可行解，该内容为定理2的含义



图4 定理2

（2）海森矩阵性质差：即使我们的拉格朗日函数的海森矩阵性质很好， \mu_{k} 很大的时候也无济于事，整个海森矩阵的特征值会呈现一个两极分化的状态。换句话说条件数很大，这个在数值优化中是一个大忌。总结一下就是说，对于所有依赖二阶信息的方法，都会呈现出很强的不稳定性

要解决这个问题，有一种方法就是改变罚项的性质，这一点非常像岭回归往LASSO的转换，就是把我们的2-范数罚项修改为1-范数罚项，也就是修改我们的函数为



图5 1-范数惩罚项

修改过后，对应下面的定理成立



图6 定理3

该定理的含义为：我们不需让 \mu 充分大，就可以找到函数的局部极小值点

二、增广拉格朗日方法（ALM）


1.增强拉格朗日函数及算法框架

将2-范数惩罚转化为1-范数惩罚后的优点在于不需 \mu \rightarrow \infty ，但同时函数也不光滑，为极小值求解带来困难，为此我们引入ALM方法。
和之前的罚项法不同的地方在于，它是针对函数对应的拉格朗日函数添加罚项，而不是针对目标函数本身。比方说对于一个等式约束问题


那么它的对应的增强拉格朗日函数就是


可以看出它就是一个拉格朗日函数加上罚项 \frac{\mu}{2}\sum_{i \in{ \varepsilon}}c_{i}^2(x) 的结果。那么这个时候，可以得到的是


注意到当这个点 x^{*} 满足KKT条件时，如果我们设它对应的拉格朗日乘数为 \lambda_{i} ，那么很明显无论 \mu 取多少，都有 \bigtriangledown_{x}L_{A}(x^{*},\lambda^{*};\mu)=0 。因此考虑下面一个迭代



图7 ALM迭代公式

此设计的思路为，一般来讲 x^{*} 是可以迭代且已知的，但 \lambda_{i}^{*} 是未知的，所以对 \lambda 进行迭代
具体的算法操作如下所示：（其中17.39指的是图7中的迭代公式）



图8 ALM算法框架

2.ALM法性质

（1）不需 \mu \rightarrow \infty 就可找到解


（2）只要 \lambda_{k} 足够靠近 \lambda^{*} ， x_{k} 就会足够靠近 x^{*} ，并且每一步迭代都会使得 \lambda_k 与 \lambda^{*} 的差距以线性收敛速度缩小，并且迭代点附近也有LICQ一样的性质。换句话说，我们的增广拉格朗日方法在实操中是可行的，毕竟数值优化算法的误差是不可避免的。


3.从对偶上升法看增强拉格朗日


三、交替方向乘子法（ADMM）


1.定义及算法步骤




图9 ADMM基本问题



图10 ADMM增广拉格朗日函数

对于两个子函数的优化问题，我们的想法就是加上交替下降的思路，即每一次固定一个变量为常数，视作单变量的优化问题。然后再使用增广拉格朗日方法。具体的步骤如下：



图11 ADMM算法步骤

即在第一步固定z为常数，最小化x，在第二步固定x，最小化z，在第三步固定x和z，最小化拉格朗日乘子s（s有的文章里也成为对偶变量）。这里的前两步就是交替下降法（坐标下降，详见：飞灵：凸优化入门2：“运筹OR帷幄”凸优化（10）笔记总结），也就是说每一步固定一个变量，只考虑与另外一个变量有关的项进行优化。第三步就是增广拉格朗日法，一直迭代到收敛为止即可。
ADMM方法的速度不算快（包括局部上的，这也算是一个缺点），如果 f_1,f_2 凸，那么它会有 O（\frac{1}{k}） 的收敛速度。进一步的如果说是 f_1,f_2 强凸的，那么收敛速度就是线性的。但对于一阶方法而言，这已经够了。

2.标准化形式的ADMM（Scaled From ADMM）

（1）notation重述
由于和上面的部分来自于两篇文章，notation稍微有点不同，为了更清晰的理解，先重新说明一下notation



图12-1 问题



图12-2 拉格朗日函数



图12-3 求解步骤

（2）标准化形式的ADMM
如果设 \omega = \frac{u}{\rho} ，图12-2中拉格朗日函数会发生一些改动：



图13 改动后拉格朗日函数

图15来自于经典开平方的逆运算，容易验证是和图12-2等价的。进行图13的改动过后，公式会变成下面的样子：



图14 标准化ADMM算法步骤

这么修改的好处也有一些，一是可以提出一个与 x,z 都无关的项 \frac{\rho}{2}||\omega||_{2}^{2} ，所以优化的时候就可以直接无视它。二是在对 \omega 作更新的时候，其实等价于之前的 u 的更新式子再两边除以一个 \rho 。因此我们会发现在更新 \omega 的时候其实没有所谓的步长的说法了（回顾一下，在对偶上升法中，这个系数的意义就是步长），这也是“标准化形式”这个说法的由来。

3.经典实例1：ADMM求解LASSO问题

（1）普通ADMM求解


要使用ADMM方法，一个很重要的操作就是构造出两个相互不影响的函数。因此我们的想法就是设 Ax-b=z ，所以这样的话问题就会变成


那么如果要使用ADMM，我们的迭代步骤就是:



图15 ADMM求解LASSO过程

这个计算的步骤也存在一些难点。对于第二个子问题，其实它是很容易找到显式解（closed-form）的，毕竟都是二次项，求个梯度然后设为0就好。但是对于第一个子问题， \lambda||x||_{1} 的存在就使得问题的解没有一个固定的形式。不过这个问题也有解决的方案，这就是交替方向近端乘子法（Alternating Direction Proximal Method of Multipliers, ADPMM）。
（2）ADPMM求解
这个方法的思路来源于一阶方法中的近端梯度法，也就是加一个二阶项权重，使得问题的closed-form能够重现。也就是说

（3）标准化ADMM求解






按照ADMM的步骤，可知要对增广拉格朗日函数中先优化β，再优化α。
优化β即要解决如下问题：


其中等号的原因就是将第一步中的平方乘开，去除常数项，整理可得等号后部分
让式子对β求梯度可得


因此不难得到 \beta_{k} 的更新公式，只需代入 a^{(k-1)},\omega^{(k-1)} 即可
得到β的更新公式后，针对α进行优化，即考虑问题



alpha目标函数

其中，去除了 L_p 中很多含β项的原因在于ADMM中坐标下降法的思想，即在更新其中一个变量时，固定另一个变量，因此可将另一个变量看为常数。
α目标函数即为近端梯度法（优化│凸优化（4）——次梯度案例，加速梯度法，随机梯度下降法，近端梯度法引入 example2）的软阈值算子，因此可轻松求解
最终的迭代公式为：


4.经典实例2：ADMM求解2d-fused LASSO问题



这里的2d含义是指两个罚项分别是针对x,y坐标来做的，即 |\Theta_{i,j}-\Theta_{i+1,j}| 代表对x坐标的惩罚， |\Theta_{i,j}-\Theta_{i,j+1}| 代表对y坐标的惩罚
如何将该问题从无约束优化转化为约束优化，再使用ADMM呢？这里有两种思路
（1）设 z=D\theta



注：这里笔者认为约束条件写错了

这样的话可以把ADMM的迭代公式写为


（2）将 \Theta 拆分为 H，V 两个




这里H是一列一列更新，而V是一行一行更新的
5.ADMM的分布式计算

此部分内容参考：
考虑如下问题（Consensus问题）：


即将前面简单问题中仅考虑 f_1,f_2 两个函数相加拓展成 n 个函数相加，求解过程如下：


通过上述迭代可以看出，更新 x_i,v_i 时，至于下标为 i 的变量有关，与 x_j,v_j,f_j(j\ne i) 无关，即 n 个下标索引的计算可以分配到 n 台计算机/线程/进程分别进行计算，只在更新 z ,需要汇总各个计算节点的数据，更新 z 后，再将结果分发到各个节点，从而实现分布式计算