优化算法-3｜增广拉格朗日函数(ALM)及其优化方法-ADMM算法、AMA算法

要理解本章知识，需要有拉格朗日函数定义和对偶性的知识前提。

我们先回顾一下

拉格朗日函数法：

对于一般性约束问题，

我们可以将其改写为

思考：拉格朗日算法的缺陷？

为了便于理解，推导更容易，我们先仅考虑等式约束(equality constraints)。

考虑等式约束问题：

其拉格朗日函数形式为:

Recall： 对偶性

要对 进行优化，我们可以通过对偶性，利用上下界在优化点相等的特性来求解，即

(1)

显然的，为了最大化其下界， 的值将是 ，除非 。

因此， 函数非常不光滑(highly nonsmooth), 想要对这个拉格朗日函数估计是非常困难的。

因为拉格朗日函数的求解非常困难，我们希望有一些办法，其优化结果与拉格朗日函数相同，但是优化过程是光滑的。

我们可以尝试增加一个罚项(penality term，也有叫"proximal point" term)。

假设已经存在一个 的先验估计(prior estimation) 。

通过引入一个罚项，

将(1)改为

(2)

这时， 就比较容易优化了（一个二次凹函数），利用Newton-Step进行迭代：

(3)

Recall: 对偶性。 （此处理解有困难请回顾 优化算法-1|拉格朗日函数和对偶性）

将 (3)代入 (2) 得

(4)

即为 拉格朗日增广函数。

（5）

• 更新 ；
• 利用(2) 更新 ;
• 重复直到收敛。

伪代码( pseudo code)：

for i=1,...,k,...,T（i=T时收敛）:

考虑不等式(inequality constraints)约束问题：

（6）

前文中，不等式约束的拉格朗日乘子常使用 表示，这里为了便于理解（希望能够更容易看出不等式约束与等式约束的区别），系数也使用 表示。

Recall: KKT条件--- dual feasbility, 。

（6）的 拉格朗日函数与(1)相比，增加了 的限制：

因此， 的更新公式相比（3），也要增加此限制：

(7)

然而，(7) 看起来也不是那么容易求，我们还是希望能够转化成(3)的形式，让求解的方法与上文提到的等式约束时保持一致。

Recall， 等式约束问题:

不等式约束问题写作：

为了方便处理，我们可以让不等式约束以类似等式约束的形式表示：

因此，不等式约束问题的增广拉格朗日函数为

(8)

其优化过程为

for i=1,...,k,...,T（i=T时收敛）:

为什么需要ADMM算法

观察式(8)发现，其原始目标函数 （primal object function）包含(x,s)两个参数，为了处理这个情况，我们可以引入ADMM算法，对这两个参数交替优化，就可以解决双参数优化的问题。

ADMM算法说明

考虑目标问题为

其增广拉格朗日函数为

尽管 是看起来分离(separable)的两个优化目标，然而我们增加的罚项"proximal point" term是一个二次(quadratic)的，让这部分减小需要同时优化(x,z)，他俩就关联起来了，此处有疑问的请自行了解f(x,z)的梯度下降。

所以我们可以分别的依次的（separately and sequentially）优化 x和z:

for i=1,...,k,...,T（i=T时收敛）:

.

如此，我们就可以的对不等式约束问题的增广拉格朗日(8)进行优化。

有时候，要直接找到 也是比较困难的，我们可以尝试使用 梯度下降的办法 来逐步逼近，于是有：

for i=1,...,k,...,T（i=T时收敛）:

.

这里 是梯度下降的学习率。

for i=1,...,k,...,T（i=T时收敛）:

.

与ADMM算法的区别是，在更新 x时令z为0.

参考资料：

1. Standford, CS229 Lecture Notes5----Part V ：http://cs229.stanford.edu/notes2021fall/cs229-notes3.pdf
2. CMU Statistics, Convex Optimization----Karush-Kuhn-Tucker Conditions ：http://stat.cmu.edu/~ryantibs/convexopt/lectures/kkt.pdf
3. 学弱猹制作的课件, SVM: An Application of KKT Conditions: Li Liu - Personal Website
4. University of Rochester, CSC 576: Alternating Direction Method for Multipliers (ADMM): https://www.cs.rochester.edu/u/jliu/CSC-576/class-note-11.pdf
5. University of Wisconsin-Madison, Augmented Lagrangian Methods: http://pages.cs.wisc.edu/~swright/nd2016/IMA_augmentedLagrangian.pdf