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

KaaPexei · 发表于 2021-12-4 15:32

背景知识

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

拉格朗日函数法(Lagrangian Multipliers)

我们先回顾一下
拉格朗日函数法：
对于一般性约束问题，

$\begin{align} {\rm object: }\ \ \ \ &{\min f(x)} \\ {\rm s.t.} \quad &h_i(x)= 0, \ &(i=1,2,...,m) \\ &\mathcal{G}_j(x) \leq 0,\ & (j=1,2,...,k)\\ \end{align}$
我们可以将其改写为

$\begin{equation} \mathcal{L}(x,\lambda,\mu)=f(x)+ \sum_{i=1}^m \lambda_i h_i(x) +\sum_{j=1}^k \mu_j\mathcal{G}_j(x) \end{equation}$

思考：拉格朗日算法的缺陷？
为了便于理解，推导更容易，我们先仅考虑等式约束(equality constraints)。
考虑等式约束问题：

$\begin{align} {\rm object: }\ \ \ \ &{\min f(x)} \\ {\rm s.t.} \quad &Ax=b \ \end{align}$
其拉格朗日函数形式为:

$\mathcal{L}(x,\lambda):=f(x)+\lambda^T(Ax-b)$
Recall：对偶性
要对  进行优化，我们可以通过对偶性，利用上下界在优化点相等的特性来求解，即

$\min_x \max_\lambda f(x)+\lambda^T(Ax-b)$ (1)
显然的，为了最大化其下界，  的值将是 $+\infty$ ，除非 $Ax-b=0$ 。
因此，函数非常不光滑(highly nonsmooth), 想要对这个拉格朗日函数估计是非常困难的。
增广拉格朗日函数法(ALM)

因为拉格朗日函数的求解非常困难，我们希望有一些办法，其优化结果与拉格朗日函数相同，但是优化过程是光滑的。
我们可以尝试增加一个罚项(penality term，也有叫&#34;proximal point&#34; term)。
假设已经存在一个  的先验估计(prior estimation) $\bar{\lambda}$ 。
通过引入一个罚项， $\frac{1}{2\rho}||\lambda-\bar{\lambda}||^2$
将(1)改为

$\min_x \Big \lbrace \max_\lambda f(x)+\lambda^T(Ax-b)-\frac{1}{2\rho}||\lambda-\bar{\lambda}||^2 \Big\rbrace$ (2)
这时，  就比较容易优化了（一个二次凹函数），利用Newton-Step进行迭代：

$\lambda = \bar{\lambda}+\rho(Ax-b)$ (3)
Recall: 对偶性。（此处理解有困难请回顾优化算法-1|拉格朗日函数和对偶性）
将 (3)代入 (2) 得

$\min_x f(x)+{\bar{\lambda}}^T(Ax-b)+\frac{\rho}{2}||Ax-b||^2 = \min_x\mathcal{L}(x,\bar{\lambda};\rho)$ (4)

$\mathcal{L}(x,\lambda;\rho)$   即为 拉格朗日增广函数。

$\mathcal{L}(x,\lambda;\rho) = f(x)+\lambda^T(Ax-b)+\frac{\rho}{2}||Ax-b||^2$ （5）
增广拉格朗日函数(ALM)的优化过程(optimal process):

$\min_x\mathcal{L}(x,\bar{\lambda};\rho)$ $\rightarrow$ 更新 $x$ ；
利用(2) 更新 $\bar{\lambda}$ ;
重复直到收敛。

伪代码( pseudo code)：
for i =1,...,k,...,T（i=T时收敛）:

$x_k = \arg\min_x \mathcal{L}(x,\lambda_{k-1};\rho);$

$\lambda_k=\lambda_{k-1}+\rho(Ax_k-b)$

ALM与不等式约束

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

$\begin{align} {\rm object: }\ \ \ \ &{\min f(x)} \\ {\rm s.t.} \quad &Ax\geq b \ \end{align}$ （6）
前文中，不等式约束的拉格朗日乘子常使用 $\mu$ 表示，这里为了便于理解（希望能够更容易看出不等式约束与等式约束的区别），系数也使用 表示。
Recall: KKT条件--- dual feasbility, 。
（6）的拉格朗日函数与(1)相比，增加了  的限制：

$\min_x \max_{\lambda\geq0}f(x)+\lambda^T(Ax-b)$
因此， 的更新公式相比（3），也要增加此限制：

$\lambda = \max \Big ( \bar{\lambda}+\rho(Ax-b),0 \Big )$   (7)
然而，(7) 看起来也不是那么容易求，我们还是希望能够转化成(3)的形式，让求解的方法与上文提到的等式约束时保持一致。

Recall，等式约束问题:

$\min_x f(x) \quad {\rm s.t.} \ \ c(x) =0$
不等式约束问题写作：

$\min_x f(x) \quad {\rm s.t.} \ \ c(x)\geq0$
为了方便处理，我们可以让不等式约束以类似等式约束的形式表示：

$\min_x f(x) \quad {\rm s.t.} \ \ c(x)=s, \ s\geq0$

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

$\mathcal{L}(x,s,\bar{\lambda};\rho) = f(x)+\lambda^T(c(x)-s)+\frac{\rho}{2}||c(x)-s||_2^2$   (8)
其优化过程为
for i =1,...,k,...,T（i=T时收敛）:

$（x_k，s_k) = \arg\min_{x,s} \mathcal{L}(x,s,\lambda_{k-1};\rho); \ s.t. \ s\geq0$

$\lambda_k=\lambda_k-1+\rho \big (c(x_k)-s_k\big )$

ADMM算法(Alternating Direction Method of Multipliers)

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

$\begin{align} {\rm object: }\ \ \ \ &{\min_{(x,z)} f(x)}+h(z) \\ {\rm s.t.} \quad &Ax+Bz=c \ \end{align}$
其增广拉格朗日函数为

$\mathcal{L}(x,z,{\lambda};\rho) = f(x)+h(z)+\lambda^T(Ax-Bz-c)+\frac{\rho}{2}||Ax-Bz-c||_2^2$
尽管   $x,z$ 是看起来分离(separable)的两个优化目标，然而我们增加的罚项&#34;proximal point&#34;  term是一个二次(quadratic)的，让这部分减小需要同时优化(x,z)，他俩就关联起来了，此处有疑问的请自行了解f(x,z)的梯度下降。
所以我们可以分别的依次的（separately and sequentially）优化 x和z:
for i =1,...,k,...,T（i=T时收敛）:

$x_k = \arg\min_x \mathcal{L}(x,z_{k-1},\lambda_{k-1};\rho);$

.

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

ADMM算法的变体(A Variant of ADMM)

有时候，要直接找到 $\arg\min$ 也是比较困难的，我们可以尝试使用梯度下降的办法来逐步逼近，于是有：
for i =1,...,k,...,T（i=T时收敛）:

$x_k = x_{k-1}-\alpha_x\frac{\partial \mathcal{L(x,z_{k-1},\lambda_{k-1};\rho)}}{\partial x}$

$z_k = z_{k-1}-\alpha_z\frac{\partial \mathcal{L(x_k,z,\lambda_{k-1};\rho)}}{\partial z}$

.
这里 $\alpha$ 是梯度下降的学习率。

AMA算法

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

$x_k = \arg\min_x \mathcal{L}(x,0,\lambda_{k-1};\rho);$

.
与ADMM算法的区别是，在更新 x时令z为0.
<hr/>参考资料：

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

Ilingis · 发表于 2021-12-4 15:39

谢谢博主！请问 admm中的全局一致性中，如果需要求解两个全局变量z，z1是n个x 向量，d是m个y向量，也可以展开吗，约束项写成两个相加，惩罚项两次相加，迭代过程中，依次x,d,z1,z2,乘子吗

APSchmidt · 发表于 2021-12-4 15:40

没太看明白您的问题，z2是啥？如果你是想问多变量的求解，对于同一个约束函数f, 包括多种变量x1, x2, x3是没有问题的，具体的请参考多变量的梯度下降

Doris232 · 发表于 2021-12-4 15:46

太谢谢您了！我昨天打错了，z1是n个x向量，z2是m个d向量。迭代过程应该可以写成第k次的x,d；z1；z2；第k次的乘子miu1，miu2。我昨天想问的是这个。我想这样是可以的吧，谢谢您！

量子计算9 · 发表于 2021-12-4 15:47

太棒了兄弟[笔芯]

redhat9i · 发表于 2021-12-4 15:52

请问（3）带入（2）问什么负号变正号了

APSchmidt · 发表于 2021-12-4 15:58

这里的lambda已经是估计的bar{lambda}，跟前面的约掉了

		自动登录	找回密码
密码			立即注册