预设时间下的分布式优化和纳什均衡点求解

张苗苗,叶茂娇,郑元世

(1.西安电子科技大学机电工程学院,陕西西安 710071;2.南京理工大学自动化学院,江苏南京 210094)

1 引言

近二十几年来,以多无人机、多传感器等大规模网络为代表的多智能体系统的协调控制与优化问题得到了学者们的极大关注[1-3].其中,分布式优化和纳什均衡点搜索问题作为多智能体系统优化问题中占据重要地位的两类优化问题,成为了近年来的研究热点.在分布式优化和非合作博弈问题中,每个智能体都携带一个目标函数.但这两类问题的区别是:在分布式优化问题中,每个智能体的优化目标均为所有智能体携带的目标函数之和[4].主要考虑智能体如何协同的利用局部信息实现全局目标函数的优化.而在博弈问题中,每个智能体的优化目标是不相同的,分布式纳什均衡点搜索问题主要研究智能体如何依赖自身信息以及与邻居智能体之间的信息交互优化自身的目标函数,因此优化问题中智能体之间的行为是协同的,而纳什均衡点求解问题中智能体之间的行为是从自身利益出发的.

近年来,各类分布式优化方法相继被提出.Nedic等人在局部信息有限的情况下提出了分布式次梯度算法,在该算法中,每个智能体通过与邻居的通信更新自身的状态以收敛到全局最优解[5].由于通信环境中信息交换存在不可预测性,因此任意两个节点之间存在通信链路是一个随机事件,据此Lobel等人提出了随机网络上的分布式次梯度算法,并证明了该算法可以使得多智能体以概率1收敛到系统的最优解[6].文献[7]结合近似梯度和梯度跟踪的思想提出了一种分布式优化算法并证明了算法的收敛性.Nedic等人提出了一类subgradient-push算法[8]以解决非平衡通信网络下的分布式优化问题,该算法需要用到每个节点的出度信息,这一方法在push-sum算法[9]的基础上演变得到的.文献[10]基于梯度法与投影算子等解决了带约束的分布式优化问题.此外,文献[11]还考虑了含不同凸集合约束的分布式优化问题,基于次梯度投影算法提出了一类分布式优化协议.而文献[12]基于一致性和次梯度算法提出了一类连续时间的优化算法,解决含不等式约束时的分布式优化问题,并利用状态转移矩阵的性质得到了智能体的状态与优化问题最优解的误差上界.为了提高算法的收敛速度,文献[13]通过改进梯度项,利用部分历史梯度信息,提出了一类extra优化算法使得智能体的状态能够精确收敛到系统的最优解.文献[14-15]针对智能体目标函数为光滑凸函数的分布式优化问题,提出了快速分布式优化方法.此外,文献[16]和文献[17-18]分别针对原始-对偶域(primal-dual)优化方法和zero-gradientsum优化方法开展研究.

另外,学者们从不同的角度出发,在分布式纳什均衡搜索方面做出了一些有意义的工作.文献[19-20]基于领导者跟随一致性(leader-following consensus)协议和梯度信息提出了一类分布式纳什均衡点搜索算法,并证明了该算法可以使得智能体的状态渐近收敛到纳什均衡点.文献[21]基于leader-following一致性协议和梯度信息解决了混杂博弈问题,并证明了所提出的算法呈指数收敛.文献[22-23]针对双网络零和博弈问题开展研究,并基于梯度算法等提出了一类分布式协议寻找具有鞍点性质的纳什均衡点.文献[24]基于饱和函数、梯度法及一致性协议解决了有界控制输入系统中的分布式纳什均衡搜索问题.文献[25]提出了可线性收敛的分布式纳什均衡搜索方法.

需要指出,上述分布式优化算法/分布式纳什均衡搜索算法仅能保证智能体的状态可以渐近/指数收敛到分布式优化问题的最优解解/纳什均衡点.这表明,分布式优化与非合作博弈问题的精确求解需要消耗无穷时间.然而在实际工程领域中,无穷时间的收敛并不利于实际应用,多智能体系统往往需要在精确时间内完成任务,这使得渐近收敛的方式无法满足实际工程领域中收敛时间的要求.当前对这一类问题的研究文献略少,设计可在有限时间内实现分布式优化与博弈问题有效求解方法兼具理论意义与实际应用价值.为此,文献[26]设计了基于符号函数的有限时间分布式优化方法.文献[27]基于有限时间一致性协议与连续时间零梯度和算法提出了一类有限时间的分布式连续时间算法,利用Lyapunov方法实现了分布式优化问题在有限时间内的有效求解.此外,文献[28]也考虑了有限时间分布式优化问题.文献[29]则研究了固定时间分布式纳什均衡搜索方法.文献[30]利用凸分析理论和Lyapunov稳定性理论解决了固定时间的分布式资源分配问题.

虽然文献[26-30]中所提出的方法可在有限时间内收敛到分布式优化问题的解或纳什均衡点,这将求解方法的收敛速度从无限时间转为有限时间.然而,这些求解方法的收敛时间受智能体的初始状态与系统参数的影响并且无法提前预测,在一定程度上限制了求解方法的实际适用性.为了解决上述问题,设计一类可在预设时间内收敛的分布式优化方法与纳什均衡点搜索方法是十分必要的.在本文研究的同时期,文献[31]假设智能体在离散采样时间进行交互,基于采样数据的算法和辅助变量设计了一类的优化协议,并通过利用离散采样时间的Lyapunov理论解决了指定时间的带等式约束的分布式优化问题.实际上,预设时间的控制和优化是近几年的研究热点.例如,文献[32]研究了二阶多智能体系统的预设时间一致性跟踪问题,并证明了多智能体系统中的领导者与跟随者在预设时间内达成了一致.文献[33]基于Lyapunov函数等实现了预设时间多智能体系统的平均一致性和包围控制.文献[34]建立了一类预设时间的包围控制协议,该协议可以保证多智能体系统中的跟随者可在预先设定的时间内移动到领航者状态所构成的凸包内.文献[35]研究了预设时间的分布式纳什均衡点求解问题,该方法是根据时间函数变换方法,从而严格保证了所提算法的全局收敛性.此外,文献[36]提出了一种新的针对资源分配问题的预定时间分布式优化协议,利用一个连续可微的时间函数实现了预定时间的收敛.文献[37]研究了预设时间的分布式资源分配问题,该算法采用具有指数项的非齐次函数,从而达到预定时间的收敛速度.文献[38]建立了一种新的有限时间控制方法,所提的算法可以保证跟随者可以在任意给定的有限时间内运动到领航者状态所围成的凸包内,这为本文研究预设时间下的分布式优化求解方法和纳什均衡搜索算法提供了思路.

本文考虑智能体之间存在合作与非合作的行为,分别研究了预设时间的分布式优化求解方法与纳什均衡搜索方法的设计与分析,特别地,收敛时间T可以预先设置并与智能体的初始状态和系统参数无关.本文的主要贡献如下:

1) 本文针对分布式优化与纳什均衡搜索问题分别提出一类预设时间分布式优化方法和纳什均衡搜索方法.与文献[26-30]中的固定/有限时间分布式优化方法/纳什均衡搜索方法相比,本文所提出的分布式优化方法和纳什均衡搜索方法可在任意预设时间内收敛,并且该收敛时间独立于智能体的初始状态与系统参数;

2) 基于Lyapunov稳定性理论、图论以及矩阵理论的相关知识,给出了保证所提出的算法可以使得智能体的状态收敛到分布式优化问题的解/非合作博弈问题的纳什均衡点的充分条件.

本文的结构安排如下:第2节介绍了相关的图论以及凸分析理论知识,并给出了一些基本的引理和假设;第3节介绍了预设时间的分布式优化问题,提出一类预设时间分布式优化算法并给出了收敛性证明;第4节介绍了预设时间的分布式纳什均衡点求解问题,给出了预设时间的分布式纳什均衡点求解协议并证明了该协议的收敛性;第5节通过仿真算例验证了所提分布式协议的有效性;最后给出了本文的结论.

为了便于表示,在下表中给出了文中出现数学符号的具体含义.

2 预备知识

本节将介绍一些预备知识,文中符号说明见表1.首先给出有关图论以及矩阵论的相关知识:

表1 符号说明Table 1 List of symbols

无向图若图G中的每条边都是没有方向的,则称G=(V,E,A)为无向图,其中V={1,2,···,n}表示图的顶点集,E ⊂V ×V是边集,A=(aij)n×n为图的邻接矩阵,其中如果(j,i)∈E,则aij ＞0,否则aij=0,且A一定是对称矩阵(aij=aji).智能体i的邻居集定义为Vi={j ∈V|(j,i)∈E}[39].

拉普拉斯矩阵(Laplacian)L=D-A定义为图的拉普拉斯矩阵,其中D为图的度矩阵,A为图的邻接矩阵.拉普拉斯矩阵的基本性质为:L1n=0n,0是它的一个特征值,1n是0特征值所对应的特征向量[37].

定义1(强凸函数)[40]假设S ⊂Rn是一个非空的凸集,f是定义在S上的实函数,如果对于∀x1,x2∈S及每个数λ ∈(0,1),都有

则称f为S上的强凸函数,特别地m=0时,f为凸函数.

定义2(纳什均衡)[19]在一个博弈过程中,如果在其他所有参与者策略确定的情况下,任意一位参与者其选择的策略是最优的,那么这个策略组合就被定义为纳什均衡.即:是纳什均衡点当且仅当

为证明本文所提协议的收敛性,下面给出一些基本的引理以及必要的假设条件.

假设1通信拓扑图G为无向连通图.

引理1[41]在假设1成立的前提下,矩阵Q=L+W是正定实对称矩阵,其中L是图G的拉普拉斯矩阵,W是正定实对角矩阵,即:W=diag{wi},wi ＞0.

引理2[42]如果矩阵Q是正定实对称矩阵,则有以下不等式成立:

其中常数m ＞0称为强凸函数f(x)的凸性参数.

3 预设时间的分布式优化

本节考虑智能体之间的行为是合作的,研究了基于多智能体系统的预设时间分布式优化问题.考虑有n个智能体的多智能体系统:V={1,2,···,n},在该系统中,每个智能体都会携带一个目标函数fi(z),并且对于所有的智能体i ∈V,只有智能体i能够获得目标函数fi(z)的信息,所有智能体通过与邻居的交互协同的最小化每个智能体目标函数的和函数.据此,分布式优化问题描述如下:

在该优化问题中,每个智能体通过与邻居的交互获得邻居的信息从而更新自身的状态.本文的目的是设计一类预设时间的分布式优化协议能够使得智能体在预设时间T内通过局部信息收敛到全局目标函数的最优解.为了设计该分布式协议,假设每个智能体i都产生一个变量xi(t)用以估计优化问题(2)的最优解.

因此,针对问题(2),本文在文献[12]的基础上结合一致性协议和梯度下降算法,提出了一类在预设时间内收敛的分布式优化协议

其中:xi(t)∈R表示智能体i的状态,μ ＞0为控制增益,常数c ＞0,aij是邻接矩阵A中i行j列的元素,∇fi(xi(t))表示智能体i的目标函数fi(z)在z=xi(t)处的梯度,T为预设的收敛时间.

假设2智能体i的目标函数fi(z)是二阶连续可微的强凸函数,i ∈V.

注1由于智能体i的目标函数fi(z)是二阶连续可微函数,因此微分方程(3)的解存在,且也是强凸函数,则z*是唯一的最小值点.因此所有智能体的状态不仅可以在预设时间收敛到优化问题的最优解z*,还能够在预设时间内达到一致.

下面给出预设时间分布式优化问题的主要结果.

定理1如果假设1-2成立,则在协议(3)下,所有智能体的状态在预设时间T内收敛到问题(2)的最优解.即存在z* ∈Z*,使得=z*成立.

证此定理的证明可以通过以下步骤形成:首先,将式(3)写成如下矩阵的形式:

其中对任意的μ ＞0,都可以选择一个正定对角矩阵W使得以下式子成立:

则根据式(5)有

因此,当t→T时,V(t)→0,则可得当t→T时,‖δ(t)‖→0,即:=z*成立,综上可得,协议(3)可以使得多智能体的状态在预设时间内收敛到优化问题(2)的最优解. 证毕.

注2本文与文献[31]中的两种方法均能实现预设时间的收敛,并且两种方法得到的收敛时间均独立于系统参数与初始条件.但与该文献不同的是,本文研究的是一般的分布式优化问题min,其中z为所有局部目标函数fi的共享决策变量.因此,每个智能体i需要产生局部变量xi去估计优化问题(2)的最优解.并且当xi达到最优解时,智能体的局部估计值能够达到一致状态(i.e.,x1=x2=···=xn=z*).而文献[31]研究的是一类特殊的分布式优化问题min,其中每个目标函数fi只与自身的决策变量zi有关.因此文献[31]中的方法无法使用于本文所考虑的分布式优化问题.

4 预设时间的分布式纳什均衡求解

本节研究了预设时间下的分布式纳什均衡点求解问题,与分布式优化问题不同的是,该问题中智能体之间的行为是从自身利益出发的.考虑有n个智能体的多智能体系统:V={1,2,···,n}表示,每个智能体i均利用局部信息调整自身的行为使得其成本最小,该问题描述如下:

其中fi(·)为每个智能体i的成本函数.记为智能体i收敛到纳什均衡点时成本函数的最优值,ui为控制输入.

在非合作博弈问题(6)中,由于假设每个智能体仅能获得其邻居的信息,无法得到那些非邻居智能体的行为状态,因此每个智能体会对其他智能体的行为产生一个估计值,并利用与邻居之间的信息交互更新估计值,然后基于梯度方法更新自身的行为状态.本文的目的是设计一类搜索协议使得每个智能体在预设时间T内通过局部信息调整自己的行为收敛到纳什均衡点,从而最小化自身的成本.

在文献[19]的基础上,本文基于一致性协议和梯度算法,提出了一类预设时间的分布式纳什均衡点求解协议

注3在假设4的条件下,问题(6)的纳什均衡点存在且唯一,其中R(x)=0n的充要条件是x=x*[19].

下面给出预设时间分布式纳什均衡点求解问题的主要结论.

定理2如果假设1,3-4成立,则在协议(7)下,存在一个正常数k*,使得增益k ∈(0,k*)时,所有智能体的状态在预设时间T内能收敛到问题(6)的纳什均衡,即

证此定理的证明可以通过以下步骤形成:首先,式(7)可以写成如下矩阵的形式:

最后,对上式在[0,t]上积分得到

因此,根据式(10)可以得到

5 仿真

在本节中,本文通过两个例子来验证理论结果的有效性.

例1考虑由4个智能体{1,2,3,4}构成的多智能体系统,假设智能体的通讯拓扑图由图1所示,每个智能体仅与自己的邻居通信,且通信拓扑图为无向连通图,对应的邻接矩阵和拉普拉斯矩阵为

图1 例1中智能体的通信拓扑图Fig.1 The communication topology of all agents in example 1

假设每个智能体的目标函数如下:

图2 在协议(3)下,智能体的状态xi(t)(i={1,2,3,4})轨迹图(T=3)Fig.2 Under protocol (3),the trajectories of the agent’s states value xi(t)(i={1,2,3,4})(T=3)

图3 误差δ的收敛轨迹图(T=3)Fig.3 Trajectories of convergence errors δ(T=3)

从仿真结果可以看出,选定的初始状态虽然与最优解的相差很大,但是在所设计的协议下均能够在预设时间收敛到最优解,这也验证了定理1的有效性.

例2考虑由5个智能体{1,2,···,5}构成的多智能体系统,智能体的通信拓扑图由图4所示,每个智能体仅与自己的邻居通信,且通信拓扑图为无向连通图,对应的邻接矩阵和拉普拉斯矩阵为

图4 例2中智能体的通信拓扑图Fig.4 The communication topology of all agents in example 2

从图4中可以看出每个智能体仅与自己的邻居通信且成本函数仅受邻居和其自身决策的影响,假设每个智能体的成本函数如下:

其中每个成本函数fi(xi,x-i)满足假设3-4.令系统参数c=1,收敛时间为T=6.

设置智能体的初始值为:x(0)=[3 2-12/37-4/9 1/2]T,yi(0)=[0 0 0 0 0]T.每个智能体根据协议(7)更新自身的状态,并存在一个正常数k*,使得k ∈(0,k*),此时得到了与理论一致的结果.

图5表示智能体i的行为xi(t)在预设时间T=6收敛到非合作博弈问题minfi(x)的纳什均衡点:x*=[0.5063 0.2564-0.0769-0.0256-0.0298]T,i={1,2,3,4,5}(令伪梯度向量R(x)=05得到唯一的纳什均衡点).

图5 协议(7)下,智能体的状态xi(t)(i={1,2,3,4,5})轨迹图Fig.5 Under protocol(7),the trajectories of the agent’s states value xi(t)(i={1,2,3,4,5})

图7表示在初始估计值均为0的情况下,智能体i对智能体j的估计值yij(t)在预设时间T=6 收敛到xj(t),而每个xj(t)在预设时间收敛到纳什均衡点,因此yij(t)在预设时间收敛到纳什均衡点.图6和图8分别表示智能体的行为xi(t)与纳什均衡的点的误差和智能体i对智能体j的估计值yij(t)与纳什均衡的点的误差在预设时间T=6收敛到0,即θ和φ在预设时间T=6收敛到0.

图6 误差θ的收敛轨迹图(T=6)Fig.6 Trajectories of convergence errors θ(T=6)

图7 在协议(7)下,每个智能体对其他智能体估计值yij(t)的轨迹图,即T=6时yij(t)→xj(t)Fig.7 Under protocol (7),the trajectories of the agent’s states value yij(t),i.e.yij(t)→xj(t)as T=6

图8 误差φ的收敛轨迹图(T=6)Fig.8 Trajectories of convergence errors φ(T=6)

由仿真结果可以得到,在给定智能体的初始状态后,智能体是可以在预设时间搜索到纳什均衡点,因此验证了定理2的有效性.

6 结论

本文基于无向图解决了预设时间下的分布式优化/纳什均衡点求解问题,针对分布式优化问题/纳什均衡点问题结合一致性和梯度协议提出了一类预设时间的优化算法/纳什均衡点求解算法.在每个智能体仅能获得有限信息的情况下,当智能体的目标函数是强凸函数时,通过选取适当的Lyapunov函数证明了多智能体系统可以在预设时间内收敛到优化问题的最优解/非合作博弈问题的纳什均衡点,特别地,收敛时间独立于多智能体的初始状态与系统参数,并且可以预先设计收敛时间.仿真算例验证了所提算法的收敛性,结果表明给定智能体的初始状态后,智能体均能够在所提协议下实现预设时间的收敛.