正则化Consensus问题的收敛性证明

Convergence Proof of Regularized Consensus Problems

摘要: 交替方向乘子法(ADMM算法)是求解可分离凸优化问题的一种有效方法。该算法利用目标函数的可分性，将原问题拆分成若干个极小化的子问题，然后交替迭代求解。而一致性(Consensus)问题是求解大数据问题的重要的一种形式，本文提出了一种正则化的一致性问题，给出了其迭代过程，并在适当的假设下，证明了其收敛性。

Abstract: Alternating direction multiplier method (ADMM algorithm) is an effective method to solve sepa-rable convex optimization problems. The algorithm USES the separability of the objective function to divide the original problem into several minimization subproblems and then solve them alter-nately iteratively. Consensus is an important form of solving big data problems. In this paper, a regularized consistency problem is proposed, its iterative process is given, and its convergence is proved under appropriate assumptions.

1. 引言

乘子交替方向法(ADMM)是一种求解线性约束凸优化问题的高效算法，由Glowinski等 [1] 及Gabay等 [2] 分别于1975年和1976年提出。该算法首先构造原问题的增广拉格朗日函数，每个迭代步由多个子问题构成，每个子问题对于增广拉格朗日函数关于1块变量进行极小化，当所有子问题求解结束后更新乘子(对偶变量)。该算法收敛速度较快，且子问题规模较小、计算量较低，因而该算法的计算效率较高，已被广泛应用于求解信息科学、统计学、机器学习等领域的多种优化问题，如矩阵完整化问题、图像去模糊去噪问题、协方差矩阵校正问题等 [3] [4] [5] [6] [7]。斯坦福大学Boyd等 [6] 于2011年对ADMM进行了综述，并指出该算法适合求解大规模分布式优化问题。

所谓全局变量一致性优化问题，即目标函数根据数据分解成N子目标函数(子系统)，每个子系统和子数据都可以获得一个参数解，但是全局解只有一个z，于是就可以写成如下优化命题：

$\begin{array}{l}\min {\displaystyle \underset{i=1}{\overset{N}{\sum }}{f}_i\left(x_i\right)}\\ \text{s}\text{.t}\text{.}{x}_i-z=0,i=1,\cdots ,N\end{array}$

注意，此时仍是凸函数，而并不是对参数空间进行划分，这里是对数据而言，所以维度一样，与之前的问题并不太一样。这种问题其实就是所谓的并行化处理，或分布式处理，希望从多个分块的数据集中获取相同的全局参数解。

在ADMM算法框架下(先返回最初从扩增lagrangian导出的ADMM)，这种问题解法相当明确：

$\begin{array}{l}{L}_{\rho }\left(x_1,\cdots ,x_N,z,y\right)={\displaystyle \underset{i=1}{\overset{N}{\sum }}\left(f_i\left(x_i\right)+y_i^{\text{T}}\left(x_i-z\right)+\left(\rho /2\right){\Vert x_i-z\Vert }_2^2\right)}\\ \text{s}\text{.t}\text{.}C=\left\{\left(x_1,\cdots ,x_N\right)|x_1=\cdots =x_N\right\}\end{array}$

从而迭代结果为

$\begin{array}{l}{x}_i^{k+1}=\underset{x_i}{\arg \min }\left(f_i\left(x_i\right)+y_i^{k\text{T}}\left(x_i-z^k\right)+\left(\rho /2\right){\Vert x_i-z^k\Vert }_2^2\right)\\ z^{k+1}=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}\left(x_i^{k+1}+\left(1/\rho \right)y_i^k\right)}\\ y_i^{k+1}=y_i^k+\rho \left(x_i^{k+1}-z^{k+1}\right)\end{array}$

对y-update和z-update的和分别求个平均，易得，于是可以知道z-update步其实可以简化为，于是上述ADMM其实可以进一步化简为如下形式：

$\begin{array}{l}{x}_i^{k+1}=\underset{x_i}{\arg \min }\left(f_i\left(x_i\right)+y_i^{k\text{T}}\left(x_i-{\bar{x}}^k\right)+\left(\rho /2\right){\Vert x_i-{\bar{x}}^k\Vert }_2^2\right)\\ y_i^{k+1}=y_i^k+\rho \left(x_i^{k+1}-{\bar{x}}^{k+1}\right)\end{array}$

这种迭代算法写出来了，并行化那么就是轻而易举了，各个子数据分别并行求最小化，然后将各个子数据的解汇集起来求均值，整体更新对偶变量，然后再继续回带求最小值至收敛。当然也可以分布式部署(hadoop化)，但是说起来容易，真正工程实施起来又是另外一回事，各个子节点机器间的通信更新是一个需要细细揣摩的问题。

另外，对于全局一致性优化，也需要给出相应的终止迭代准则，与一般的ADMM类似，这里的primal和dual的residuals为

$r^k=\left(x_1^k-{\bar{x}}^k,\cdots ,x_N^k-{\bar{x}}^k\right),s^k=-\rho \left({\bar{x}}^k-{\bar{x}}^{k-1},\cdots ,{\bar{x}}^k-{\bar{x}}^{k-1}\right)$

从而2-norm为

${\Vert r^k\Vert }_2^2={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\Vert x_i-{\bar{x}}^k\Vert }_2^2},{\Vert s^k\Vert }_2^2=N{\rho }^2{\Vert {\bar{x}}^k-{\bar{x}}^{k-1}\Vert }_2^2$

本文主要考虑正则化的Consensus问题，即在目标函数后面加个正则项g(z)，并且这个正则项存在偏导数。证明提出的正则化的一致性算法的收敛性，给出了详细证明。

2. 正则化的Consensus问题

下面就是要将之前所谈到的经典的机器学习算法并行化起来。想法很简单，就是对全局变量加上正则项即可，

$\begin{array}{l}\min {\displaystyle \underset{i=1}{\overset{N}{\sum }}{f}_i\left(x_i\right)}+g\left(z\right)\\ \text{s}\text{.t}\text{.}{x}_i-z=0,i=1,\cdots ,N\end{array}$

首先构建非增广的Lagrangian $L_0$ 有

$L_0\left(x_1,\cdots ,x_N,z,y\right)={\displaystyle \underset{i=1}{\overset{N}{\sum }}\left(f_i\left(x_i\right)+y_i^{\text{T}}\left(x_i-z\right)\right)}+g\left(z\right)$，

从而增广的Lagrangian $L_{\rho }$ 有

$L_{\rho }\left(x_1,\cdots ,x_N,z,y\right)={\displaystyle \underset{i=1}{\overset{N}{\sum }}\left(f_i\left(x_i\right)+y_i^{\text{T}}\left(x_i-z\right)+\left(\rho /2\right){\Vert x_i-z\Vert }_2^2\right)}+g\left(z\right)$.

因此ADMM算法只需要改变下z-update步即可

$\begin{array}{l}{x}_i^{k+1}=\underset{x_i}{\arg \min }\left(f_i\left(x_i\right)+y_i^{k\text{T}}\left(x_i-z^k\right)+\left(\rho /2\right){\Vert x_i-z^k\Vert }_2^2\right)\\ z^{k+1}=\underset{z}{\arg \min }\left(g\left(z\right)+{\displaystyle \underset{i=1}{\overset{N}{\sum }}-y_i^{k\text{T}}z}+\left(\rho /2\right){\Vert x_i^{k+1}-z\Vert }_2^2\right)\\ y_i^{k+1}=y_i^k+\rho \left(x_i^{k+1}-z^{k+1}\right)\end{array}$

同样的，我们仍对z做一个平均处理，于是就有

$z^{k+1}=\underset{z}{\arg \min }\left(g\left(z\right)+\left(N\rho /2\right){\Vert z-{\bar{x}}^{k+1}-\left(1/\rho \right){\bar{y}}^k\Vert }_2^2\right)$

上述形式都取得是最原始的ADMM形式，简化处理，写成scaled形式即有

$\begin{array}{l}{x}_i^{k+1}=\underset{x_i}{\arg \min }\left(f_i\left(x_i\right)+\left(\rho /2\right){\Vert x_i-z^k+u_i^k\Vert }_2^2\right)\\ z^{k+1}=\underset{z}{\arg \min }\left(g\left(z\right)+\left(N\rho /2\right){\Vert z-{\bar{x}}^{k+1}-{\bar{u}}^k\Vert }_2^2\right)\\ u_i^{k+1}=u_i^k+x_i^{k+1}-z^{k+1}\end{array}$

这样对于后续处理问题就清晰明了多了。可以看到如果 $g\left(z\right)=\lambda {\Vert z\Vert }_1$，即lasso问题，那么z-update步就用软阈值operator即

$z^{k+1}=S_{\lambda /N\rho }\left({\bar{x}}^{k+1}-\left(1/\rho \right){\bar{y}}^k\right)$

因此，对于大规模数据，要想用lasso等算法，只需要对数据做切块(切块也最好切均匀点)，纳入到全局变量一致性的ADMM框架中，即可并行化处理。

3. 项收敛性证明

本部分主要说明上述算法的收敛性，在证明之前首先给出一些符号说明及条件假设。

符号说明：令 $\left(x_1,\cdots ,x_N,y,z\right)$ 为 $\left(x,y,z\right)$， $f\left(x\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}f\left(x_i\right)}$。

假设1：函数 $f_i,g$ 是偏导数存在的凸函数。

假设2：非增广的Lagrangian $L_0$ 存在鞍点，即存在 $\left(x^{*},y^{*},z^{*}\right)$，对任意的 $\left(x,y,z\right)$ 使得：

$L_0\left(x^{*},y,z^{*}\right)\le L_0\left(x^{*},y^{*},z^{*}\right)\le L_0\left(x,y^{*},z\right)$

定理：在满足上述假设条件1，2和上述算法的迭代过，当 $k\to \infty$，

$r^k\to 0,z^{k+1}-z^k\to 0$

从而我们有

$\underset{k\to \infty }{\lim }{p}^k=p^{*}$

证明：

部分1

因为 $\left(x^{*},y^{*},z^{*}\right)$ 是函数 $L_0$ 的鞍点，所以有：

$L_0\left(x^{*},z^{*},y^{*}\right)\le L_0\left(x^{k+1},z^{k+1},y^{*}\right)$ (1)

再利用 $x^{*}-z^{*}=0$，令

$p^{k+1}=f\left(x^{k+1}\right)+g\left(z^{k+1}\right)$， $p^{*}=f\left(x^{*}\right)+g(\; z\; *\; )$

从而(1)式有

$p^{*}\le p^{k+1}+y^{*\text{T}}{r}^{k+1}$ (2)

部分2

通过定义我们知道， $x^{k+1}$ 是 $L_{\rho }\left(x,z^k,y^k\right)$ 的极小值。由于f是可偏导的凸函数。所以：

$0\in \partial L_{\rho }\left(x^{k+1},z^k,y^k\right)=\partial f\left(x^{k+1}\right)+y^k+\rho \left(x^{k+1}-z^k\right)$

又因为 $y^{k+1}=y^k+\rho r^{k+1}$，所以有 $y^k=y^{k+1}+\rho r^{k+1}$，从而

$0\in \partial L_{\rho }\left(x^{k+1},z^k,y^k\right)=\partial f\left(x^{k+1}\right)+y^{k+1}-\rho \left(z^{k+1}-z^k\right)$

这里表明 $x^{k+1}$ 是下面这个函数的极小值

$f\left(x\right)+y^{k+1}-\rho \left(z^{k+1}-z^k\right)x$ (4)

与上面相似的证法可以说明 $z^{k+1}$ 是函数 $g\left(z\right)+y^{\left(k+1\right)\text{T}}z$ 的极小值。结合(4)式有

$f\left(x^{k+1}\right)+y^{k+1}-\rho \left(z^{k+1}-z^k\right)x^{k+1}\le f\left(x^{*}\right)+y^{k+1}-\rho \left(z^{k+1}-z^k\right)x^{*}$ (5)

$g\left(z^{k+1}\right)+y^{\left(k+1\right)\text{T}}{z}^{k+1}\le g\left(z^{*}\right)+y^{\left(k+1\right)\text{T}}{z}^{*}$ (6)

再结合 $x^{*}-z^{*}=0$，结合(5)和(6)式有

$p^{k+1}-p^{*}\le -{\left(y^{k+1}\right)}^{\text{T}}{r}^{k+1}-\rho {\left(z^{k+1}-z^k\right)}^{\text{T}}\left(-r^{k+1}+z^{k+1}-z^{*}\right)$ (7)

证明3

结合(2)和(7)有

$2{\left(y^{k+1}-y^{*}\right)}^{\text{T}}{r}^{k+1}-2\rho {\left(z^{k+1}-z^k\right)}^{\text{T}}{r}^{k+1}+2\rho {\left(z^{k+1}-z^k\right)}^{\text{T}}\left(z^{k+1}-z^{*}\right)\le 0$ (8)

对于(8)式中的第一部分利用 $y^{k+1}=y^k+\rho r^{k+1}$ 有

$2{\left(y^k-y^{*}\right)}^{\text{T}}{r}^{k+1}+\rho {\Vert r^{k+1}\Vert }_2^2+\rho {\Vert r^{k+1}\Vert }_2^2$ (9)

再利用 $r^{k+1}=\left(1/\rho \right)\left(y^{k+1}-y^k\right)$，因此(9)式中的前两部分有

$\left(2/\rho \right){\left(y^k-y^{*}\right)}^{\text{T}}\left(y^{k+1}-y^k\right)+\left(1/\rho \right){\Vert y^{k+1}-y^k\Vert }_2^2+\rho {\Vert r^{k+1}\Vert }_2^2$

又因为 $y^{k+1}-y^k=\left(y^{k+1}-y^{*}\right)-\left(y^k-y^{*}\right)$，从而上式变为

$\left(1/\rho \right)\left({\Vert y^{k+1}-y^{*}\Vert }_2^2-{\Vert y^k-y^{*}\Vert }_2^2\right)+\rho {\Vert r^{k+1}\Vert }_2^2$ (10)

接下来，整理(8)和(9)式中剩下的部分，即

$\rho {\Vert r^{k+1}\Vert }_2^2-2\rho {\left(z^{k+1}-z^k\right)}^{\text{T}}{r}^{k+1}+2\rho {\left(z^{k+1}-z^k\right)}^{\text{T}}\left(z^k-z^{*}\right)$

再利用 $z^{k+1}-z^{*}=\left(z^{k+1}-z^k\right)-\left(z^k-z^{*}\right)$，有

$\rho {\Vert r^{k+1}-\left(z^{k+1}-z^k\right)\Vert }_2^2+\rho {\Vert z^{k+1}-z^k\Vert }_2^2+2\rho {\left(z^{k+1}-z^k\right)}^{\text{T}}\left(z^k-z^{*}\right)$

再结合 $z^{k+1}-z^k=\left(z^{k+1}-z^{*}\right)-\left(z^k-z^{*}\right)$，从而有

$\rho {\Vert r^{k+1}-\left(z^{k+1}-z^k\right)\Vert }_2^2+\rho \left({\Vert z^{k+1}-z^{*}\Vert }_2^2-{\Vert z^k-z^{*}\Vert }_2^2\right)$

令

$U_k=\left(1/\rho \right){\Vert y^k-y^{*}\Vert }_2^2+\rho {\Vert z^k-z^{*}\Vert }_2^2$

从而(8)可以写成

$U_k-U_{k+1}\ge \rho {\Vert r^{k+1}-\left(z^{k+1}-z^k\right)\Vert }_2^2$ (11)

由证明2中可以看出， $z^{k+1}$ 是函数 $g\left(z\right)+y^{\left(k+1\right)\text{T}}z$ 的极小值， $z^k$ 是函数 $g\left(z\right)+y^{\left(k\right)\text{T}}z$ 的极小值，从而有

$g\left(z^{k+1}\right)+y^{\left(k+1\right)\text{T}}{z}^{k+1}\le g\left(z^k\right)+y^{\left(k+1\right)\text{T}}{z}^k$

$g\left(z^k\right)+y^{\left(k\right)\text{T}}{z}^k\le g\left(z^{k+1}\right)+y^{\left(k\right)\text{T}}{z}^{k+1}$

结合上面两个不等式，有

${\left(y^{k+1}-y^k\right)}^{\text{T}}\left(z^{k+1}-z^k\right)\le 0$

又因为 $y^{k+1}-y^k=\rho r^{k+1}$，从而得到

$\rho r^{k+1}\left(z^{k+1}-z^k\right)\le 0$ (12)

结合(12)式，使得(11)有

$U_k-U_{k+1}\ge \rho \Vert r^{k+1}\Vert +\rho {\Vert z^{k+1}-z^k\Vert }_2^2$

从而有

${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}\left(\rho \Vert r^{k+1}\Vert +\rho {\Vert z^{k+1}-z^k\Vert }_2^2\right)}\le U_0$ (13)

从(13)式可以看出 $r^k\to 0,z^{k+1}-z^k\to 0,k\to \infty$，从而得到

$\underset{k\to \infty }{\lim }{p}^k=p^{*}$

4. 总结

通过正则化的一致性问题，我们可以看到并行和分布式部署优化方案的可行性。我们可以切分数据以及相应的目标函数，也可以切分变量到各个子系统上去，分别作优化，甚至我们可以大胆想象对不同类型数据块用不同的优化算法，结合Consensus问题和ADMM算法，达到同一个全局变量的优化目的；并且在理论上说明了算法的收敛性。

致 谢

本文的撰写感谢程一元老师的指导。

基金项目

巢湖学院省级大学生创新创业训练计划资助项目(S201910380067)，巢湖学院省级大学生创新创业训练计划资助项目(S201910380065)，巢湖学院校级科研项目(XLY-201903)。