1. 引言
乘子交替方向法(ADMM)是一种求解线性约束凸优化问题的高效算法,由Glowinski等 [1] 及Gabay等 [2] 分别于1975年和1976年提出。该算法首先构造原问题的增广拉格朗日函数,每个迭代步由多个子问题构成,每个子问题对于增广拉格朗日函数关于1块变量进行极小化,当所有子问题求解结束后更新乘子(对偶变量)。该算法收敛速度较快,且子问题规模较小、计算量较低,因而该算法的计算效率较高,已被广泛应用于求解信息科学、统计学、机器学习等领域的多种优化问题,如矩阵完整化问题、图像去模糊去噪问题、协方差矩阵校正问题等 [3] [4] [5] [6] [7]。斯坦福大学Boyd等 [6] 于2011年对ADMM进行了综述,并指出该算法适合求解大规模分布式优化问题。
所谓全局变量一致性优化问题,即目标函数根据数据分解成N子目标函数(子系统),每个子系统和子数据都可以获得一个参数解,但是全局解只有一个z,于是就可以写成如下优化命题:
注意,此时仍是凸函数,而并不是对参数空间进行划分,这里是对数据而言,所以维度一样,与之前的问题并不太一样。这种问题其实就是所谓的并行化处理,或分布式处理,希望从多个分块的数据集中获取相同的全局参数解。
在ADMM算法框架下(先返回最初从扩增lagrangian导出的ADMM),这种问题解法相当明确:
从而迭代结果为
对y-update和z-update的和分别求个平均,易得,于是可以知道z-update步其实可以简化为,于是上述ADMM其实可以进一步化简为如下形式:
这种迭代算法写出来了,并行化那么就是轻而易举了,各个子数据分别并行求最小化,然后将各个子数据的解汇集起来求均值,整体更新对偶变量,然后再继续回带求最小值至收敛。当然也可以分布式部署(hadoop化),但是说起来容易,真正工程实施起来又是另外一回事,各个子节点机器间的通信更新是一个需要细细揣摩的问题。
另外,对于全局一致性优化,也需要给出相应的终止迭代准则,与一般的ADMM类似,这里的primal和dual的residuals为
从而2-norm为
本文主要考虑正则化的Consensus问题,即在目标函数后面加个正则项g(z),并且这个正则项存在偏导数。证明提出的正则化的一致性算法的收敛性,给出了详细证明。
2. 正则化的Consensus问题
下面就是要将之前所谈到的经典的机器学习算法并行化起来。想法很简单,就是对全局变量加上正则项即可,
首先构建非增广的Lagrangian
有
,
从而增广的Lagrangian
有
.
因此ADMM算法只需要改变下z-update步即可
同样的,我们仍对z做一个平均处理,于是就有
上述形式都取得是最原始的ADMM形式,简化处理,写成scaled形式即有
这样对于后续处理问题就清晰明了多了。可以看到如果
,即lasso问题,那么z-update步就用软阈值operator即
因此,对于大规模数据,要想用lasso等算法,只需要对数据做切块(切块也最好切均匀点),纳入到全局变量一致性的ADMM框架中,即可并行化处理。
3. 项收敛性证明
本部分主要说明上述算法的收敛性,在证明之前首先给出一些符号说明及条件假设。
符号说明:令
为
,
。
假设1:函数
是偏导数存在的凸函数。
假设2:非增广的Lagrangian
存在鞍点,即存在
,对任意的
使得:
定理:在满足上述假设条件1,2和上述算法的迭代过,当
,
从而我们有
证明:
部分1
因为
是函数
的鞍点,所以有:
(1)
再利用
,令
,
从而(1)式有
(2)
部分2
通过定义我们知道,
是
的极小值。由于f是可偏导的凸函数。所以:
又因为
,所以有
,从而
这里表明
是下面这个函数的极小值
(4)
与上面相似的证法可以说明
是函数
的极小值。结合(4)式有
(5)
(6)
再结合
,结合(5)和(6)式有
(7)
证明3
结合(2)和(7)有
(8)
对于(8)式中的第一部分利用
有
(9)
再利用
,因此(9)式中的前两部分有
又因为
,从而上式变为
(10)
接下来,整理(8)和(9)式中剩下的部分,即
再利用
,有
再结合
,从而有
令
从而(8)可以写成
(11)
由证明2中可以看出,
是函数
的极小值,
是函数
的极小值,从而有
结合上面两个不等式,有
又因为
,从而得到
(12)
结合(12)式,使得(11)有
从而有
(13)
从(13)式可以看出
,从而得到
4. 总结
通过正则化的一致性问题,我们可以看到并行和分布式部署优化方案的可行性。我们可以切分数据以及相应的目标函数,也可以切分变量到各个子系统上去,分别作优化,甚至我们可以大胆想象对不同类型数据块用不同的优化算法,结合Consensus问题和ADMM算法,达到同一个全局变量的优化目的;并且在理论上说明了算法的收敛性。
致 谢
本文的撰写感谢程一元老师的指导。
基金项目
巢湖学院省级大学生创新创业训练计划资助项目(S201910380067),巢湖学院省级大学生创新创业训练计划资助项目(S201910380065),巢湖学院校级科研项目(XLY-201903)。