带事件触发机制的分布式量化随机无梯度投影算法

谢奕彬,高文华

(华南理工大学数学学院,广东广州 510640)

1 引言

有线和无线技术的最新进展导致了大规模网络的出现,带来了多智能体网络中的许多新应用,其中分布式优化问题得到了广泛关注,其目标函数为网络中所有智能体的目标函数之和,每个智能体在仅知道自身目标函数的情况下,利用网络通信对状态信息进行更新,最终所有的智能体的状态在最优解处达到一致.分布式优化理论和应用已经成为当代系统和控制科学的重要发展方向之一,并在许多领域取得了重大突破[1-7].例如近年来逐渐取得广泛关注的智能电网调度策略、分布式机器学习、基于分布式优化的信息-物理系统的优化控制、自主式水下机器人的队形控制、基于算术均值融合的分布式随机集多目标跟踪等[8-10].

分布式优化问题的特点是算法设计依赖于节点组成的通信网络拓扑结构和节点间的信息传输方式,而传输的信息依赖于目标函数模型,不同性质的目标函数假设意味着个体能获取的信息不同.下面就从网络结构、信息传输和目标函数3方面阐述已有的与本文相关的研究结果.

早期的研究大多考虑在平衡网络中分布式优化算法,如Nedi´c(2009)提出了分布式次梯度算法[11-12],Srivastava(2010)研究了带白噪声的分布式次梯度算法[13],Lin(2016)研究了通信带延迟的分布式次梯度算法[14].

现实中智能体很可能分布在时变不平衡网络中,此时通信网络图的权重矩阵不再是双随机的.为了解决不平衡网络所带来的影响,Nedi´c(2015)提出了subgradient-push算法[15],只要求权重矩阵是列随机矩阵,随后(2017)提出了Push-DIGing算法,要求权重矩阵是列随机且采用了固定步长.而Xie(2018)借助优化问题的上境图形式抵消了不平衡图给分布式次梯度算法带来的影响[16].

上述分布式算法要求智能体准确地接收到邻居的状态信息.但随着模型规模变大,例如在深度学习算法中,每次迭代的通信开销成为主要瓶颈,量化通信是解决此问题的主要方法,但这导致了许多的结果无法直接应用.Rabbat(2005)研究了分布式量化增量优化算法[17],Nedi´c(2008)研究了分布式量化次梯度算法[18],Taheri(2020)研究了量化graident-push算法[19].此外,Li(2011)提出了一个基于编译码方案的量化器[20],Yi(2014)应用这个编译码的量化方案设计了分布式量化次梯度算法[21].Zhang(2018)将节点间的量化信息减少到只用符号信息[22].

为了进一步解决通信成本问题,可以让智能体选择在必要时才与邻居通信.Yu(2019)研究了基于事件触发机制和传输延迟的分布式优化算法[23],Hayashi和Naoki(2020)提出了基于事件触发机制的定步长次梯度分布式算法[24],Li(2018)结合了事件触发机制和量化的技术,提出了基于事件触发机制的分布式量化次梯度算法[25].

上述文献为解决目标函数不可微都采用了次梯度的方法,当目标函数的次梯度求解太过于繁琐时,Nesterov(2017)提出了一种随机无梯度方法[26].随机无梯度方法仅要求目标函数是凸的且Lipschitz连续,其求解过程不需用到梯度信息,具有广泛的应用前景.文献[27-33]将随机无梯度方法应用到分布式算法上.特别地,Yuan(2015)基于gradient-push提出了不平衡图上的随机无梯度算法[32],但该算法不易拓展到约束优化问题.Ding(2017)提出了分布式量化随机无梯度投影算法[33],但该算法仅适用于时变平衡图的情况且在文章中没有给出具体的量化方案.

目前,分布式随机无梯度方法有待深入研究,本文在文献[33]的基础上,应用文献[34]中对梯度加权的方法,将随机无梯度投影算法拓展到时变不平衡图上,该算法仅要求权重矩阵是行随机的,这在基于广播的通信机制中具有更好的实用性.同时为减少通信成本,本文结合了编译码动态量化规则和事件触发机制提出了基于事件触发机制的分布式量化随机无梯度投影算法,降低了对通信网络的带宽要求且更大效率地利用通信资源.

本文的主要结果是如下3个方面:

1) 在分布式优化算法的基础上,考虑到了通信带宽和通信成本的限制,采用了基于事件触发的动态编译码方案进行信息传输,有效地降低了对网络通信带宽的要求和通信次数.此外,采用了随机无梯度方法替代传统的次梯度方法,仅要求目标函数是凸的且Lipschitz连续.

2) 在所有的量化器不饱和的条件下,第3.2节给出一种时变不平衡有向图上的分布式算法求解优化问题的近似解.

3) 在所有的量化器不饱和的条件下,第4节对所提算法进行收敛性分析,给出算法的收敛速率,并求出了量化器不饱和的量化水平下界.

本文余下部分的结构如下:第2节介绍了分布式优化问题并给出预备知识;第3节陈述了编译码量化规则和事件触发设置,设计了基于事件触发的分布式量化随机无梯度算法;第4节研究了所提出的算法的收敛性并给出使量化器不饱和的量化水平下界;第5节提供了具体的仿真来验证分布式优化算法的有效性;最后,第6节给出结论.

记号:所有向量均视为列向量.智能体i涉及的变量(可能是标量、集合和函数)均标有下标i,例如xi(k)智能体i在迭代时刻k的状态值.用代表涉及量化的相关变量估计,例如(k)代表智能体j得到对xi(k)的量化估计值.用˜·代表涉及事件触发机制的相关变量估计,例如(k)为考虑事件触发机制后智能体j得到对xi(k)的估计值.设1m为所有元素均为1的m维列向量,I为m维单位矩阵,R和Rn分别为全体实数集合和n维实数空间.向量x的欧式范数和无穷范数分别记为‖x‖和‖x‖∞,

向量x在非空闭凸集X上的投影记为PX(x),

∇f(x)代表f(x)的梯度,问题(1)-(2)的最优解分别记为x∗和,即

2 问题描述与预备知识

本文考虑一个由V={1,2,···,m}标记的智能体网络.智能体之间可以局部的交换信息.多智能体系统的共同目标是协同求解一个凸优化问题,该问题的目标函数是所有智能体局部目标函数的和,

其中:fi:Rn →R是智能体i的局部目标函数,全局约束集X ⊆Rn.

假设1a)X是一个有限的非空的闭凸集,半径为CX.即‖x‖≤CX,∀x ∈X.

b) 优化问题(1)的最优解集非空.

c) 局部目标函数fi(x)为凸的且L0(fi)-Lipschitz连续,即存在L0(fi)＞0使得

注1文献[34]采用次梯度算法,假设中不要求目标函数满足Lipschitz连续的条件,只要求次梯度存在且有界,而根据文献[35],次梯度有界其本质等价于目标函数Lipschitz连续.在非光滑优化算法中,存在目标函数非光滑非Lipschitz连续的优化算法,如文献[35],但该算法依然需要计算次梯度.随机无梯度方法如文献[27-33]皆要求目标函数Lipschitz连续,以保证光滑后的函数能逼近原函数.本文假设1是随机无梯度方法的通常假设.

由于每个局部目标函数fi(x)都是非光滑的,则fi(x)的梯度不存在,而次梯度信息在有些实际问题中计算相对复杂,此时基于梯度或次梯度的方法不能有效的解决优化问题(1).为此,本文通过高斯光滑函数fi,µi(x)逼近原目标函数进而得到随机无梯度,用于代替传统的梯度信息.由文献[26]知高斯光滑函数fi,µi(x)和随机无梯度定义如下:

其中µi是(x)的非负光滑参数.

其中u是单位球体上均匀分布的随机向量.由文[26]可知fi,µi(x)是可微的,且有

其中F(k)是由迭代算法从0步到k −1步产生的随机变量构成的σ-代数,即

注21)次梯度的计算需要一定的技巧与时间,且在次梯度的计算过程中,有时需要额外的内存来储存中间变量,这对于有记忆限制的模型不再适用.2) 当系统的确切表达式不可知,仅知道系统的输入与输出时,基于次梯度的算法不再适用但可以采用随机无梯度方法[36-37].

引理1[26]若fi(x)满足假设1(c)则

a)fi,µi(x)是凸函数,且满足

将问题(1)的目标函数用所对应的高斯光滑函数替代,得到问题(2).

多智能体之间的信息通信可以建模成时变有向

图G(k)=(V,E(k)),其中节点i ∈V代表第i个智能体,有向边(i,j)∈E(k)表示在k时刻信息可以从智能体i传送到智能体j.A(k)=[aij(k)]为时变有向图G(k)的非负权重矩阵,当(i,j)∈E(k)则有aji(k)＞0,否则aji(k)=0.如果存在一系列的有向边(i1,i2),(i2,i3),···,(it−1,it),使 得(il−1,il)∈E(k),l=2,···,t,称k时刻i1是可达it.如果任意节点都是可达其他节点的,称时变有向图是强连通的.本文对时变有向图的连通性有如下常见的假设,见文献[15,34,38].

假设2时变有向图是B-强连通的,即对任意k≥0,存在一个正整数B使得

是强连通的.

在假设2的条件下,时变有向图G(k)不需要在任意时刻k都保持连通,但G(k)是B-强连通的,以保证在B连续时间段内信息能从一个节点传输到另一个节点.

注3对于时变不平衡有向图,权重矩阵的双随机条件不再满足,许多平衡图下的算法不再适用,因此有必要设计新的分布式优化算法.文献[15]提出gradient-push算法,该算法要求权重矩阵是列随机的,即=1,为此每个节点要求知道它的出度.而本文仅要求权重矩阵是行随机的,相比于双随机矩阵和列随机矩阵,行随机矩阵在通信机制中有更好的实用性.

定义转移矩阵A(k:s):

引理2[34]在假设2成立的条件下,对于所有s≥0,存在一随机向量π(k),即πT(k)1m=1,

a) 对任意i,j ∈V和k≥s,有

其中常数C ＞0,0＜ξ ＜1.

b) 对任意i ∈V和k≥0,有πi(k)≥η成立,其中η ＞0.

智能体在传递信息之前必须将模拟信号转换成数字信号,而这就必须涉及到量化器的设计和使用.最基本的量化操作就是取整,一般称之为均匀量化.这种量化器易于实现和分析,但遗憾的是如果要量化的信息具有非常大的幅值,则对量化结果进行编码就需要相当多的比特数.这将会给通讯网络带来巨大的负载.许多研究人员提出了新的量化器形式,例如抖动量化器,对数量化器等,这些量化操作相比于基础的均匀量化来说均有不同方面性能的提升,但这种静态的量化方案所产生的量化误差是从始至终都存在的.文献[20]提出了一种动态量化的方案,通过在量化编译中引入动态的伸缩函数β(k),随着智能体状态的变化动态地调整量化信号,以此逐步消除量化对信号传输的影响.

传统的分布式优化算法通常会固定采样周期,在每个周期开始的时候,传感器会对智能体的状态进行采样量化并发送出去,但这种模式会造成不必要的网络资源的浪费.一个最明智的方法是通过事件触发更新.其主要的思想是让智能体在必要时刻才进行信息传输,更确切地说,只有当系统的某一项指标超过了阈值,通信才会发生.从这个意义上讲,事件触发策略比传统的固定采样周期的策略在减少不必要的通讯方面更具有优势.

下面本文结合动态量化编译和事件触发机制,提出基于事件触发机制的分布式量化随机无梯度投影算法解决不平衡图上的分布式优化问题.

3 基于事件触发的分布式量化随机无梯度算法

3.1 编译码量化规则和事件触发设置

上述静态均匀量化器的量化水平为2K+1,所需的比特数为nlog2(2K+1).可以通过降低量化水平减少信息传输所需的比特数,从而减少信息传输所需的带宽,但量化水平过小会导致量化器饱和从而算法不收敛.为此,本文采用与文献[20,25]类似的动态编译码方案替代传统的静态均匀量化器,降低量化水平的同时确保量化器不饱和.

在k时刻,有向通信通道(i,j)上信息发送端智能体i的编码器设计如下:

其中:ξij(k)是编码器的内部变量;xi(k)和sij(k)分别为编码器的输入和输出;kij表示智能体i在k时刻之前的最新事件触发时刻;β(k −1)是伸缩函数,用于放大缩小信号xi(k)−ξ(kij);Iij(k)为示性函数,

信息接收端智能体j的解码器设计如下:

3.2 基于事件触发的分布式量化随机无梯度投影算法

为解决分布式优化问题(1),本文提出如下的基于事件触发的分布式量化随机无梯度投影算法:

4 收敛性分析和量化水平估计

为证明所提出算法的收敛性,本文先给出下面4个引理.

引理3[40]投影的非扩张性.

引理4卷积上界公式:

引 理5[41]设{ι(k)},{χ(k)}和{ψ(k)}是非负的随机序列,{ζ(k)}为确定性的非负序列.记F(k)是通过ι(1),···,ι(k),χ(1),···,χ(k),ψ(1),···,ψ(k)产生的σ-代数,若有

引理6在量化器不饱和的条件下有

下面是本文的主要结果.在量化器不饱和的条件下,定理1和定理2证明了所提算法的收敛性,定理3给出了算法的收敛速率,定理4求出了使得量化器不饱和的最小的量化水平.

定理1在量化器不饱和及假设1-4成立的条件下,迭代序列xi(k)几乎必然收敛到问题(2)的最优解.即存在使得

倒数第3个不等式是由于(x)的凸性,最后一个不等式是由于范数的凸性和权重矩阵A(k)是行随机的,结合d1的定义和式(22)有

注6由假设3-4可知,定理2中不等式右边的第1项在k趋向∞时会趋于0,第2项是由于本文的算法采用了随机无梯度方法而产生的.由定理2可知算法产生的序列E[f((k))]能收敛到问题1最优值的邻域,其半径由µi和L0(fi)所决定,在µi →0,∀i ∈V的情况下,当k →∞,E[f((k))]收敛到f(x∗).

为使得量化器不饱和可以一直采用较大的量化水平,但会造成通信资源的浪费.现在笔者给出随迭代时间变化的量化水平更新规则以节约通信成本.

定理4在假设1-4成立和随机无梯度有界的条件下,若K(k)满足

即量化器在k+1时刻不饱和,故定理2成立.

5 数值仿真

考虑由10个智能体组成的多智能体系统:

假设x ∈R,X=[−2,2].智能体i的局部目标函数如下:

其中:pi=10,∀i ∈V,λ=10,aij和bij都是按照正态分布随机生成的.通信网络按照图1给出了时变的一般不平衡有向图连接,其中任何单个图都不连通的,但它们的联合图是连通的.假设在整个迭代过程中,图G(k)在图1中的两个图上连续变化.

图1 时变联合强连通有向图Fig.1 Time-varying joint strongly connected directed graph

由引理1的结论

将本文算法与分布式gradient-push,原有的不带事件触发和量化机制的随机无梯度投影方法在相同参数设置下进行对比.图2 比较了3 种算法误差f(x)−f(x∗)的收敛情况,结果表明3种算法都能收敛到最优解.

图2 误差f(x)−f(x∗)的收敛情况Fig.2 Convergence of error f(x)−f(x∗)

相比于gradient-push算法,虽然gradient-push算法有更快的收敛速率,如图3所示,但带投影算子的gradient-push的收敛性尚未得到证明,且算法要求权重矩阵是列随机矩阵,这在构造权重矩阵时要求每个智能体知道节点的出度.

图3 Gradient-push算法状态值xi(k)的收敛情况Fig.3 Convergence of state value xi(k) of Gradient-push algorithm

而本文的算法是针对约束优化问题,且仅要求权重矩阵是行随机矩阵,在基于广播的通信机制中具有更好的实用性.相比于原有的不带事件触发和量化机制的随机无梯度投影方法,两种算法的收敛速率变化不大,如图4-5所示.但本文的算法不要求智能体准确地接收到邻居的状态信息,且应用了量化通信和事件触发机制,降低了对通信网络的带宽要求且减少了通信次数,如图6所示,其中*为事件触发时刻.图7显示了不同参数µi对状态值收敛情况的影响,可以看出,选取不同µi值,虽然不会影响到智能体的收敛速率,但µi过大时,会影响到状态值收敛的精确度.

图4 Gradient-free projection算法状态值xi(k)的收敛情况Fig.4 Convergence of state value xi(k) of Gradient-free projection algorithm

图5 本文算法状态值xi(k)的收敛情况Fig.5 Convergence of state value xi(k)of the algorithm in this paper

图6 事件触发时刻数列Fig.6 Event trigger time sequence

图7 不同参数µ对智能体1的状态收敛情况的影响Fig.7 The influence of different parametersµon the state convergence of agent 1

6 结论

本文结合编译码动态量化规则和事件触发机制提出了一种基于事件触发的分布式量化随机无梯度投影算法,用于解决分布式约束优化问题.所提出算法适用于一般行随机的时变不平衡有向图,这在基于广播的通信机制中具有更好的实用性.本文证明了当目标函数为凸且Lipschitz连续,在选取合适的量化水平后,所有的智能体的状态值收敛到其高斯光滑近似函数的最优解,序列E[f((k))]能收敛到问题1最优值的邻域,并给出了选择不同步长时算法的收敛速率.数值仿真验证了所提算法的收敛性,表明了在合理的设置事件触发机制和量化通信的规则后,降低了对通信网络的带宽的要求,更有效地利用通信资源,同时不会降低原有分布式随机无梯度算法的收敛速率.