一类分布最优问题的指数时间收敛算法

刘书新,韩佳敏,杜海霞,曹若薇

(新疆农业大学数理学院,新疆乌鲁木齐,830052)

摘要:具有全局等式约束分布优化问题在资源分配、投资组合、智能电网等领域有广泛应用。针对这类协作式的分布优化问题,设计了一个指数时间收敛的分布式算法,利用凸分析、代数图论和Lyapunov 稳定性理论,证明了该算法的指数时间收敛性。最后,通过一个电力调度问题,验证了提出的算法在求解具有全局等式约束分布优化问题时的有效性。

关键词:分布式算法;凸优化;多智能体系统

多智能体系统[1]作为分布式人工智能的一个重要分支,主要研究多个智能体在复杂环境下如何处理协同合作等问题。多智能体系统的一致性问题主要是基于多智能体系统中的智能体相互之间的信息交换,通过设计一致性协议[2]使得智能体的状态趋于一致。近年来,多智能体系统的一致性问题得到了广泛的应用,例如分布式传感器网络、机器人系统的协作等[3]。另一方面,随着人工智能和大数据等新兴领域的发展,基于多智能体一致性的分布式优化理论[4]得到了越来越多的关注,并逐渐在协同控制、工程计算等各个领域得到广泛应用。多智能体系统分布式优化是通过多智能体之间的有效合作完成优化任务,在多智能体系统一致性的框架下求解分布式最优问题,其中有代表性的算法有基于迭代框架下的离散时间算法[5]、基于协调控制的连续时间算法[6]、基于有限时间收敛的不连续算法[7]和基于固定时间收敛的连续算法[8]。基于以上讨论,提出了一个求解多智能体优化问题的分布式指数时间收敛的算法。

1 预备知识和问题表述

1.1 代数图论

多智能体系统各智能体之间的通讯拓扑可以用图进行描述。令G={V,E,B} 表示一个拓扑图,其中V={v1,v2,…,vn} 表示其节点的集合,n 为图中节点个数,节点的下标集合为InEV ×V 表示边的集合,eij=(vi,vj)表示图的边;邻接矩阵B=[bij],其中bij为非负实数,表示节点vi到节点vj的连接权重。如果节点vi可以接收到节点vj的信息,则bij >0;否则,bij=0,假设相连节点之间连接权重均为1,拓扑图中每个节点没有自连,即对于所有iInbij=0。如果一个拓扑图的邻接矩阵B是对称矩阵,则称该拓扑图是无向的。一个图的Laplacian 矩阵定义为L=[lij]∈Rn×n。当i=jij时,lij=-bij。对于任意节点vi,定义其邻域节点集为Ni={vjV ∶(vi,vjE)}。如果对于两个节点vi,vj,存在下标集合{k1,k2,…,ki} 满足,则称节点vi到节点vj 之间存在一条有向信息传输路径。对于一个无向图,如果图中任意两个节点都存在至少一条有向连接路径,则称该图G 是连通的。矩阵L 所有特征根都是非负实数。矩阵L 第二最小特征根λ2(L)>0,其又被称作该扑图的代数连通度,且因此,如果1Tε=0,则有εTλ2(L )εTε

引理对于一个无向连通图的Laplacian 矩阵L 具有如下的性质:

(1)0 是矩阵L 的一个特征值,1 是其相应的特征向量;

(2)对任意向量ε=[ε1,ε2,…,εn]T,有下式成立

1.2 指数收敛

考虑方程

其中,fRnRn为一个连续函数。

定义1 方程(1)的解为有界的。如果对于任意的(t0,x0)∈R × Rn,都存在M= M(t0,x0),使得对于一切tt0,有‖x(t0,x0)‖≤M[10]

定义2 方程(1)的解为全局指数收敛的。若存在正常数k,δ,使得任意解x(t)对唯一平衡解x0,当tt0时,有

1.3 问题表述

考虑由n个智能体组成的多智能体系统,其中每个智能体具有局部目标函数hi(xi)。要讨论的问题是在保持全局等式约束的同时,最小化所有局部目标函数的和,即

x=[x1,x2,…,xn]T是一个决策向量,h(x)是全局目标函数,hi(xi)是局部目标函数,Ci0 表示变量,xi 是一个常量。

注1 问题(2)的等式约束来自一些物理约束,如资源配置、供需平衡、借贷平衡等。

假设1 智能体之间的通信拓扑是无向连通图。

假设2 目标函数hi(xi)是强凸的,存在正常数σ使得∇2hi(xi)≥σ >0。

由假设2可知问题(2)具有唯一的最优解。

2 指数时间收敛的算法设计

为求解优化问题(2),提出下面的分布式算法:

其中,r 是常数,yiθi 是辅助变量。事实上,根据假设1和bij= bji,则有

表示算法(3)始终满足问题(2)的等式约束,同时,将问题(2)转化为下面的无约束优化问题:

其中,y=[y1,y2,…,yn]T是辅助决策向量。

根据(3)式中的第二个式子,把xi(i=1,2,…,n)对yj(j=1,2,…,n)求导得

进一步,有

注意到h(x)的梯度为∇h(x)=(θ1,…,θn)T

由(4)式,得到

其中,L代表通信图对应的拉普拉斯矩阵。显然,h(y)的Hessian矩阵满足

证明算法(3)的收敛性。

定理 在假设1 和2 的条件下,分布式算法(3)可以在指数时间内求解问题(2)。

证明 假设凸优化问题(2)的唯一最优解用z=[z1,z2,…,zn]T表示。a 是任意常数,如果z= a1,则z是平凡解。探讨非平凡解的情况。对于任意的凸紧集QRn/a1,和任意的y,wQ,由h(y)的强凸性可得

因为通信图是无向连通的,所以通信图拉普拉斯矩阵L特征向量1,ξ2,…,ξn的特征值相应的表示为0= λ1 < λ2 ≤…≤λn,其 中‖ ξi ‖=1,i=2,…,n。向量y - z可以表示如下

其中,τi(i=1,2,…,n)是常数,ξ= τ2 ξ2+…+ τn ξn,则

注意到

根据假设2,得

由(8)式,进一步得到

将(5)式代入上式的右边

由于0 是拉普拉斯矩阵L 特征向量1 的单特征值,则L1=0。因此

对于(7)式,设w= z。当∇h(z)=0,有

将(6)式代入(10)式得

根据假设2得

结合(9)和(11)有

注意,‖ ξ ‖≠0对非平凡解成立。因此

选取Lyapunov函数

对(14)式求导得

再由(10)式可得y 指数收敛到z。即算法(3)在指数时间内能求解问题(2)。

3 数值模拟

用电力调度问题来测试算法(3)的性能。考虑一个由3 台发电机和3 个负载组成的电力系统,其中节点1、2、3 表示发电机,节点4、5、6 表示对应的负载,如图1所示。

图1 电力系统

xi(i=1,2,3)和C 分别表示由第i 台发电机产生的有效功功率和总负载需求。在电力工程中,发电机的成本函数hi(xi)一般由二次函数近似:hi(xi)=其中τiβiηi 代表成本系数。考虑的电力系统经济调度问题可以表达为

显然,算法(3)可以直接用于解决经济调度问题(16)。假设总负荷需求C 为420 MW,成本系数τiβiηi如表1所示。将初始状态设为

表1 发电机成本参数

利用算法(3)得到的经济调度问题(16)解的动态轨迹,模拟结果显示最优解为

4 结语

对一类等式约束的分布凸优化问题,基于多智能体系统设计了一个指数时间收敛的算法,利用Lyapunov 函数理论,证明了算法的指数收敛性。最后通过实例模拟验证了理论分析的有效性。

参考文献

[1]邵中华,崔艳.参数自适应的有限时间多智能体一致性算法[J].山西师范大学学报(自然科学版),2018,32(1):37-42.

[2]王晓波,邢建春,李决龙,等.多智能体系统快速有限时间平均一致性协议研究[J].微电子学与计算机,2018,35(5):11-14.

[3]毛志勇,何小燕.多智能体系统的分布式有限时间跟踪控制[J].内蒙古大学学报(自然科学版),2016,47(6):658-663.

[4]洪奕光,张艳琼.分布式优化:算法设计和收敛性分析[J].控制理论与应用,2014,31(7):850-857.

[5]LU J.TANG Y.REGIER R.etal.Gossip algorithms for convex consensus optimization over networks[J].IEEE Transactions on Automatic Control,2011,56(12):2917-2923.

[6]CHEN W.REN W.Event-triggered zero-gradient-sum distributed consensus optimiza-tionover directed networks[J].Automatica,2016,65(15):90-97.

[7]LIN P.REN W.Distributed multi-agent optimization subject to nonidentical constraints and communication delays[J].Automatica,2016,65(16):120-131.

[8]CHEN G.A fixed-time convergent algorithm for distributed convex optimization in multi-agent systems[J].Automatica,2018,95(60):539-543.

[9]CHRIS G.Algebraic graph theory[M].Beijing:World book publishing company,2004.

[10]迪申加卜.泛函微分方程解的指数收敛性及其有界性[J].锦州师范学院学报(自然科学版),1997(3):51-53.

Exponential Time Convergence Algorithm for a Class of Distributed Optimal Problems

LIU Shu-xin,HAN Jia-min,DU Hai-xia,CAO Ruo-wei
(School of Mathematics and Physics,Xinjiang Agricultural University,Urumqi Xinjiang,830052)

Abstract:The global equal-constrained distribution optimization problem is widely used in resource allocation,investment portfolio,smart power grid and other fields.For this kind of cooperative distribution optimization problem,a distributed algorithm with exponential time convergence is designed in this paper,and its exponential time convergence is proved by convex analysis,al‐gebraic graph theory and Lyapunov stability theory.Finally,a power scheduling problem is presented to demonstrate the effective‐ness of the proposed algorithm in solving distributed optimization problems with global equality constraints.

Key words:distributed algorithm;convex optimization;multiagent system

中图分类号:TP13

文献标识码:A

doi:10.3969/j.issn.1674-0874.2021.04.009

文章编号:1674-0874(2021)04-0025-04

收稿日期:2021-01-14

基金项目:新疆农业大学校前期项目资助[XJAU201705]

作者简介:刘书新(1974-),山东东营人,博士,讲师,研究方向:最优化理论与算法。

〔责任编辑 高海〕