|
|
目录
1.问题模型
2.增广拉格朗日函数
3.算法流程
4.ADMM求解lasso问题
<hr/>1. 问题模型
交替方向乘子法（Alternating Direction Method of Multipliers）通常用于解决存在两个优化变量的只含等式约束的优化类问题，其一般形式为：
\begin{aligned} &\min_{x,z}\ \ f(x)+g(z) \\ &s.t. \ \ Ax + Bz = c \end{aligned}\\
其中， x\in R^n,z\in R^m 是优化变量，等式约束中 A\in R^{p \times n},B\in R^{p \times m},c\in R^p 。 f 和 g 都是凸函数。
交替方向乘子法被广泛地应用在信号处理、图像处理、机器学习、工程计算等各个领域中，具有收敛速度快，收敛性能好的优势。 2. 增广拉格朗日函数（Augmented Lagrangian）
为解决此类凸优化问题，定义增广拉格朗日函数：
L_\rho(x,z,u) = f(x) + g(z) + u^T(Ax+Bz-c)+\frac{\rho}{2}||Ax+Bz-c||_2^2\\
增广拉格朗日函数就是在关于原问题的拉格朗日函数（关于拉格朗日函数，可以参考【凸优化笔记6】-2.2节拉格朗日函数）之后增加了一个和约束条件有关的惩罚项，惩罚项中参数 \rho > 0 。 3. 算法流程
每一步只更新一个变量而固定另外两个变量，如此交替重复更新。即，对于 k=1,2,3,... ，重复如下步骤：
\begin{aligned} &step1:\ \ x^{(k)}=arg \min_xL_\rho(x,z^{(k-1)},u^{(k-1)})\\ &step2:\ \ z^{(k)}=arg \min_zL_\rho(x^{(k)},z,u^{(k-1)})\\ &step3:\ \ u^{(k)}=u^{(k-1)}+\rho(Ax^{(k)}+Bz^{(k)}-c) \end{aligned}\\
第一步先固定 z 和 u ， L_\rho 是只关于 x 的函数，用使得 L_\rho 最小的一点来更新 x ；第二步固定 u 和更新过的 x ，L_\rho 是只关于 z 的函数，用使得 L_\rho 最小的一点来更新 z ；第三步用更新过的 x 和 z 来更新 u 。不断重复以上三步直到收敛（在不太强的假设前提下，算法可以保证收敛）。 ADMM 算法提供了一个将多优化变量问题转化为单优化变量问题的转化方式（即，交替方向），并未涉及具体的下降方法，其中关于 x 和 z 的更新过程需要结合具体的下降类算法，如梯度下降算法等。
为简化形式，如果令 w=\frac{u}{\rho} ,则增广拉格朗日函数可以写成：
L_\rho(x,z,w) = f(x) + g(z) +\frac{\rho}{2}||Ax+Bz-c+w||_2^2 -\frac{\rho}{2}||w||_2^2\\
上面这个式子被称为是 ADMM 的缩放形式。
推导过程：
\begin{aligned} L_\rho(x,z,w) &= f(x) + g(z) + \rho w^T(Ax+Bz-c)+\frac{\rho}{2}||Ax+Bz-c + w - w||_2^2\\ &= f(x) + g(z) + \rho w^T(Ax+Bz-c)+\frac{\rho}{2}\{||Ax+Bz-c + w||_2^2 + ||w||_2^2 - 2w^T(Ax+Bz-c + w)\}\\ &= f(x) + g(z) +\frac{\rho}{2}||Ax+Bz-c+w||_2^2 +\frac{\rho}{2}||w||_2^2 - \rho||w||_2^2\\ &=f(x) + g(z) +\frac{\rho}{2}||Ax+Bz-c+w||_2^2 -\frac{\rho}{2}||w||_2^2\\ \end{aligned} 相应地，更新步骤变为：
\begin{aligned} &step1:\ \ x^{(k)}=arg \min_x\ f(x) + \frac{\rho}{2}||Ax+Bz^{(k-1)}-c+w^{(k-1)}||_2^2\\ &step2:\ \ z^{(k)}=arg \min_z\ g(z) + \frac{\rho}{2}||Ax^{(k)}+Bz-c+w^{(k-1)}||_2^2\\ &step3:\ \ w^{(k)}=w^{(k-1)}+Ax^{(k)}+Bz^{(k)}-c \end{aligned}\\
注意到，此时的 w^{(k)}=w^{(0)}+\sum_{i=1}^{k}{(Ax^{(i)}+Bz^{(i)}-c)} 。即，第 k 次迭代的 w^{(k)} 等于其初值 w^{(0)} 加上约束条件残差的累加和。 4. ADMM求解lasso问题
考虑 lasso 问题： \min_{\beta}\ \frac{1}{2}||y-X\beta||_2^2 + \lambda||\beta||_1\\
重写为： \begin{aligned} &\min_{\beta,\alpha}\ \frac{1}{2}||y-X\beta||_2^2 + \lambda||\alpha||_1\\ &\ s.t.\ \ \beta-\alpha=0\\ \end{aligned}\\
构造增广拉格朗日函数：
L_\rho(\beta,\alpha,u)=\frac{1}{2}||y-X\beta||_2^2 + \lambda||\alpha||_1+u^T(\beta-\alpha)+\frac{\rho}{2}||\beta-\alpha||_2^2\\
更新步骤：
首先求 \beta 的更新值。由 L_\rho 对 \beta 是可导的，直接令 \frac{\partial L}{\partial\beta}=0 ，有 \begin{aligned} &\frac{\partial L}{\partial\beta}=-X^T(y-X\beta)+u+\rho(\beta-\alpha)=0\\ \Rightarrow\ &\beta=(X^TX+\rho I)^{-1}(X^Ty+\rho\alpha-u)\\ \Rightarrow\ &\beta=(X^TX+\rho I)^{-1}(X^Ty+\rho(\alpha-w))\\ \end{aligned}\\
I 为单位矩阵。矩阵求导的几个常用公式可见【凸优化笔记3】-第 5 节-几个常用公式 然后求 \alpha 的更新值。
\begin{aligned} arg \min_\alpha L_\rho(\beta,\alpha,u)&=arg \min_\alpha \ \{\ \lambda||\alpha||_1+u^T(\beta-\alpha)+\frac{\rho}{2}||\beta-\alpha||_2^2\ \}\\ &=arg \min_\alpha \ \{\ \lambda||\alpha||_1+u^T(\beta-\alpha)+\frac{\rho}{2}||\beta-\alpha||_2^2\ \} \times \frac{2}{\rho} \\ &=arg \min_\alpha \ \{\ \frac{2\lambda}{\rho}||\alpha||_1 + ||\frac{u}{\rho} + (\beta-\alpha)||_2^2 - ||\frac{u}{\rho}||_2^2 \ \}\\ &=arg \min_\alpha \ \{\ \frac{2\lambda}{\rho}||\alpha||_1 + ||\alpha -(\frac{u}{\rho} + \beta)||_2^2\ \}\\ &=S_{\frac{\lambda}{\rho}}(\frac{u}{\rho} + \beta) = S_{\frac{\lambda}{\rho}}(w + \beta) \end{aligned}\\
其中最后一步用到了软阈值公式，可参考【凸优化笔记4】-4.3 软阈值算子 综上，lasso 问题总的更新策略为：
\begin{aligned} &\beta^{(k)}=(X^TX+\rho I)^{-1}(X^Ty+\rho(\alpha^{(k-1)}-w^{(k-1)}))\\ &\alpha^{(k)}=S_{\frac{\lambda}{\rho}}(w^{(k-1)}+\beta^{(k)})\\ &w^{(k)}=w^{(k-1)}+\beta^{(k)}-\alpha^{(k)} \end{aligned}\\
参考文献：
CMU凸优化课件-admm |
|
窥视卡
雷达卡
发表于 2022-11-4 18:08
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡