巢湖学院数学与统计学院，安徽 合肥

收稿日期：2021年2月18日；录用日期：2021年3月19日；发布日期：2021年3月30日

摘要

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

关键词

ADMM，Consensus，收敛性

Convergence Proof of Regularized Consensus Problems

Yujie Liu, Wenjing Bi, Yan Zhang, Lu Yu, Weinan Li

College of Mathematics and Statistics, Chaohu University, Hefei Anhui

Received: Feb. 18^th, 2021; accepted: Mar. 19^th, 2021; published: Mar. 30^th, 2021

ABSTRACT

Alternating direction multiplier method (ADMM algorithm) is an effective method to solve separable 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 alternately 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.

Keywords:ADMM, Consensus, The Convergence

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

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)。

文章引用

刘玉洁,毕文静,张 炎,俞 露,李伟南. 正则化Consensus问题的收敛性证明
Convergence Proof of Regularized Consensus Problems[J]. 理论数学, 2021, 11(03): 371-376. https://doi.org/10.12677/PM.2021.113049

参考文献