基于有向图的分布式连续时间非光滑耦合约束凸优化分析

刘奕葶 马铭莙 付 俊

在多智能体网络中,分布式优化是决策和数据处理的重要研究方向,近年来得到广泛研究[1-3].每个智能体都有一个局部目标函数,通过各智能体与其邻居进行信息交互,共同协作实现由局部目标函数之和构成的全局目标函数最小.随着近年来互联网、大数据等新兴技术的发展,资源分配在网络系统中得到广泛的应用,如电力系统中的经济调度、机器人研究、智能交通、能源制造、无线网络利用率最大化等[4-8],使系统具有更高的功能效率、稳定性、安全性和可靠性.

分布式优化是通过各智能体间协调合作来实现优化任务,每个智能体只能访问自己的局部目标函数和局部约束集,与优化问题相关信息分别存储在各智能体中,这充分保证了信息的隐私安全[2].其次,各智能体与其邻居节点进行信息交换即可,不必将数据信息传递到中心节点,更加节约了通信成本,也避免了集中式算法会引入的通信单点故障和传感器故障等,极大地提高了系统的鲁棒性,也避免了对于处理大规模的复杂优化问题时,集中式算法会由于智能体之间的通信、计算等限制变得低效[9].

大多数的分布式算法是基于无向通信网络实现的,如文献[10]提出的分布式精确收敛的一阶算法是通过前两次迭代的状态和梯度信息来更新节点的状态.分布式不精确梯度方法和梯度跟踪算法中每个节点采用相同的步长,变量的更新规则中并未用到动态一致性算法,最终跟踪的梯度不是全局平均梯度.之后有研究提出在无向图网络下,改进分布式不精确梯度方法和梯度跟踪技术,使其在不同节点采用不同步长,加速优化算法[11-12].

而许多实际问题中的通信网络往往是有向的,如无线电传感器网络、手机通讯网络等[13].有向图中算法收敛是一项具有挑战性的工作,如文献[12]中所提算法只适用于无向网络,在有向网络下其算法不具备收敛性.文献[14]考虑在强连通加权平衡有向图上智能体的资源分配问题.当局部目标函数强凸时,其满足等式路径约束和局部凸集的约束条件下,分布式连续时间投影算法的输出状态可渐近收敛到资源配置问题的最优解.对局部凸集约束条件进行松弛并提出可以在强连通加权不平衡有向图上的自适应连续时间梯度算法,其中局部目标函数及其梯度分别满足强凸性和Lipachitz 条件,并证明其指数收敛到问题的最优解.文献[15]结合Push-Sum 算法的核心思想,提出满足一致强连通时变有向图网络下有效收敛的Subgradient-Push 算法.假设每个节点知道其对应的出度信息,在次梯度有界的标准假设下使每个节点收敛并且都能找到最优值.

在实际应用中,当系统对实时优化有较高要求时,通常会考虑有向网络下的分布式连续时间算法,其对系统的稳定性及灵活性的高要求可以用来解决资源分配问题[16-19].文献[20-21]中提出的分布式投影算法分别用于解决无向图和加权平衡有向图的资源分配问题.文献[20]在满足线性等式约束和局部可行集约束的前提下,基于差分投影提出的连续时间算法,可以不通过初始化对无向网络下的各智能体进行决策分配.文献[21]考虑了满足局部可行集约束的非光滑代价函数在强连通加权平衡有向网络下的分布式资源分配问题.利用微分包含和LaSalle 集值不变性原理,证明了解的唯一性和算法的收敛性.但文献[20-21]所提的连续时间算法对于分布式资源分配仍存在一定的局限性.文献[20]的算法对加权平衡有向图的有效性仍需探索;文献[21]中算法在运行前需计算智能体在切锥上的投影,增加了各智能体之间的交互和计算时间.

分布式优化问题中最简单的情况是无约束优化[22-23].如文献[22]通过构造李雅普诺夫函数并进行稳定性分析,使提出的连续时间分布式算法能够指数收敛到全局最小值.在无向网络下的分布式连续时间非光滑凸优化问题中[24],只考虑局部可行集约束,通过算法在切锥上的投影,使其在满足局部可行集的约束条件下使算法收敛.此外,文献[25]中提出了一种分布式连续时间多智能体系统,使目标函数在满足不等式路径约束、等式路径约束和局部可行集的约束下算法收敛,找到全局目标函数的最小值.上述研究中大多没有考虑耦合约束,然而耦合路径约束出现在许多实际应用中,具有重大研究价值.

具有耦合约束的分布式优化,其中各个智能体的决策变量的可行域会受到其他智能体的影响.然而在实际应用中,网络拓扑图中没有中心点时,耦合约束并不能够满足对各个智能体的资源分配[26].在文献[26]中考虑具有耦合的非线性约束,提出一个改进的拉格朗日函数,引入局部乘子来解耦约束,并使用非光滑罚函数保证算法的正确性,使其鞍点不仅能得到优化问题的最优解,其原对偶次梯度的算法也是完全分布的.文献[27]研究解决不等式约束的优化问题,通过Caratheodory 意义上原始对偶动力学的解的存在的唯一性和连续性,建立在原始对偶动力学下全局渐近收敛的分布式算法.

本文基于文献[28]中提出的分布式连续时间投影算法进行延展,通过投影的定义及性质,结合线性代数理论分析,找到了证明算法的平衡解为分布式优化问题最优解的充分必要条件,并且可以适用于强连通加权平衡有向通信网络拓扑图.在满足耦合不等式约束和局部可行集约束的情况下使非光滑全局目标函数最小,找到分布式优化问题的最优解.大多数分布式优化问题考虑的是无约束、等式约束或不等式约束[23-25,29-31],与文献[24]中的局部可行集约束相比,我们考虑的耦合不等式路径约束更具有通用性,难度更高且计算更复杂,适用范围更广.本文研究了分布式优化在强连通有向通信拓扑图下的连续时间投影算法,和文献[12]中无向网络下的离散时间系统相比,可以实现实时优化,稳定性更高.本文通过Moreau-Yosida 正则化近似函数解决非光滑目标函数最优问题,比文献[24]和文献[26]中提出的方法更易于实现.结合文献[28]中所提算法找到在强连通加权平衡网络下,满足耦合不等式路径约束和局部可行集约束的最优解.

本文结构安排如下.第1 节介绍本文考虑的分布式优化问题和预备知识;第2 节提出应用在强连通有向图的分布式连续时间投影算法,并分析证明算法的平衡解为优化问题最优解的充分必要条件;第3 节通过数值实验验证理论结果;第4 节总结本文的主要结论和未来研究方向.

符号说明:R表示实数集,Rm和Rmn分别表示m维列向量集和m×n矩阵空间.Im是m维单位方阵.0m是一组元素为0 的m维列向量,1m是一组元素为1 的m维列向量.‖·‖是欧几里德范数.TS(x) 是x在集合S上的切锥.Ni={j:(j,i)∈E}是节点i的邻居集合.给定一个矩阵A,r ange(A) 表示矩阵A的像,k er(A) 表示矩阵A的核.λmax(A)表示矩阵A的最大特征值.A ⊗B表示矩阵A和B之间的Kronecker 积.矩阵A ≥0 (A＞0) 时,A为半正定(正定)矩阵,A∈Rmm.是智能体i的入度,是智能体i的出度.

1 问题描述与预备知识

1.1 问题描述

考虑如下分布式优化问题[14]

通信网络是由M个智能体组成,x i∈Rm是全局决策变量,Xi∈Rm是各智能体的局部可行集,每个智能体i∈I={1,···,M}对应一个局部决策变量其中,X0是各智能体局部可行集的交集.其对应的局部目标函数和局部耦合不等式约束分别是f i(xi):Rm →R和gi(xi):Rm →Rn,各智能体只能访问自己的局部目标函数fi和不等式约束gi,其中,x=col(x1,x2,···,x M).通过分布式连续时间投影算法让各智能体与邻居节点信息交互协同合作,在满足耦合不等式约束和局部可行集约束下,使各智能体状态收敛到全局最优解,全局目标函数值最小.

本文对目标函数、耦合不等式约束和拓扑图等作出以下假设.

假设 1.fi和gi是局部可行集Xi上的非光滑凸函数,其中Xi是闭凸集且∀ i∈I.

假设 2.考虑的信息交换图G是强连通加权平衡有向图.

假设 3.问题 (1) 至少存在一个有界的解.

注1.若局部Lipschitz 函数g是凸函数,则∂g(x) 在x处的次微分满足:∂g(x)={s∈Rn:g(y)≥s称为次梯度.

注2.在假设1 的条件下,函数非光滑是指目标函数和约束函数均为非连续可微函数.我们通过Moreau-Yosida 近似函数,使非光滑函数转化为连续可微函数[28],即

其中,γ＞0,函数f γ(x),g γ(x) 分别是非光滑凸函数f(x),g(x) 的Moreau-Yosida 近似函数.根据文献[28]和文献[32]可知,近似后的函数f γ(x),g γ(x) 为连续可微的凸函数,并且满足关系式supγ＞0fγ(x)=limγ→0fγ(x)=f(x),supγ＞0gγ(x)=limγ→0gγ(x)=g(x).值得注意的是,f(x),g(x) 是凸函数,那么存在唯一的y使y‖2},其中y称为f在x处的近似算子.

1.2 预备知识

定义2.NS(x) 是x在集合S上的法锥[28]

其中,在集合S上的法锥满足如下性质:

其中,NX(y)=col(NX(y1),···,NX(yM)).根据式(10) 中的等式关系可得,y i=yj,其中,i,j∈I.因此一定存在yi=x*,其中x*∈Rm,∀ i∈I.则式(8) 可以写为

等价于引理1 中的式 (6).

2 分布式连续时间投影算法

2.1 算法设计

针对问题 (1),提出如下分布式投影算法.将非光滑目标函数f(x) 和g(x) 代入Moreau-Yosida 近似函数中,则分布式投影算法可以写为

对比文献[12]中用于离散时间系统的DIGing算法,第2.1 节中的算法不仅用到次梯度来保证算法收敛到最优解,并且增加积分反馈项来校正由于局部梯度引起的误差,最终满足算法在连续时间系统中的强连通加权平衡有向图的收敛.

引理 2[28].当目标函数f局部有界,并且解的集合为非空凸集时,对于任意初始点x i(0)∈Xi,则每个智能体xi始终在其局部可行集Xi内.

2.2 主要结果

假设分布式优化算法 (15)～(18) 一致收敛的平衡解为c ol(x*,τ*,µ*,s*),在强连通加权平衡有向通信网络下,证明其平衡解为优化问题 (1) 的最优解需满足的充要条件.

定理1.在假设1～3 成立的条件下,满足式(19) 和式(20) 时,算法 (15)～(18) 的平衡解col(x*,τ*,µ*,s*)是优化问题取得最优解的充分必要条件,并且x*∈Rm是问题 (1) 的最优解.

下面提出的定理2 是根据文献[28]证明算法(15)～(18) 的输出轨迹x收敛于同一个平衡解,并结合定理1 的结论得到的.即分布式投影算法在强连通加权平衡有向图网络下,算法渐近收敛到优化问题 (1) 的最优解.

由凸函数的性质可得如下两个不等式关系:

代入定理2 中的设定条件可知,上式为半正定矩阵.因此能够得出J(t)≤J(0),进而证明了各参数x,τ,µ,s的有界性.结合引理2 可知,当目标函数f局部有界时,对于优化问题 (1) 的任意初始点x i(0)∈Xi,每个智能体xi始终在局部可行集Xi内.

根据注 2 中提到的Moreau-Yosida 近似函数和性质可知,对于优化问题 (1) 的任意初始解(x(0),时,有等式关系τ(0),µ(0),s(0)).当函数f,g是凸函数,在局部可行集上是连续可微的并且有下界[28],那么分布式投影算法 (15)～(18) 的解一定存在.

当t →∞时,各状态为PX=x,x=1M ⊗x′,µ=1M ⊗µ′,可得,即优化问题的所有可行解渐近收敛到平衡解,式 (39) 成立.结合定理1 证明的算法的平衡解为优化问题 (1)的充分必要条件可知,分布式投影算法 (15)～(18)中的决策变量x满足耦合不等式约束和局部可行集约束的条件下最终会收敛到问题 (1) 的最优解.

3 仿真研究

本节通过数值实验来验证强连通有向通信拓扑图下的分布式连续时间投影算法的有效性.

考虑由4 个智能体组成的强连通有向通信拓扑图,如图1 所示.局部代价函数为f i(x)=‖x-ωi‖,其中,ωi是各智能体对应的目标点,即

图1 加权平衡有向交互图Fig.1 Weight-balanced directed interaction graph

局部耦合不等式约束为gi(x)=‖x-ω0‖/4-i/4≤0,i∈{1,2,3,4},其全局耦合不等式约束为g(x)=‖x-ω0‖-5/2≤0,其中,ω0=col(4,4) 是耦合不等式约束的中心点[28].定义各智能体的状态初始值为x1=col(2,6),x2=col(3,3),x3=col(5,2),x4=col(1,2),令k=4,c1=1.3,c2=1.2.每个智能体的局部可行集Xi为

由此可以看出,针对本文所提的分布式优化问题 (1),4 个智能体在局部可行集约束和耦合不等式约束范围内共同协作找到距离4 个目标点ωi最近的点.如图2 所示,其中三角形表示各智能体xi局部可行集的交集,圆形表示耦合不等式约束的范围.从仿真图中可以看出,对于满足局部可行集约束和耦合不等式约束情况下的任意初始值,各智能体最终收敛到分布式优化问题的最优解.

图2 状态 xi 的轨迹图Fig.2 Trajectories graph of state xi

图3～5 分别表示变量τ,µ,s的运动轨迹,从图中我们可知所有变量是一致收敛的,并且µi总是非负的,仿真算例验证了理论结果.本文中的算法是利用各智能体在其局部可行集上进行投影,不同于文献[24]中在切锥上的投影,节约了智能体间的交互、计算和时间成本,使算法更快地达到收敛.其次,连续时间系统更具灵活性和实时性,可满足对实时优化精度高的实际应用.

图3 状态 τi 的轨迹图Fig.3 Trajectories graph of state τi

图4 状态 µi 的轨迹图Fig.4 Trajectories graph of state µi

图5 状态 si 的轨迹图Fig.5 Trajectories graph of state si

4 结束语

本文研究了在强连通加权平衡的有向通信拓扑网络中,目标函数和约束为凸函数,满足耦合不等式路径约束和局部可行集约束的情况下,找到了证明算法的平衡解为分布式优化问题最优解的充分必要条件,并且所提分布式连续时间投影算法渐近收敛到全局最小值点.结合文献[28]中的分布式连续时间投影算法设计,基于在智能体局部可行集上的投影,通过近似函数将非光滑的目标函数和约束近似为连续可微的凸函数,构造李雅普诺夫函数并证明算法收敛到分布式优化问题的最优解.与加权平衡有向图相比,分布式算法在加权不平衡有向图的设计对系统性能、资源分配等具有更普遍的意义,其收敛性分析也具有更大的挑战.未来的研究方向集中在将分布式投影算法拓展到加权不平衡有向图网络下,并考虑放缩强连通的假设条件至一致联合连通时算法收敛的问题.