压缩感知与稀疏模型——Augmented Lagrange Multipler(ALM)
这个博客将介绍ALM，介绍一个用来解决一个等式限制的问题的框架。
考虑下面的问题： \[ \begin{array}{ll}{\text { minimize } } & {g(\boldsymbol{x})} \\ {\text { subject to } } & {A x=y}\end{array} \] 这里的\(g:\mathbb R^n \rightarrow \mathbb R\)是一个凸函数，\(A \in \mathbb R^{m\times n},y \in \text{range}(A)\)。在之前的Lasso问题中，我们加入了噪声，然后用惩罚函数代替约束来解决。实际上用同样的方法是可以解决类似的问题： \[ \text{minimize }g(\boldsymbol{x})+\frac{\mu}{2}\|\boldsymbol{y}-\boldsymbol{A} \boldsymbol{x}\|_{2}^{2} \] 只要\(\mu\)足够大，意味着有更大的权重放在对于cost函数的优化上，这样就可以得到足够好的结果来满足约束。但是这个算法的问题在于，之前我们优化这类函数的算法，PG还是APG，他们收敛率很大程度上是受梯度\(\nabla(\mu f)=\mu A^{*}(A x-y)\)在点与点之间能变化速率影响的，这个速率由Lipschitz常数来衡量： \[ L_{\nabla \mu f}=\mu\|\boldsymbol{A}\|_{2}^{2} \] 因此就带来一个问题：\(\mu\)越大，那么上述问题就越难解决。但是想要解决等式限制问题，又必须要\(\mu\)足够大。这就意味着使用二次惩罚函数代替等式限制的方法是不够完美的。
Lagrange对偶可以将一个约束问题转化成无约束问题，而原目标函数的拉格朗日函数如下： \[ \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}) \doteq g(\boldsymbol{x})+\langle\boldsymbol{\lambda}, \boldsymbol{A} \boldsymbol{x}-\boldsymbol{y}\rangle \] 而原问题的最优解，是拉格朗日函数的鞍点（saddle point）： \[ \sup _{\boldsymbol{\lambda} } \inf _{\boldsymbol{x} } \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda})=\text{sup inf}_{\boldsymbol{\lambda} } g(\boldsymbol{x})+\langle\boldsymbol{\lambda}, \boldsymbol{A} \boldsymbol{x}-\boldsymbol{y}\rangle \] 如果我们定义对偶函数如下： \[ d(\boldsymbol{\lambda}) \doteq \inf _{\boldsymbol{x} } g(\boldsymbol{x})+\langle\boldsymbol{\lambda}, \boldsymbol{A} \boldsymbol{x}-\boldsymbol{y}\rangle \] 那么找到最优解可以通过下面的式子： \[ \begin{aligned} \boldsymbol{x}_{k+1} &=\arg \min _{\boldsymbol{x} } \mathcal{L}\left(\boldsymbol{x}, \boldsymbol{\lambda}_{k}\right) \\ \boldsymbol{\lambda}_{k+1} &=\boldsymbol{\lambda}_{k}+t_{k+1}\left(\boldsymbol{A} \boldsymbol{x}_{k+1}-\boldsymbol{y}\right) \end{aligned} \] \(\boldsymbol{A} \boldsymbol{x}_{k+1}-\boldsymbol{y}\)是对偶问题\(d(\lambda)\)的一个次梯度，这个算法就是实际上是在最大化对偶问题，因此也叫dual ascent。这个算法的缺点在于，在一些问题上，它会失败。下面是一个例子： \[ \inf _{\boldsymbol{x} }\|\boldsymbol{x}\|_{1}+\langle\boldsymbol{\lambda}, \boldsymbol{A} \boldsymbol{x}-\boldsymbol{y}\rangle=\left\{\begin{array}{ll}{-\infty} & {\left\|\boldsymbol{A}^{*} \boldsymbol{\lambda}\right\|_{\infty}>1} \\ {-\langle\boldsymbol{\lambda}, \boldsymbol{y}\rangle} & {\left\|\boldsymbol{A}^{*} \boldsymbol{\lambda}\right\|_{\infty} \leq 1}\end{array}\right. \] 可以看到的是传统的Lagrangian对于约束的惩罚是不够的，因此提出了Augmented Lagrangian： \[ \mathcal{L}_{\mu}(\boldsymbol{x}, \boldsymbol{\lambda}) \doteq g(\boldsymbol{x})+\langle\boldsymbol{\lambda}, \boldsymbol{A} \boldsymbol{x}-\boldsymbol{y}\rangle+\frac{\mu}{2}\|\boldsymbol{A} \boldsymbol{x}-\boldsymbol{y}\|_{2}^{2} \] 上面的函数可以看做是下面约束问题的Lagrangian： \[ \begin{array}{ll}{\text { minimize } } & {g(\boldsymbol{x})+\frac{\mu}{2}\|\boldsymbol{y}-\boldsymbol{A} \boldsymbol{x}\|_{2}^{2} } \\ {\text { subject to } } & {\boldsymbol{A} \boldsymbol{x}=\boldsymbol{y} }\end{array}. \] 由于惩罚项\(|\boldsymbol{y}-\boldsymbol{A} \boldsymbol{x}|_{2}^{2}\)对于可用集合中的\(x\)来说都为0，因此这个问题的最佳值与原问题的最佳值是一样的。而且通过Augmented Lagrangian，让对偶问题仅仅需要对\(g\)的一些弱假设就可以被证明是一定收敛的。为了实现它，我们对步长大小进行一个特殊的选择：\(t_k = \mu\)，得到下面的迭代策略： \[ \begin{aligned} \boldsymbol{x}_{k+1} & \in \arg \min _{\boldsymbol{x} } \mathcal{L}_{\mu}\left(\boldsymbol{x}, \boldsymbol{\lambda}_{k}\right) \\ \boldsymbol{\lambda}_{k+1} &=\boldsymbol{\lambda}_{k}+\boldsymbol{\mu}\left(\boldsymbol{A} \boldsymbol{x}_{k+1}-\boldsymbol{y}\right) \end{aligned} \] 对于步骤\(\boldsymbol{x}_{k+1}\in \arg \min _{\boldsymbol{x} }\mathcal{L}_{\mu}\left(\boldsymbol{x}, \boldsymbol{\lambda}_{k}\right)\)，本身就是一个凸优化问题，可以使用PG算法来解决。注意，\(t_{k+1}=\mu\)是非常重要的，它避免了出现失败的情况。因此对于ALM算法，可以总结如下：
- ALM for Basis Pursuit
- ALM for Principal Component Pursuit
