交替方向乘子法（admm）

统计学、机器学习和科学计算中出现了很多结构复杂且可能非凸、非光滑的优化问题。交替方向乘子法很自然地提供了一种适用范围广泛、容易理解和实现、可靠性不错地解决方案。该方法在20世纪70年代发展起来地，与许多其他算法等价或密切相关，如对偶分解、乘子方法、Douglas-Rachford Splitting方法、Dykstra交替投影方法、Bregman对于带 $l_1$ 范数问题地迭代算法、近似点算法等、本届首先介绍交替方向乘子法地基本算法；在介绍了Douglas-Rachford Splitting方法之后，说明见其应用在对偶问题上与交替方向乘子法应用在原始问题上等价；然后给出交替方向乘子法地一些变形技巧，以及它和其他一些算法地关系；接着给出大量实际问题地例子，并展示如何用交替方向乘子法来求解这些问题

一、交替方向乘子法
本节考虑如下凸问题
$\begin{aligned} &\min_{x_1,x_2}\quad f_1(x_1)+f_2(x_2)\\ & s.t.\quad A_1x_1+A_2x_2=b, \end{aligned}\tag{1}$
其中 $f_1,f_2$ 是适当地闭凸函数，但不要求是光滑的， $x_1\in\mathcal{R^n},x_2\in\mathcal{R^m},A_1\in\mathcal{R^{p\times n}},A_2\in\mathcal{R^{p\times m}},b\in\mathcal{R^p}$ .这个问题的特点是目标函数可以分成彼此分离的两块，但是变量被线性约束结合在一起。常见的一些无约束和带约束的优化问题都可以表示成这一形式。下面的一些例子将展示如何把某些一般的优化问题转化为适合交替方向乘子法求解的标准形式。

例1 可以分成两块的无约束优化问题
$min_x f_1(x)+f_2(x)$
为了将此问题转化为标准形式（1），需要将目标函数改成可分的形式。我们可以通过引入一个新的变量 $z$ 并令 $x = z$ ，将问题转化为
$\begin{aligned} & \min_{x,z}\quad f_1(x)+f_2(z), \\ & s.t.\quad x-z=0. \end{aligned}$

例2 带线性变化的无约束优化问题
$min_{x} f_1(x)+f_2(Ax).$
类似地，我们可以引入一个新的变量 $z$ ，令 $z = A x$ ，则问题变为
$\begin{aligned} &\min_{x,z}\quad f_1(x)+f_2(z),\\ &s.t.\quad Ax-z = 0 \end{aligned}$
对比问题（1）可知， $A_1=A,A_2=-I$

例3 凸集上的约束优化问题
$\begin{aligned} &\min_x\quad f(x)\\ &s.t.\quad Ax\in C. \end{aligned}$
其中 $C\subset\mathcal{R^n}$ 为凸集。对于集合约束 $Ax\in C$ ，我们可以用实行函数 $I_C(\cdot)$ 将其添加到目标函数中，那么问题可转化为如下形式：
$min_x f(x)+I_C(Ax),$
其中 $I_C(z)$ 是集合C的实行函数，即
$I_C(z)=\left\{ \begin{aligned} &0,&z\in C,\\ &+\infty,&otherwise. \end{aligned} \right.$
再引入约束 $z = A x$ ，那么问题转化为
$\begin{aligned} &\min_{x,z} f(x)+I_C(z)\\ &s.t. Ax-z = 0 \end{aligned}$

例4 全局一致性问题
$\min_x\sum_{i=1}^{N}\phi_i(x)$
令 $x = z$ ，将 $x$ 复制 $N$ 份，分别为 $x_i$ ，那么问题转化为
$\begin{aligned} &\min_{x_i,z}\sum_{i=1}^{N}\phi_i(x_i),\\ & s.t. x_i-z=0,i=1,2,\cdots,N \end{aligned}$
在这里注意，从形式上看全局一致性问题仍然具有问题（1）的结果：如果令 $x=(x_1^T,x_2^T,\cdots,x_N^T)^T$ 以及 $f_x(x)=\sum_{i=1}^N\phi_i(x_i),f_2(z)=0$ ,则此问题可转化为
$\begin{aligned} &\min_{x,z}f_1(x)+f_2(x),\\ &s.t. A_1x-A_2z=0, \end{aligned}$
其中矩阵 $A_1,A_2$ 定义为：
$A_1=\begin{bmatrix} &I&&&\\ &&I&&\\ &&&\ddots&\\ &&&&I \end{bmatrix}, A_2=\begin{bmatrix} I\\I\\\vdots\\I \end{bmatrix}.$
在全局一致性问题的例子中，我们将问题重写为具有两个变量快的形式，而不是简单地将问题（1）推广为多个变量快地形式，这样做的原因是ADMM算法从两个变量块推广到多个变量块的形式并不一定收敛。

例5 共享问题
$\min_{x_i}\sum_{i=1}^{N}f_i(x_i)+g(\sum_{i=1}^{N}x_i)$
为了使目标函数可分，我们将 $g$ 的变量 $x_i$ 分别复制一份为 $z_i$ ，那么问题转化为
$\begin{aligned} &\min_{x_i,z_i}\sum_{i=1}^{N}f_i(x_i)+g(\sum_{i=1}^{N}z_i),\\ &s.t. x_i-z_i=0,i=1,2,\cdots,N. \end{aligned}$
容易验证此问题也具有（1）的形式。
下面给出交替方向乘子法（alternating direction method of multipliers, ADMM）的迭代格式，首先写出问题（1）的增广拉格朗日函数：
$L_{\rho}(x_1,x_2,y)=f_1(x_1)+f_2(x_2)+y^T(A_1x_1+A_2x_2-b)+\frac{\rho}{2}||A_1x_1+A_2x_2-b||_2^2, \tag{2}$
其中 $\rho>0$ 是二次惩罚项的稀疏。常见的求解带约束问题的拉格朗日函数法为如下更新：
$\begin{aligned} (x_1^{k+1},x_2^{k+1}) & = argmin_{x_1,x_2}L_{\rho}(x_1,x_2,y^k) \end{aligned} \tag{3}$
$y^{k+1}=y^k+\tau\rho(A_1x_1^{k+1}+A_2^{k+1}-b) \tag{4}$
其中 $\tau$ 为步长。在实际求解中，第一步迭代（3）同时对 $x_1$ 和 $x_2$ 进行优化有时候比较困难，而固定一个变量求解关于另一个变量的极小化问题可能比较简单，因此我们可以考虑对 $x_1$ 和 $x_2$ 交替极小化，这就是交替方向乘子法的基本思路。其迭代格式可以总结如下：
$x_1^{k+1}=arg\min_{x_1}L_{\rho}(x_1,x_2^k,y^k),\tag{5}$
$x_2^{k+1}=arg\min_{x_2}L_{\rho}(x_{k+1},x_2,y^k),\tag{6}$
$y^{k+1}=y^k+\tau\rho(A_1x_1^{k+1}+A_2x_2^{k+1}-b),\tag{7}$
其中 $\tau$ 为步长，通常取值为 $(0,\frac{1+\sqrt{5}}{2}]$ .关于选择步长的收敛性。
观察交替方向乘子法的迭代格式，第一步固定 $x_2,y$ 对 $x_1$ 求绩效；第二步固定 $x_1,y$ 对 $x_2$ 求极小；第二步更新拉格朗日乘子 $y$ 。这一迭代格式和之前讨论的交替极小化方法非常类似。它们的区别是交替极小化方法的第一步是针对拉格朗日函数求极小，而ADMM的第一步将其化成了增广拉格朗日函数。虽然从形式上看两个算法只是略有差别，但这种改变会带来截然不同的算法表先。ADMM的一个直接的改善就是去掉了目标函数 $f_1(x)$ 强凸的要求，其本质还是由于它引入了二次惩罚项。而在交替极小化方法中我们要求 $f (x)$ 为强凸函数。
需要注意的是，虽然交替方向乘子法引入了二次惩罚项，但对一般的闭凸函数 $f_1$ 和 $f_2$ ，迭代（5）和迭代（6）在某些特殊情况下仍然不是连定义的。本届假设每个子问题的解均是存在且唯一的，但读者应当注意到这个假设对一般闭凸函数是不成立的。
与无约束优化问题不同，交替方向乘子法针对问题（1）是带约束的优化问题，因此算法的收敛准则应当借助约束优化问题的最优性条件（KKT条件）。因为 $f_1,f_2$ 均为闭凸函数，约束为线性约束，所以但Slater条件成立时，可以使用凸优化问题的KKT条件来作为交替方向乘子法的收敛准则。问题（1）的拉格朗日函数为
$L_{\rho}(x_1,x_2,y)=f_1(x_1)+f_2(x_2)+y^T(A_1x_1+A_2x_2-b)$
若 $x_1^*,x_2^*$ 为问题（1）的最优解， $y *$ 为对应的拉格朗日橙子，则以下条件满足：
$0\in\partial_{x_1}L(x_1^*,x_2^*,y^*)=\partial f_1(x_1^*)+A_1^Ty^*,\tag{8a}$
$0\in\partial_{x_2}L(x_1^*,x_2^*,y^*)=\partial f_2(x_2^*)+A_2^Ty^*,\tag{8b}$
$A_1x_1^*+A_2x_2^*=b.\tag{8c}$
在这里条件（8c）又称为原始可行条件，条件（8a）和条件(8b)又称为对偶可行性条件。由于问题中只含等式约束，KKT条件中的互补松弛条件可以不考虑。在ADMM迭代中，我们得到的迭代点实际为 $x_1^k,x_2^k,y^k)$ ，因此收敛准则应当针对 $x_1^k,x_2^k,y^k)$ 检测条件（8）.

二、Douglas-Rachford Splitting算法
Douglas-Rachford Splitting（DRS）算法时一类非常重要的算子分裂算法。它可以用于求解下面的无约束优化问题：
$\min_x\psi(x)=f(x)+h(x) \tag{9}$
其中 $f$ 和 $h$ 时闭凸函数。DRS算法的迭代格式为
$\begin{aligned} x^{k+1}&=prox_{th}(z^k),\\ y^{k+1}&=prox_{tf}(2x^{k+1}-z^k),\\ z^{k+1}&=z^k+y^{k+1}-x^{k+1} \end{aligned}$
其中t时一个正的常数，我们还可以通过一系列变形来得到DRS格式的等价迭代。首先在原始DRS格式中按照 $y, z, x$ 的顺序更新，则有
$\begin{aligned} y^{k+1}&=prox_{tf}(2x^{k}-z^k),\\ z^{k+1}&=z^k+y^{k+1}-x^{k},\\ x^{k+1}&=prox_{th}(z^{k+1}).\\ \end{aligned}$
引入辅助变量 $\omega^k=z^k-x^k$ ，并注意到上面迭代中变量 $z^k,z^{k+1}$ 可以小区，则得到DRS算法的等价迭代格式：
$\begin{aligned} y^{k+1}&=prox_{tf}(x^{k}-\omega^k),\\ x^{k+1}&=prox_{th}(\omega^k+y^{k+1}),\\ \omega^{k+1}&=\omega^k+y^{k+1}-x^{k+1}.\\ \end{aligned}$

三、常见的变形和技巧
本小节将给出交替方向乘子法的一些变形以及实现交替方向乘子法的一些技巧。

线性化
我们构造ADMM的初衷时将自变量拆分，最终使得关于 $x_1$ 和 $x_2$ 的子问题有显示解。但是实际应用中，有时子问题并不容易求解，或者没必要精确求解。那么如何寻找子问题的一个近似呢？
不失一般性，我们考虑第一个子问题，即
$\min_{x_1} f_1(x_1)+\frac{\rho}{2}||A_1x_1-v^k||^2,\tag{10}$
其中
$v^k=b-A_2x_2^k-\frac{1}{\rho}y^k.\tag{11}$
当子问题不能显示求解时，可采用线性化的方法近似求解问题（9）.线性化技巧实际上时使用近似点项对子问题目标函数吉星二次近似。当子问题目标函数可微时，线性化可见问题（9）变为：
$x_1^{k+1}=arg\min_{x_1}\{(\nabla f_1(x_1^k))+\rho （A_1^T(A_1x_1^k-v^k)）^Tx_1+\frac{1}{2\eta_k}||x_1-x^k||_2^2\},$
其中 $\eta_k$ 是步长参数，这等价于做一步梯度下降。当目标函数不可微时，可以考虑之间二次项线性化，即
$x_1^{k+1}=arg\min_{x_1}\{f(x_1)+\rho （A_1^T(A_1x_1^k-v^k)）^Tx_1+\frac{1}{2\eta_k}||x_1-x^k||_2^2\},$
这等价于求解子问题（9）时做一步近似点梯度步。当然，若 $f_1(x_1)$ 时可微函数与不可微函数的和时，也可将其可微部分线性化。
缓存分解
如果目标函数中含二次函数，例如 $f_1(x_1)=\frac{1}{2}||Cx_1-d||_2^2$ ，那么针对 $x_1$ 的更新等价于求解线性方程组
$(C^TC+\rho A_1^TA_1)x_1=C^Td+\rho A_1^Tv^k,$
其中 $v^k$ 的定义如（11）式。虽然子问题有显示解，但是每部求解的复杂度仍然比较高，这个时候可以考虑用缓存分解的方法。首先对 $C^TC+\rho A_1^TA_1$ 进行Cholesky分解并缓存分解的结果，在每步迭代中只需要求解简单的三角形方程组；当 $\rho$ 发生更新时，就要重新进行分解。特别地，当 $C^TC+\rho A_1^TA_1$ 一部分容易求逆，另一部分时低秩的情形，可以用SMW公式来求逆。
优化转移
有时候为了方便求解子问题，可以用一个性质郝的矩阵D近似二次项 $A_1^TA_1$ ，此时子问题（10）替换为
$x_1^{k+1}=arg\min_{x_1}\{f_1(x_1)+\frac{\rho}{2}||A_1x_1-v^k||_2^2+\frac{\rho}{2}(x_1-x^k)^T(D-A_1^TA_1)(x_1-x^k)\},$
其中 $v^k$ 的定义如（11）式，这种方法也称为优化转移。通过选取合适的D，当计算 $arg\min_{x_1}\{f_1(x_1)+\frac{2}{\rho}x_1^TDx_1\}$ 明显比计算 $arg\min_{x_1}\{f_1(x_1)+\frac{2}{\rho}x_1^TA_1^TA_1x_1\}$ 要容易时，优化转移可以极大地简化子问题地计算。特别地，当 $D=\frac{\eta_k}{\rho}I$ 时，优化转移等价于做但不地近似点梯度。
二次惩罚项系数地动态调节
动态调节二次惩罚项系数在交替方向乘子法地实际应用中时非常重要地数值技巧。在介绍ADMM时我们引入了原始可行性和对偶可行性。在实际求解过程中，二次惩罚项系数 $\rho$ 太大会导致原始可行性下降很快，但是对偶可行性下降很慢；二次惩罚项系数太小，则会有相反地效果。这样都会导致收敛比较慢或得到地解可行性很差。一个自然地想法是在每次迭代时动态调节惩罚系数 $\rho$ 地大小，从而使得原始可行性和对偶可行性能够以比较一致地速度下降到零。这种做法通常可以改善算法在实际中地收敛效果，以及使算法表现更少地依赖于惩罚系数地初始选择。一个简单有效地方式是令
$\rho^{k+1}=\left\{ \begin{aligned} &\gamma_p\rho^k,&||r^k||>\mu||s^k||,\\ &\frac{\rho^k}{\gamma^d},&||s^k||>\mu||r^k||,\\ &\rho^k,&otherwise \end{aligned} \right.$
其中 $\mu>1,\gamma_p>1,\gamma_d>1$ 是参数，常见地选择为 $\mu=10,\gamma_p=\gamma_d=2$ 。该惩罚参数更新方式背后地想法是在迭代过程中，将原始可行性和对偶可行性保持在彼此地 $\mu$ 倍以内。如果原始可行性或对偶可行性下降过慢就应该相应增加或减小二次惩罚项系数 $\rho^k$ 。但在改变 $\rho^k$ 地时候需要注意，若之前利用了缓存分解地技巧，此时分解需要重新计算。更一般地，我们可以考虑对每一个约束给一个不同地惩罚系数，审制可以将增广拉格朗日函数中地二次项 $\frac{\rho}{2}||r||^2$ 替换为 $\frac{\rho}{2}r^TPr$ ，其中P是一个对称镇定矩阵。如果P在郑哥迭代过程中是不变地，我们可以将这个一般地交替方向乘子法解释为标准地交替方向乘子法应用在修改后地初始问题上-----等式约束 $A_1x_1+A_2x_2-b=0$ 替换为 $F(A_1x_1+A_2x_2-b)=0$ ，其中F为P地Cholesky因子，即 $P=F^TF$ ，且F是对角元为正树地上三角矩阵。
超松弛
另外一种想法是用超松弛地技巧，在（6）式与（7）式中， $A_1x_1^{k+1}$ 可以被替换为
$\alpha_kA_1x_1^{k+1}-(1-\alpha_k)(A_2x_2^k-b),$
其中 $\alpha_k\in(0,2)$ 是一个松弛参数。但 $\alpha_k>1$ 时，这种技巧称为超松弛；但 $\alpha_k<1$ 时，这种技巧称为欠松弛。实验表明 $\alpha_k\in[1.5,1.8]$ 地超松弛可以提高收敛速度。

原文链接：https://blog.csdn.net/luzhanbo207/article/details/122448498