压缩感知与稀疏模型——Augmented Lagrange Multipler(ALM)

这个博客将介绍ALM,介绍一个用来解决一个等式限制的问题的框架。

考虑下面的问题:

这里的$g:\mathbb R^n \rightarrow \mathbb R$是一个凸函数,$A \in \mathbb R^{m\times n},y \in \text{range}(A)$。在之前的Lasso问题中,我们加入了噪声,然后用惩罚函数代替约束来解决。实际上用同样的方法是可以解决类似的问题:

只要$\mu$足够大,意味着有更大的权重放在对于cost函数的优化上,这样就可以得到足够好的结果来满足约束。但是这个算法的问题在于,之前我们优化这类函数的算法,PG还是APG,他们收敛率很大程度上是受梯度$\nabla(\mu f)=\mu A^{*}(A x-y)$在点与点之间能变化速率影响的,这个速率由Lipschitz常数来衡量:

因此就带来一个问题:$\mu$越大,那么上述问题就越难解决。但是想要解决等式限制问题,又必须要$\mu$足够大。这就意味着使用二次惩罚函数代替等式限制的方法是不够完美的。

Lagrange对偶可以将一个约束问题转化成无约束问题,而原目标函数的拉格朗日函数如下:

而原问题的最优解,是拉格朗日函数的鞍点(saddle point):

如果我们定义对偶函数如下:

那么找到最优解可以通过下面的式子:

$\boldsymbol{A} \boldsymbol{x}_{k+1}-\boldsymbol{y}$是对偶问题$d(\lambda)$的一个次梯度,这个算法就是实际上是在最大化对偶问题,因此也叫dual ascent。这个算法的缺点在于,在一些问题上,它会失败。下面是一个例子:

可以看到的是传统的Lagrangian对于约束的惩罚是不够的,因此提出了Augmented Lagrangian:

上面的函数可以看做是下面约束问题的Lagrangian:

由于惩罚项$|\boldsymbol{y}-\boldsymbol{A} \boldsymbol{x}|_{2}^{2}$对于可用集合中的$x$来说都为0,因此这个问题的最佳值与原问题的最佳值是一样的。而且通过Augmented Lagrangian,让对偶问题仅仅需要对$g$的一些弱假设就可以被证明是一定收敛的。为了实现它,我们对步长大小进行一个特殊的选择:$t_k = \mu$,得到下面的迭代策略:

对于步骤$\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算法,可以总结如下:

  1. ALM for Basis Pursuit
  2. ALM for Principal Component Pursuit