最小事件间隔时间可设计的分布式事件触发优化算法

杨志强，贾红云，韦梦立，季秋桐，赵中原; YANG Zhiqiang; JIA Hongyun; WEI Mengli; JI Qiutong; ZHAO Zhongyuan

引 en

最小事件间隔时间可设计的分布式事件触发优化算法

杨志强¹
机构：
1. 南京信息工程大学自动化学院,南京, 210044
×
，贾红云¹
机构：
1. 南京信息工程大学自动化学院,南京, 210044
×
，韦梦立²
机构：
2. 东南大学网络空间安全学院,南京, 211189
×
，季秋桐²
机构：
2. 东南大学网络空间安全学院,南京, 211189
×
，赵中原¹
机构：
1. 南京信息工程大学自动化学院,南京, 210044
×

1. 南京信息工程大学自动化学院,南京, 210044；
2. 东南大学网络空间安全学院,南京, 211189；

Distributed event-triggered optimization algorithm with designable minimum inter-event time

YANG Zhiqiang¹
Affiliation：
1. School of Automation,Nanjing University of Information Science & Technology,Nanjing 210044 ,China
×
，JIA Hongyun¹
Affiliation：
1. School of Automation,Nanjing University of Information Science & Technology,Nanjing 210044 ,China
×
，WEI Mengli²
Affiliation：
2. School of Cyber Science and Engineering,Southeast University,Nanjing 211189 ,China
×
，JI Qiutong²
Affiliation：
2. School of Cyber Science and Engineering,Southeast University,Nanjing 211189 ,China
×
，ZHAO Zhongyuan¹
Affiliation：
1. School of Automation,Nanjing University of Information Science & Technology,Nanjing 210044 ,China
×

1. School of Automation,Nanjing University of Information Science & Technology,Nanjing 210044 ,China；
2. School of Cyber Science and Engineering,Southeast University,Nanjing 211189 ,China；

作者简介:

杨志强,男,硕士生,研究方向为多智能体的分布式优化．318419931@qq.com

通讯作者:

赵中原,男,博士,讲师,主要研究方向为多智能体系统分布式协调与控制．zhaozhongyuan@nuist.edu.cn

中图分类号:TP273

文献标识码:A

DOI:10.13878/j.cnki.jnuist.20221119001

全文
评论
参考文献
出版信息

参考文献 1

郑伟,胡长斌,丁丽,等.基于多智能体系统微电网分布式控制研究[J].高压电器,2019,55(3):177-184.ZHENG Wei,HU Changbin,DING Li,et al.Research on distributed control of microgrid based on multi-agent system[J].High Voltage Apparatus,2019,55(3):177-184

查找原文

参考文献 2

Han D,Wu J F,Zhang H S,et al.Optimal sensor scheduling for multiple linear dynamical systems[J].Automatica,2017,75:260-270

查找原文

参考文献 3

Pantelimon G,Tepe K,Carriveau R,et al.Survey of multi-agent communication strategies for information exchange and mission control of drone deployments[J].Journal of Intelligent and Robotic Systems,2019,95(3/4):779-788

查找原文

参考文献 4

胡金波,刘智伟,葛明峰.基于采样分布式估计器的多无人艇轨迹跟踪控制[J].南京信息工程大学学报(自然科学版),2018,10(4):443-449.HU Jinbo,LIU Zhiwei,GE Mingfeng.Consensus tracking control of multi-USV system based on distributed estimator under sampled interactions[J].Journal of Nanjing University of Information Science & Technology(Natural Science Edition),2018,10(4):443-449

查找原文

参考文献 5

Basir Khan M R,Jidin R,Pasupuleti J.Multi-agent based distributed control architecture for microgrid energy management and optimization[J].Energy Conversion and Management,2016,112:288-307

查找原文

参考文献 6

朱亚楠,温广辉.权重平衡有向网络下分布式约束优化的连续时间算法设计[J].南京信息工程大学学报(自然科学版),2020,12(5):549-555.ZHU Yanan,WEN Guanghui.Continuous-time algorithm design for distributed constrained optimization over weight-balanced directed networks[J].Journal of Nanjing University of Information Science & Technology(Natural Science Edition),2020,12(5):549-555

查找原文

参考文献 7

Nedic A,Ozdaglar A.Distributed subgradient methods for multi-agent optimization[J].IEEE Transactions on Automatic Control,2009,54(1):48-61

查找原文

参考文献 8

Pang Y P,Hu G Q.Randomized gradient-free distributed optimization methods for a multiagent system with unknown cost function[J].IEEE Transactions on Automatic Control,2020,65(1):333-340

查找原文

参考文献 9

Liu H Z,Yu W W.Discrete-time algorithm for distributed unconstrained optimization problem with finite-time computations[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2021,68(1):351-355

查找原文

参考文献 10

Lin P,Ren W,Farrell J A.Distributed continuous-time optimization:nonuniform gradient gains,finite-time convergence,and convex constraint set[J].IEEE Transactions on Automatic Control,2017,62(5):2239-2253

查找原文

参考文献 11

Lu J,Tang C Y.Zero-gradient-sum algorithms for distributed convex optimization:the continuous-time case[J].IEEE Transactions on Automatic Control,2012,57(9):2348-2354

查找原文

参考文献 12

Song Y F,Chen W S.Finite-time convergent distributed consensus optimisation over networks[J].IET Control Theory & Applications,2016,10(11):1314-1318

查找原文

参考文献 13

Zhu W,Pu H Z,Wang D D,et al.Event-based consensus of second-order multi-agent systems with discrete time[J].Automatica,2017,79:78-83

查找原文

参考文献 14

Dimarogonas D V,Frazzoli E,Johansson K H.Distributed event-triggered control for multi-agent systems[J].IEEE Transactions on Automatic Control,2012,57(5):1291-1297

查找原文

参考文献 15

Seyboth G S,Dimarogonas D V,Johansson K H.Event-based broadcasting for multi-agent average consensus[J].Automatica,2013,49(1):245-252

查找原文

参考文献 16

Berneburg J,Nowzari C.Robust dynamic event-triggered coordination with a designable minimum inter-event time[C]//IEEE Transactions on Automatic Control.September 1,2020,IEEE,2020:3417-3428

查找原文

参考文献 17

Qian Y Y,Wan Y.Design of distributed adaptive event-triggered consensus control strategies with positive minimum inter-event times[J].Automatica,2021,133:109837

查找原文

参考文献 18

王誉达,查利娟,刘金良,等.基于事件触发和欺骗攻击的多智能体一致性控制[J].南京信息工程大学学报(自然科学版),2019,11(4):380-389.WANG Yuda,ZHA Lijuan,LIU Jinliang,et al.Event-based consensus of multi-agent systems with deception attacks[J].Journal of Nanjing University of Information Science & Technology(Natural Science Edition),2019,11(4):380-389

查找原文

参考文献 19

杨涛,徐磊,易新蕾,等.基于事件触发的分布式优化算法[J].自动化学报,2022,48(1):133-143.YANG Tao,XU Lei,YI Xinlei,et al.Event-triggered distributed optimization algorithms[J].Acta Automatica Sinica,2022,48(1):133-143

查找原文

参考文献 20

Kia S S,Cortés J,Martínez S.Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication[J].Automatica,2015,55:254-264

查找原文

参考文献 21

赵中原,陈刚.基于事件驱动的二次凸优化问题分布式优化算法[J].控制与决策,2019,34(8):1635-1644.ZHAO Zhongyuan,CHEN Gang.Distributed event-triggered algorithm for quadratic convex optimization problem[J].Control and Decision,2019,34(8):1635-1644

查找原文

参考文献 22

Liu J Y,Chen W S.Distributed convex optimisation with event-triggered communication in networked systems[J].International Journal of Systems Science,2016,47(16):3876-3887

查找原文

参考文献 23

Zhao Z Y,Chen G.Event-triggered scheme for zero-gradient-sum optimisation under directed networks with time delay[J].International Journal of Systems Science,2021,52(1):47-56

查找原文

参考文献 24

Du W,Yi X L,George J,et al.Distributed optimization with dynamic event-triggered mechanisms[C]//2018 IEEE Conference on Decision and Control(CDC).December 17-19,2018,Miami,FL,USA.IEEE,2019:969-974

查找原文

目录contents

摘要 Abstract
关键词 Keywords
0 引言
1 预备知识及问题描述
1.1 图论
1.2 凸函数
1.3 问题描述
2 算法设计及主要结果
2.1 分布式优化算法
2.2 事件触发条件
3 仿真结果
4 结论
参考文献

摘要

针对多智能体系统中的分布式凸优化问题,本文提出一种基于自适应事件触发机制的零梯度和优化算法．基于虚拟时钟设计了一种自适应事件触发条件,当每个智能体的虚拟时钟满足该条件时才触发条件,有效地降低了控制器的更新次数和系统的通信负担．通过构造李雅普诺夫函数,证明了在该算法下所有智能体的状态能渐近收敛到全局最优解．此外,所设计的事件触发条件使得最小事件触发间隔时间可设计,有效地排除Zeno行为．最后,通过仿真验证了该算法的有效性．

Abstract

Aiming at the distributed convex optimization problem in multi-agent systems,a zero-gradient-sum optimization algorithm based on adaptive event-triggered mechanism is proposed in this paper.The adaptive event-triggered condition is designed based on virtual clock,and the condition will not be triggered until the virtual clock of each agent meets the condition,which effectively reduces the update times of the controller as well as the communication burden of the system.Through constructing the Lyapunov function,it is proved that the states of all agents can converge asymptotically to the global optimal solution under the algorithm.In addition,the designed event-triggered condition makes the minimum inter-event time designable,which effectively excludes the Zeno behavior.Finally,simulation results verify the effectiveness of the algorithm.

关键词

分布式优化；多智能体系统；凸优化；事件触发控制

Keywords

distributed optimization ； multi-agent system ； convex optimization ； event-triggered control

0 引言
近年来，多智能体系统因其在微电网控制与运行^[1]、传感器调度^[2]、无人机协调^[3]、轨迹跟踪控制^[4]等多个领域的应用而受到了广泛关注．分布式优化问题作为多智能体系统基本问题成为当前的一个研究热点^[5-6]，其目标是通过智能体之间的分布式协作以实现全局目标函数最小化．
在分布式优化问题的求解方面，学者们提出了一系列的分布式优化算法．早期的算法研究成果主要是基于离散时间模型^[7-9]，例如:文献^[7]基于离散时间一致性和分布式梯度下降法来解决分布式优化问题; 文献^[8]针对成本函数未知的分布式优化问题，利用两点梯度估计器设计了一种随机无梯度算法．连续时间分布式优化算法同样得到了广泛研究:文献^[10]研究了固定无向网络上的连续时间优化算法; 文献^[11]给出了一种基于零梯度和原理的连续时间算法，使得智能体的状态指数收敛到全局最优值; 文献^[12]进一步提出有限时间零梯度和优化算法，实现了最优解的有限时间收敛性．上述文献中的算法需要智能体之间进行连续通信，但智能体的通信资源通常是有限的，连续通信对实际的多智能体系统通信带宽依然是一种挑战．
事件触发机制作为一种事先给定触发条件的控制方式能够有效减低智能体之间的通信频率．近年来，事件触发机制已经被广泛应用于一致性问题中^[13-18]．文献^[13]针对离散系统上的一致性问题，提出一种基于事件触发机制的一致性算法; 文献^[14]进一步给出连续时间上的分布式动态事件触发一致性算法，有效地降低了智能体之间的通信负担．然而，上述文献无法有效处理Zeno行为．文献^[15]基于周期采样控制提出一种分布式事件触发算法，事件仅在周期采样时刻检测，有效地避免了Zeno行为; 文献^[16-17]采用自适应事件触发控制策略来解决无向网络上的一致性问题，使得每个智能体事件触发间隔时间可设计．目前，事件触发机制已经被扩展到分布式优化问题中^[19-24]．文献^[19]提出一种分布式事件触发优化算法有效地解决了智能体之间的连续通信问题，文献^[22]将事件触发机制和零梯度和原理应用于分布式优化问题，它们尽管在理论上避免了Zeno行为，然而无法提供明确的最小事件间隔时间．文献^[23]进一步提出一种基于采样数据的分布式事件触发零梯度和优化算法，保证事件触发间隔时间是采样周期，Zeno行为很容易被排除在外．为了进一步扩大事件触发间隔时间，文献^[24]提出一种基于动态事件触发的分布式优化算法，有效地降低了系统的通信负担．然而，文献^[23-24]需要进行严格的时钟同步．
受文献^[16-17，24]的启发，本文针对无向图下的多智能体分布式优化问题，提出一种分布式自适应事件触发零梯度和优化算法，在所设计事件触发条件下，每个智能体事件触发间隔时间可设计．本文的主要贡献如下:
1）设计了一种具有新型事件触发条件的零梯度和优化算法来解决无向图上的分布式优化问题，所有智能体的状态都可在不使用任何全局信息的情况下收敛到全局最优值，并可有效地降低系统的通信负担;
2）智能体采用分布式异步事件触发机制，不需要时钟同步;
3）所提出的事件触发机制可有效排除Zeno现象，且每个智能体最小事件触发间隔时间可设计．
1 预备知识及问题描述
1.1 图论
多智能体系统可以用无向图G=（V，E）来建模，其中V={v₁，···，v_n}表示智能体的集合，E∈{V×V}为边的集合．定义A=[a_ij]∈Rⁿ^×ⁿ为图G的加权邻接矩阵，如果（v_i，v_j）∈E，则权重a_ij=1，否则a_ij=0，不考虑自环的情况，所以a_ii=0．令D=diag{d₁，d₂，···，d_n}表示入度矩阵，其中 $d_{i} = \sum_{j = 1}^{n} a_{i j}$ ．定义L=[l_ij]ⁿ^×ⁿ为图G的拉普拉斯矩阵，它满足L=D-A．
1.2 凸函数
如果一个二次连续可微函数g_i:Rⁿ→R是局部强凸的，则对于凸紧集 $Ω \subset R^{n}$ 中任意值都有:

\begin{matrix} g_{i} (x^{'}) - g_{i} (x) - \nabla g_{i} (x)^{T} (x^{'} - x) ⩾ \\ \frac{φ_{i}}{2} {∥x^{'} - x∥}^{2}, \forall x, x^{'} \in Ω; \end{matrix}

(1)

\begin{matrix} {(\nabla g_{i} (x^{'}) - \nabla g_{i} (x))}^{T} (x^{'} - x) ⩾ \\ \frac{φ_{i}}{2} {∥x^{'} - x∥}^{2}, \forall x, x^{'} \in Ω; \end{matrix}

(2)

\nabla^{2} g_{i} (x) ⩾ φ_{i} I_{n} .

(3)

其中，φ_i是一个正常数， $\nabla g_{i} （ x ） : R^{n} ⟶ R^{n}$ 是g_i的梯度， $\nabla^{2} g_{i} （ x ） : R^{n} ⟶ R^{n \times n}$ 是黑森矩阵．
1.3 问题描述
本文所研究的优化问题如下:

x^{*} = a r g \underset{x \in R}{m i n} F (x) .

(4)

其中，x^*为全局最优值． $F （ x ） = \sum_{i = 1}^{n} f_{i} （ x ）$ ，局部代价函数f_i（x），i=1，···，n，是二次连续可微且强凸的．
本文的目的是设计一种分布式事件触发优化算法来解决上述优化问题，同时减少控制器的更新次数，降低多智能体之间的通信频率．因此，基于事件触发机制设计了一种新型零梯度和优化算法解决优化问题（4）．
2 算法设计及主要结果
本节详细介绍所提出的分布式优化算法，并给出该算法的主要结果．
2.1 分布式优化算法
定义 $\{t_{k}^{i} : k \in N\}$ 为智能体i的第k次事件触发时刻．为了方便起见，对于 $t \in [t_{k}^{i} ， t_{k + 1}^{i})$ ，定义 ${\hat{x}}_{i} （ t ） = x_{i} (t_{k}^{i})$ ．
本文设计的分布式优化算法如下:

\dot{x_{i}} (t) = {(\nabla^{2} f_{i} (x_{i} (t)))}^{- 1} u_{i} (t) .

(5)

其中: $x_{i} （ 0 ） = x_{i}^{*}$ ， $x_{i}^{*}$ 为智能体i成本函数优化值; u_i（t）为控制输入，u_i（t）表示为

u_{i} (t) = \sum_{j \in N_{i}} a_{i j} ({\hat{x}}_{j} (t) - {\hat{x}}_{i} (t)) .

(6)

2.2 事件触发条件
对于 $t \in [t_{k}^{i} ， t_{k + 1}^{i})$ ，设计偏差变量为

e_{i} (t) = x_{i} (t) - {\hat{x}}_{i} (t) .

(7)

进一步，定义一个受限制的虚拟变量0≤β_i（t）＜1，

{\dot{β}}_{i} (t) = γ_{i} = \{\begin{matrix} m i n \{{\bar{γ}}_{i}, 0\} - σ_{i}, ∥e_{i} (t)∥ \neq 0 \\ - σ_{i}, ∥e_{i} (t)∥ = 0 . \end{matrix}

(8)

其中，σ_i＞0为正常数， ${\bar{γ}}_{i}$ 为待设计的参数．虚拟变量β_i（t）本质上是一个计时器，当β_i（t）≤0时，智能体i将它的状态信息传递给它的邻居，更新 ${\hat{x}}_{i} （ t ）$ =x_i（t），并且重置β_i（t）为它的最大值．
因此，事件触发条件被设计为

t_{k + 1}^{i} = m i n \{t^{'} ⩾ t_{k}^{i} ∣ β_{i} (t^{'}) ⩽ 0\} .

(9)

定理1 假设图G是无向连通图，分布式优化算法（5）在事件触发条件（9）下可以解决优化问题（4），即 $\underset{t \to 0}{l i m} x_{1} （ t ） = \dots = \underset{t \to 0}{l i m} x_{n} （ t ） = x^{*}$ ，其中x^*为系统全局优化值．
证明定义Lyapunov函数

V (t) = \sum_{i = 1}^{n} (f_{i} (x^{*}) - f_{i} (x_{i} (t)) - f_{i}^{'} (x_{i} (t)) (x^{*} - x_{i} (t))) + \frac{1}{2} e (t)^{T} β (t) e (t) .

(10)

其中， $e （ t ） = {[e_{1} （ t ）， e_{2} （ t ）， \dots ， e_{n} （ t ）]}^{T} ， β （ t ） = d i a g \{β_{1} （ t ）， β_{2} （ t ）， \dots ， β_{n} （ t ）\}$ ．
令 $V_{1} = \sum_{i = 1}^{n} (f_{i} (x^{*}) - f_{i} (x_{i} （ t ）) - f^{'}_{i} (x_{i} （ t ）) (x^{*} - x_{i} （ t ）)) ， V_{2} （ t ） = \frac{1}{2} e （ t ）^{T} β （ t ） e （ t ）$ ，式（10）可以被写为

V (t) = V_{1} (t) + V_{2} (t) .

(11)

由式（1）可得:

V_{1} (t) ⩾ \sum_{i = 1}^{n} \frac{φ_{i}}{2} {(x^{*} - x_{i} (t))}^{2} ⩾ 0 .

(12)

由于β_i（t）≥0，可以得到:

V_{2} (t) ⩾ 0 .

(13)

由式（12）和（13）可得:

V (t) = V_{1} (t) + V_{2} (t) ⩾ 0 .

(14)

因此，李雅普诺夫函数是正定的．
对V₁（t）求导，结合式（5）可得:

\begin{matrix} {\dot{V}}_{1} (t) = \sum_{i = 1}^{n} (- f_{i}^{'} (x_{i} (t)) {\dot{x}}_{i} (t) - \\ f_{i}^{''} (x_{i} (t)) {\dot{x}}_{i} (t) (x^{*} - x_{i} (t)) + f_{i}^{'} (x_{i} (t)) {\dot{x}}_{i} (t)) = \\ \sum_{i = 1}^{n} - f_{i}^{''} (x_{i} (t)) {\dot{x}}_{i} (t) (x^{*} - x_{i} (t)) . \end{matrix}

(15)

由式（5）可知，式（15）可表示为

\begin{matrix} {\dot{V}}_{1} (t) = \sum_{i = 1}^{n} - f_{i}^{''} (x_{i} (t)) (- f_{i}^{''} {(x_{i} (t))}^{- 1} \sum_{j \in N_{i}} a_{i j} ({\hat{x}}_{i} (t) - \\ {\hat{x}}_{j} (t))) (x^{*} - x_{i} (t)) = \sum_{i = 1}^{n} (\sum_{j \in N_{i}} a_{i j} ({\hat{x}}_{i} (t) - \\ {\hat{x}}_{j} (t))) (x^{*} - x_{i} (t)) . \end{matrix}

(16)

由于图G是强连通和平衡的，可以得到:

\sum_{i = 1}^{n} \sum_{j \in N_{i}} a_{i j} ({\hat{x}}_{i} (t) - {\hat{x}}_{j} (t)) x^{*} = 0 .

(17)

由式（16）和（17）可知:

\begin{matrix} {\dot{V}}_{1} (t) = - x^{T} (t) L \hat{x} (t) = \\ - (\hat{x} (t) + e (t))^{T} L \hat{x} (t) . \end{matrix}

(18)

其中 $x （ t ） = {[x_{1} （ t ）， x_{2} （ t ）， \dots ， x_{n} （ t ）]}^{T} ， \hat{x} （ t ） = {[{\hat{x}}_{1} （ t ）， {\hat{x}}_{2} （ t ）， \dots ， {\hat{x}}_{n} （ t ）]}^{T} .$
对V₂（t）求导可得:

{\dot{V}}_{2} (t) = - e^{T} (t) β L \hat{x} (t) + \frac{1}{2} e^{T} (t) Γ e (t) .

(19)

其中，Γ=diag{γ₁，γ₂，···，γ_n}．
由式（18）和（19）可得:

\begin{matrix} \dot{V} (t) = - \hat{x} (t)^{T} L \hat{x} (t) - e (t)^{T} L \hat{x} (t) - \\ e^{T} (t) β L \hat{x} (t) + \frac{1}{2} e^{T} (t) Γ e (t) = \\ - \frac{1}{2} \sum_{i = 1}^{n} y_{i} (t) - e (t)^{T} L \hat{x} (t) - \\ e^{T} (t) β L \hat{x} (t) + \frac{1}{2} e^{T} (t) Γ e (t) . \end{matrix}

(20)

其中， $y_{i} （ t ） = \sum_{j = 1}^{n} a_{i j} {({\hat{x}}_{i} （ t ） - {\hat{x}}_{j} （ t ）)}^{2}$ ．当‖e_i（t）‖=0时， $\dot{V} （ t ） = - \frac{1}{2} \sum_{i = 1}^{n} y_{i} （ t ） ⩽ 0$ ．因此只考虑‖e_i（t）‖≠0的情况．由于

\begin{matrix} e^{T} (t) L \hat{x} (t) = \sum_{i = 1}^{n} e_{i} (t) \sum_{j = 1}^{n} L_{i j} {\hat{x}}_{j} (t) = \\ \sum_{i = 1}^{n} \sum_{j \in N_{i}} e_{i} (t) a_{i j} ({\hat{x}}_{i} (t) - {\hat{x}}_{j} (t)) . \end{matrix}

(21)

根据杨氏不等式可得:

\begin{matrix} e^{T} (t) L \hat{x} (t) ⩽ \\ \sum_{i = 1}^{n} \sum_{j \in N_{i}} a_{i j} e_{i}^{2} (t) + \frac{1}{4} a_{i j} {({\hat{x}}_{i} (t) - {\hat{x}}_{j} (t))}^{2} ⩽ \\ \sum_{i = 1}^{n} d_{i} e_{i}^{2} (t) + \frac{1}{4} \sum_{i = 1}^{n} \sum_{j \in N_{i}} a_{i j} {({\hat{x}}_{i} (t) - {\hat{x}}_{j} (t))}^{2} ⩽ \\ \sum_{i = 1}^{n} d_{i} e_{i} (t)^{2} + \frac{1}{4} \sum_{i = 1}^{n} y_{i} (t) . \end{matrix}

(22)

将式（22）代入（20）可得:

\begin{matrix} \dot{V} (t) ⩽ - \frac{1}{2} \sum_{i = 1}^{n} y_{i} (t) + \sum_{i = 1}^{n} d_{i} e_{i}^{2} (t) + \frac{1}{4} \sum_{i = 1}^{n} y_{i} (t) - \\ e^{T} (t) β L \hat{x} (t) + \frac{1}{2} e^{T} (t) Γ e (t) ⩽ \\ - \frac{1}{4} \sum_{i = 1}^{n} y_{i} (t) + \sum_{i = 1}^{n} d_{i} e_{i}^{2} (t) - \\ e^{T} (t) β L \hat{x} (t) + \frac{1}{2} e^{T} (t) Γ e (t) . \end{matrix}

(23)

由于

\begin{matrix} e^{T} (t) β L \hat{x} (t) = \sum_{i = 1}^{n} e_{i} (t) β_{i} (t) \sum_{j = 1}^{n} L_{i j} {\hat{x}}_{j} (t) ⩽ \\ \sum_{i = 1}^{n} β_{i} (\sum_{j \in N_{i}} a_{i j} e_{i}^{2} (t) + \frac{1}{4} \sum_{j = N_{i}} a_{i j} {({\hat{x}}_{i} (t) - {\hat{x}}_{j} (t))}^{2}) ⩽ \\ \sum_{i = 1}^{n} β_{i} (t) d_{i} e_{i}^{2} (t) + \sum_{i = 1}^{n} \frac{β_{i}}{4} y_{i} (t) . \end{matrix}

(24)

可以得到:
$\begin{matrix} \dot{V} ⩽ - \frac{1}{4} \sum_{i = 1}^{n} y_{i} (t) + \sum_{i = 1}^{n} d_{i} e_{i}^{2} (t) + \\ \sum_{i = 1}^{n} β_{i} (t) d_{i} e_{i}^{2} (t) + \sum_{i = 1}^{n} \frac{β_{i} (t)}{4} y_{i} (t) + \end{matrix}$

\begin{matrix} \frac{1}{2} e^{T} (t) Γ e (t) ⩽ \\ - \sum_{i = 1}^{n} (\frac{1 - β_{i} (t)}{4}) y_{i} (t) + \\ \sum_{i = 1}^{n} (1 + β_{i} (t)) d_{i} e_{i}^{2} (t) + \sum_{i = 1}^{n} \frac{γ_{i}}{2} e_{i}^{2} . \end{matrix}

(25)

当 $- \frac{1 - β_{i} （ t ）}{4} y_{i} （ t ） + (1 + β_{i} （ t ）) d_{i} e_{i}^{2} （ t ） + \frac{γ_{i} e_{i}^{2} （ t ）}{2} <$ 0 时，可得 $\dot{V} （ t ）$ ＜0．当y_i（t）≠0和e_i（t）≠0时，选择γ_i的最大值为

{\bar{γ}}_{i} = \frac{(1 - β_{i} (t))}{2} \frac{y_{i} (t)}{e_{i}^{2} (t)} - 2 (1 + β_{i} (t)) d_{i} .

(26)

由式（8）和（26）可知 $\dot{V} （ t ）$ ＜0．
因此可以得到 $\dot{V} （ t ）$ ≤0．根据拉塞尔不变集原理可知，当 $\dot{V} （ t ）$ =0时，有

\underset{t \to \infty}{l i m} {\hat{x}}_{1} (t) = \dots = \underset{t \to \infty}{l i m} {\hat{x}}_{n} (t) = c .

(27)

由于 $\dot{V} （ t ）$ =0，且有e_i（t）=0，然后可以得到:

\underset{t \to \infty}{l i m} x_{1} (t) = \dots = \underset{t \to \infty}{l i m} x_{n} (t) = c .

(28)

基于算法（5）可得:

\begin{matrix} \sum_{i = 1}^{n} \frac{d (f_{i}^{'} (x_{i} (t)))}{d t} = - \sum_{i = 1}^{n} \sum_{j \in N_{i}} a_{i j} ({\hat{x}}_{j} - {\hat{x}}_{i}) = \\ - 1^{T} L \hat{x} (t) = 0 . \end{matrix}

(29)

其中，1=[1，1，···，1]_n．
等式（29）意味着

\sum_{i = 1}^{n} f_{i} (x_{i} (t)) = \sum_{i = 1}^{n} f_{i} (x_{i} (0)) = \sum_{i = 1}^{n} f^{'}_{i} (x_{i}^{*}) = 0 .

(30)

由于 $F （ x ） = \sum_{i = 1}^{n} f_{i} （ x ）$ 是强凸函数，所以可以得到F（x）只有一个全局最优值x^*，使得 $\sum_{i = 1}^{n} f_{i}^{'} (x^{*}) = F^{'} (x^{*}) = 0$ ．因此，有

\underset{t \to \infty}{l i m} x_{1} (t) = \dots = \underset{t \to \infty}{l i m} x_{n} (t) = c = x^{*} .

(31)

定理1证明完毕．
定理2 假设图G是无向连通图，分布式优化算法（5）在事件触发条件（9）下可以避免Zeno现象，且每个智能体的最小事件触发间隔时间都是可设计的，即:

Δ t = \frac{1}{2 d_{i}} l n (1 + \frac{2 d_{i} β_{i}}{2 d_{i} + σ_{i}}) > 0 .

(32)

其中， $β$ 和σ_i是可设计的参数．
证明2 由式（8）和 $\underset{e_{i} \to 0}{l i m} m i n \{{\bar{γ}}_{i} ， 0\} = 0$ 可得:

- 2 (1 + β_{i} (t)) d_{i} - σ_{i} ⩽ γ ⩽ - σ_{i} .

(33)

因此，可以得到对于 $t \in [t_{k}^{i} ， t_{k + 1}^{i})$ ，有β_i（t）≥φ_i（t），其中φ_i（t）满足:

{\dot{ϕ}}_{i} (t) = - 2 (1 + ϕ_{i} (t)) d_{i} - σ_{i}

(34)

ϕ_{i} (t_{k}^{i +}) = β_{i} (t_{k}^{i +}) .

(35)

进一步可以得到:

\begin{matrix} ϕ_{i} (t) = e^{2 d_{i} t} ϕ_{i} (0) + e^{2 d_{i} t} \int_{0}^{t} e^{- 2 d_{i} τ} (- 2 d_{i} - σ_{i}) d τ = \\ e^{2 d_{i} t} ϕ_{i} (0) + \frac{2 d_{i} + σ_{i}}{2 d_{i}} - \frac{2 d_{i} + σ_{i}}{2 d_{i}} e^{2 d_{i} t} . \end{matrix}

(36)

其中，φ_i（0）=i．当事件触发条件满足时，有φ_i（t′）=0，即:

e^{2 d_{i} Δ t} β_{i} + \frac{2 d_{i} + σ_{i}}{2 d_{i}} - \frac{2 d_{i} + σ_{i}}{2 d_{i}} e^{2 d_{i} Δ t} = 0 .

(37)

进而推导出

\begin{matrix} Δ t = \frac{1}{2 d_{i}} l n \frac{2 d_{i} β_{i} + (2 d_{i} + σ_{i})}{2 d_{i} + σ_{i}} = \\ \frac{1}{2 d_{i}} l n (1 + \frac{2 d_{i} β_{i}}{2 d_{i} + σ_{i}}) > 0 . \end{matrix}

(38)

这意味着Zeno行为可以被有效避免，且每个智能体的相邻事件触发间隔的下界都是可设计的．
定理2证明完毕．
3 仿真结果
本文通过由4个智能体构成的多智能体系统验证所提出的算法的有效性，智能体之间的通信拓扑如图1所示．所采用的智能体的成本函数如下所示:
$f_{i} (x) = (x - i)^{4} + 8 i (x - i)^{2}, i = 1, 2, 3, 4 .$
参数设置如下:σ₁=σ₂=σ₃=σ₄=0.001; 虚拟变量β_i（t）的最大值被设置为 $β$ ₁=0.5， $β$ ₂=0.6， $β$ ₃=0.7和 $β$ ₄=0.5; 每个代理的初始状态值为x₁（0）=x^*₁=1，x₂（0）=x^*₂=2，x₃（0）=x^*₃=3，x₄（0）=x^*₄=4．
图1 通信拓扑
Fig.1 Communication topology
图2显示了x_i（t）的收敛过程，经过80次迭代收敛到全局最优值x^*=2.862 2．
图2 x_i的收敛过程，i=1，2，3，4
Fig.2 Convergence processes of x_i, i=1, 2, 3, 4
对于每个智能体，当满足其事件触发条件时，该事件将被触发．也就是说，当β_i=0时，事件触发条件成立，该事件就会触发，β_i被重置为i，每个智能体触发过程如图3—6所示．
图3 β₁的轨迹
Fig.3 Trajectory of β₁
图4 β₂的轨迹
Fig.4 Trajectory of β₂
${\hat{u}}_{i}$ 的演化过程如图7所示，它是一个分段常数函数，只在智能体i及其邻居的触发时刻进行更新．图8展示了每个智能体的事件触发时刻的分布情况．可以看出，每个智能体的事件触发时刻都非常稀疏，这有效地减少了代理之间的通信负担，Zeno现象被有效排除．
图5 β₃的轨迹
Fig.5 Trajectory of β₃
图6 β₄的轨迹
Fig.6 Trajectory of β₄
图7 u_i的轨迹
Fig.7 Trajectory of u_i
图8 每个智能体的事件触发时刻
Fig.8 Event-triggered instant for each agent
4 结论
本文针对多智能体系统分布式凸优化问题，设计了一种基于事件触发策略的零梯度和优化算法，在所提出的优化算法下，所有智能体的状态可以在不使用任何全局信息的情况下收敛全局最优值．此外，在所提出的事件触发条件下，每个智能体的相邻事件触发间隔时间的下界都是可设计的，Zeno现象被有效排除，每个智能体只需在其自身及其邻居事件触发时刻更新自身状态信息，大大减少了智能体之间的通信成本．在未来的研究中，尝试将该方法应用于有向图上的分布式优化问题．
参考文献
- [1] 郑伟,胡长斌,丁丽,等.基于多智能体系统微电网分布式控制研究[J].高压电器,2019,55(3):177-184.ZHENG Wei,HU Changbin,DING Li,et al.Research on distributed control of microgrid based on multi-agent system[J].High Voltage Apparatus,2019,55(3):177-184
- [2] Han D,Wu J F,Zhang H S,et al.Optimal sensor scheduling for multiple linear dynamical systems[J].Automatica,2017,75:260-270
- [3] Pantelimon G,Tepe K,Carriveau R,et al.Survey of multi-agent communication strategies for information exchange and mission control of drone deployments[J].Journal of Intelligent and Robotic Systems,2019,95(3/4):779-788
- [4] 胡金波,刘智伟,葛明峰.基于采样分布式估计器的多无人艇轨迹跟踪控制[J].南京信息工程大学学报(自然科学版),2018,10(4):443-449.HU Jinbo,LIU Zhiwei,GE Mingfeng.Consensus tracking control of multi-USV system based on distributed estimator under sampled interactions[J].Journal of Nanjing University of Information Science & Technology(Natural Science Edition),2018,10(4):443-449
- [5] Basir Khan M R,Jidin R,Pasupuleti J.Multi-agent based distributed control architecture for microgrid energy management and optimization[J].Energy Conversion and Management,2016,112:288-307
- [6] 朱亚楠,温广辉.权重平衡有向网络下分布式约束优化的连续时间算法设计[J].南京信息工程大学学报(自然科学版),2020,12(5):549-555.ZHU Yanan,WEN Guanghui.Continuous-time algorithm design for distributed constrained optimization over weight-balanced directed networks[J].Journal of Nanjing University of Information Science & Technology(Natural Science Edition),2020,12(5):549-555
- [7] Nedic A,Ozdaglar A.Distributed subgradient methods for multi-agent optimization[J].IEEE Transactions on Automatic Control,2009,54(1):48-61
- [8] Pang Y P,Hu G Q.Randomized gradient-free distributed optimization methods for a multiagent system with unknown cost function[J].IEEE Transactions on Automatic Control,2020,65(1):333-340
- [9] Liu H Z,Yu W W.Discrete-time algorithm for distributed unconstrained optimization problem with finite-time computations[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2021,68(1):351-355
- [10] Lin P,Ren W,Farrell J A.Distributed continuous-time optimization:nonuniform gradient gains,finite-time convergence,and convex constraint set[J].IEEE Transactions on Automatic Control,2017,62(5):2239-2253
- [11] Lu J,Tang C Y.Zero-gradient-sum algorithms for distributed convex optimization:the continuous-time case[J].IEEE Transactions on Automatic Control,2012,57(9):2348-2354
- [12] Song Y F,Chen W S.Finite-time convergent distributed consensus optimisation over networks[J].IET Control Theory & Applications,2016,10(11):1314-1318
- [13] Zhu W,Pu H Z,Wang D D,et al.Event-based consensus of second-order multi-agent systems with discrete time[J].Automatica,2017,79:78-83
- [14] Dimarogonas D V,Frazzoli E,Johansson K H.Distributed event-triggered control for multi-agent systems[J].IEEE Transactions on Automatic Control,2012,57(5):1291-1297
- [15] Seyboth G S,Dimarogonas D V,Johansson K H.Event-based broadcasting for multi-agent average consensus[J].Automatica,2013,49(1):245-252
- [16] Berneburg J,Nowzari C.Robust dynamic event-triggered coordination with a designable minimum inter-event time[C]//IEEE Transactions on Automatic Control.September 1,2020,IEEE,2020:3417-3428
- [17] Qian Y Y,Wan Y.Design of distributed adaptive event-triggered consensus control strategies with positive minimum inter-event times[J].Automatica,2021,133:109837
- [18] 王誉达,查利娟,刘金良,等.基于事件触发和欺骗攻击的多智能体一致性控制[J].南京信息工程大学学报(自然科学版),2019,11(4):380-389.WANG Yuda,ZHA Lijuan,LIU Jinliang,et al.Event-based consensus of multi-agent systems with deception attacks[J].Journal of Nanjing University of Information Science & Technology(Natural Science Edition),2019,11(4):380-389
- [19] 杨涛,徐磊,易新蕾,等.基于事件触发的分布式优化算法[J].自动化学报,2022,48(1):133-143.YANG Tao,XU Lei,YI Xinlei,et al.Event-triggered distributed optimization algorithms[J].Acta Automatica Sinica,2022,48(1):133-143
- [20] Kia S S,Cortés J,Martínez S.Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication[J].Automatica,2015,55:254-264
- [21] 赵中原,陈刚.基于事件驱动的二次凸优化问题分布式优化算法[J].控制与决策,2019,34(8):1635-1644.ZHAO Zhongyuan,CHEN Gang.Distributed event-triggered algorithm for quadratic convex optimization problem[J].Control and Decision,2019,34(8):1635-1644
- [22] Liu J Y,Chen W S.Distributed convex optimisation with event-triggered communication in networked systems[J].International Journal of Systems Science,2016,47(16):3876-3887
- [23] Zhao Z Y,Chen G.Event-triggered scheme for zero-gradient-sum optimisation under directed networks with time delay[J].International Journal of Systems Science,2021,52(1):47-56
- [24] Du W,Yi X L,George J,et al.Distributed optimization with dynamic event-triggered mechanisms[C]//2018 IEEE Conference on Decision and Control(CDC).December 17-19,2018,Miami,FL,USA.IEEE,2019:969-974

基本信息

中图分类号: TP273
文献标识码: A
DOI: 10.13878/j.cnki.jnuist.20221119001

基金信息

江苏省自然科学基金(BK20200824)；
南京信息工程大学人才启动经费(2019r082)；
国家自然科学基金（U23B2061）；
江苏省研究生科研与实践创新计划（SJCX23_0393）；

引用信息

稿件历史

收稿日期: 2022-11-19

参考文献

[1] 郑伟,胡长斌,丁丽,等.基于多智能体系统微电网分布式控制研究[J].高压电器,2019,55(3):177-184.ZHENG Wei,HU Changbin,DING Li,et al.Research on distributed control of microgrid based on multi-agent system[J].High Voltage Apparatus,2019,55(3):177-184
[2] Han D,Wu J F,Zhang H S,et al.Optimal sensor scheduling for multiple linear dynamical systems[J].Automatica,2017,75:260-270
[3] Pantelimon G,Tepe K,Carriveau R,et al.Survey of multi-agent communication strategies for information exchange and mission control of drone deployments[J].Journal of Intelligent and Robotic Systems,2019,95(3/4):779-788
[4] 胡金波,刘智伟,葛明峰.基于采样分布式估计器的多无人艇轨迹跟踪控制[J].南京信息工程大学学报(自然科学版),2018,10(4):443-449.HU Jinbo,LIU Zhiwei,GE Mingfeng.Consensus tracking control of multi-USV system based on distributed estimator under sampled interactions[J].Journal of Nanjing University of Information Science & Technology(Natural Science Edition),2018,10(4):443-449
[5] Basir Khan M R,Jidin R,Pasupuleti J.Multi-agent based distributed control architecture for microgrid energy management and optimization[J].Energy Conversion and Management,2016,112:288-307
[6] 朱亚楠,温广辉.权重平衡有向网络下分布式约束优化的连续时间算法设计[J].南京信息工程大学学报(自然科学版),2020,12(5):549-555.ZHU Yanan,WEN Guanghui.Continuous-time algorithm design for distributed constrained optimization over weight-balanced directed networks[J].Journal of Nanjing University of Information Science & Technology(Natural Science Edition),2020,12(5):549-555
[7] Nedic A,Ozdaglar A.Distributed subgradient methods for multi-agent optimization[J].IEEE Transactions on Automatic Control,2009,54(1):48-61
[8] Pang Y P,Hu G Q.Randomized gradient-free distributed optimization methods for a multiagent system with unknown cost function[J].IEEE Transactions on Automatic Control,2020,65(1):333-340
[9] Liu H Z,Yu W W.Discrete-time algorithm for distributed unconstrained optimization problem with finite-time computations[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2021,68(1):351-355
[10] Lin P,Ren W,Farrell J A.Distributed continuous-time optimization:nonuniform gradient gains,finite-time convergence,and convex constraint set[J].IEEE Transactions on Automatic Control,2017,62(5):2239-2253
[11] Lu J,Tang C Y.Zero-gradient-sum algorithms for distributed convex optimization:the continuous-time case[J].IEEE Transactions on Automatic Control,2012,57(9):2348-2354
[12] Song Y F,Chen W S.Finite-time convergent distributed consensus optimisation over networks[J].IET Control Theory & Applications,2016,10(11):1314-1318
[13] Zhu W,Pu H Z,Wang D D,et al.Event-based consensus of second-order multi-agent systems with discrete time[J].Automatica,2017,79:78-83
[14] Dimarogonas D V,Frazzoli E,Johansson K H.Distributed event-triggered control for multi-agent systems[J].IEEE Transactions on Automatic Control,2012,57(5):1291-1297
[15] Seyboth G S,Dimarogonas D V,Johansson K H.Event-based broadcasting for multi-agent average consensus[J].Automatica,2013,49(1):245-252
[16] Berneburg J,Nowzari C.Robust dynamic event-triggered coordination with a designable minimum inter-event time[C]//IEEE Transactions on Automatic Control.September 1,2020,IEEE,2020:3417-3428
[17] Qian Y Y,Wan Y.Design of distributed adaptive event-triggered consensus control strategies with positive minimum inter-event times[J].Automatica,2021,133:109837
[18] 王誉达,查利娟,刘金良,等.基于事件触发和欺骗攻击的多智能体一致性控制[J].南京信息工程大学学报(自然科学版),2019,11(4):380-389.WANG Yuda,ZHA Lijuan,LIU Jinliang,et al.Event-based consensus of multi-agent systems with deception attacks[J].Journal of Nanjing University of Information Science & Technology(Natural Science Edition),2019,11(4):380-389
[19] 杨涛,徐磊,易新蕾,等.基于事件触发的分布式优化算法[J].自动化学报,2022,48(1):133-143.YANG Tao,XU Lei,YI Xinlei,et al.Event-triggered distributed optimization algorithms[J].Acta Automatica Sinica,2022,48(1):133-143
[20] Kia S S,Cortés J,Martínez S.Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication[J].Automatica,2015,55:254-264
[21] 赵中原,陈刚.基于事件驱动的二次凸优化问题分布式优化算法[J].控制与决策,2019,34(8):1635-1644.ZHAO Zhongyuan,CHEN Gang.Distributed event-triggered algorithm for quadratic convex optimization problem[J].Control and Decision,2019,34(8):1635-1644
[22] Liu J Y,Chen W S.Distributed convex optimisation with event-triggered communication in networked systems[J].International Journal of Systems Science,2016,47(16):3876-3887
[23] Zhao Z Y,Chen G.Event-triggered scheme for zero-gradient-sum optimisation under directed networks with time delay[J].International Journal of Systems Science,2021,52(1):47-56
[24] Du W,Yi X L,George J,et al.Distributed optimization with dynamic event-triggered mechanisms[C]//2018 IEEE Conference on Decision and Control(CDC).December 17-19,2018,Miami,FL,USA.IEEE,2019:969-974

地址：江苏省南京市宁六路219号邮编：210044

联系电话：025-58731025 E-mail：nxdxb@nuist.edu.cn

分享给微信好友或者朋友圈

使用微信“扫一扫”功能。

最小事件间隔时间可设计的分布式事件触发优化算法

Distributed event-triggered optimization algorithm with designable minimum inter-event time

摘要

Abstract

关键词

Keywords

0 引言

1 预备知识及问题描述

1.1 图论

1.2 凸函数

(1)

(2)

(3)

1.3 问题描述

(4)

2 算法设计及主要结果

2.1 分布式优化算法

(5)

(6)

2.2 事件触发条件

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

(33)

(34)

(35)

(36)

(37)

(38)

3 仿真结果

4 结论

参考文献

基本信息

基金信息

引用信息

稿件历史

参考文献