引用本文

 

杨涛, 徐磊, 易新蕾, 张圣军, 陈蕊娟, 李渝哲. 基于事件触发的分布式优化算法. 自动化学报, 2022, 48(1): 133−143 doi: 10.16383/j.aas.c200838

Yang Tao, Xu Lei, Yi Xin-Lei, Zhang Sheng-Jun, Chen Rui-Juan, Li Yu-Zhe. Event-triggered distributed optimization algorithms. Acta Automatica Sinica, 2022, 48(1): 133−143 doi: 10.16383/j.aas.c200838

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200838?viewType=HTML

文章简介

关键词

分布式优化, 事件触发通信, Zeno行为, 比例积分算法

摘   要

本文研究了一类分布式优化问题, 其目标是通过局部信息交换使由局部成本函数之和构成的全局成本函数最小. 针对无向连通图, 我们提出了两种基于比例积分策略的分布式优化算法. 在局部成本函数可微且凸的条件下, 证明了所提算法渐近收敛到全局最小值点. 更进一步, 在局部成本函数具有局部Lipschitz梯度和全局成本函数关于全局最小值点是有限强凸的条件下, 证明了所提算法的指数收敛性. 此外, 为了避免智能体之间的连续通信和减少通信负担, 将所提的两种分布式优化算法与事件触发通信相结合, 提出了两种基于事件触发的分布式优化算法. 证明了提出的事件触发优化算法不存在Zeno行为, 并且在相应条件下保持了与连续通信下分布式优化算法一样的收敛性. 最后, 通过数值仿真验证了上述理论结果.

引   言

在多智能体系统中, 每个智能体(节点)都具有一个局部成本函数, 分布式优化的目标是使由局部成本函数之和所构成的全局成本函数最小. 分布式优化的研究由来已久, 至少可以追溯到. 近年来, 由于其在电力系统、机器学习和传感器网络等领域的广泛应用, 这一研究重新引起了关注. 研究者设计了多种分布式优化算法, 详见综述文章[3-10], 大致可分为离散时间算法和连续时间算法.

现有的大多数离散时间算法均基于一致性算法和分布式次梯度下降(Distributed gradient descent, DGD)算法. 尽管DGD算法可以处理非光滑凸函数的分布式优化问题, 并在通讯延迟、丢包等多个方向上进行扩展以处理更为实际的情况, 但由于使用了衰减步长, 因此收敛速度较慢. 在步长固定的情况下, 虽然DGD算法收敛速度快, 但只能收敛到最小值点的邻域. 最近的研究集中在利用历史信息来设计具有固定步长的加速算法. 具体而言, 文献[18-19]中提出的算法是基于比例积分(Proportional integral, PI)控制策略, 文献[20-25]中提出的算法是基于分布式不精确梯度算法和分布式动态平均梯度跟踪技术. 现有的连续时间算法可以分为两类: 第一类是文献[27-29]中提出的基于梯度的算法, 这类算法本质上都是基于PI控制策略, 其中每个智能体使用一个辅助状态(积分反馈)来校正由不同局部梯度引起的误差; 第二类算法使用二阶Hessian信息, 例如文献[30-32].

为了避免连续通信和减少通信负担, 事件触发通信和控制的思想最初是针对单个系统提出的. 后来这种思想被应用到分布式一致性问题. 近年来, 研究者提出了基于事件触发通信的分布式优化算法. 文献[29]提出了一种不存在Zeno行为的事件触发算法, 即在有限时间内不会触发无限多次事件, 并针对无向连通图, 在局部成本函数强凸以及梯度局部Lipschitz且可微的条件下, 证明了算法指数收敛到最小值点的邻域. 受文献[30]提出的零梯度和 (Zero-gradient-sum, ZGS)算法的启发, 文献[44]提出周期性的事件触发机制; 文献[45]则设计了基于动态事件触发的ZGS算法. 针对无向连通图或权平衡强连通的有向图, 在局部成本函数强凸且具有局部Lipschitz Hessians的条件下, 证明了算法的指数收敛性.

本文提出了两种基于比例积分策略的分布式优化算法, 并证明了算法的收敛性. 在此基础上, 为了减少通信负担, 我们提出了基于事件触发的分布式优化算法, 并证明了提出的基于事件触发的优化算法不存在Zeno行为, 且保持了与连续通信下分布式优化算法相同的收敛性. 文献[29]提出的事件触发算法只有在局部成本函数强凸且具有局部Lipschitz梯度的条件下收敛到全局最小值点的一个邻域, 而我们提出的算法在局部成本函数可微且凸的条件下, 即可精确地指数收敛到唯一的全局最小值点. 与文献[46]中提出的算法相比, 我们提出的算法更简单, 因为在执行文献[46]中的算法时需要一些特殊设计的增益参数. 与文献[44-45]中提出的基于二阶Hessian信息的事件触发ZGS算法相比, 我们提出的算法是基于一阶梯度的, 易于实现. 此外, ZGS算法需要特殊的初始化, 而我们提出的算法允许任意初始化.

本文其余部分安排如下. 第1节介绍图论的基础知识. 第2节介绍本文所考虑的分布式优化问题. 第3节提出两种基于PI控制策略的分布式优化算法, 并分析所提算法的收敛性. 第4节提出基于事件触发通信机制的分布式优化算法并分析其收敛性. 第5节利用数值仿真验证理论结果. 第6节总结本文的主要结果并介绍未来的研究方向.

图 2  算法(4)中智能体6, 16, 26, 36, 46的状态演化

图 3  算法(6)中智能体6, 16, 26, 36, 46的状态演化

作者简介

杨   涛

东北大学流程工业综合自动化国家重点实验室教授. 主要研究方向为工业人工智能, 信息物理系统, 分布式协同控制和优化.

E-mail: yangtao@mail.neu.edu.cn

徐   磊

东北大学流程工业综合自动化国家重点实验室博士研究生. 主要研究方向为分布式控制及优化, 网络化系统, 马尔科夫跳变系统.

E-mail: 2010345@stu.neu.edu.cn

易新蕾

瑞典皇家理工学院电气工程与计算机科学学院博士后. 主要研究方向为在线优化, 分布式优化, 事件驱动控制.

E-mail: xinleiy@kth.se

张圣军

北德州大学电气工程专业博士研究生. 主要研究方向为分布式优化, 统计学习, 稀疏主成分分析.

E-mail: ShengjunZhang@my.unt.edu

陈蕊娟

华中科技大学人工智能与自动化学院博士研究生. 主要研究方向为基于动力系统的优化算法的设计和理论分析.

E-mail: ruijuancheni@hust.edu.cn

李渝哲

东北大学流程工业综合自动化国家重点实验室教授. 主要研究方向为网络化系统, 信息物理系统, 人工智能与信息安全. 本文通信作者.

E-mail: yuzheli@mail.neu.edu.cn

相关文章

[1]   陈世明, 邵赛, 姜根兰. 基于事件触发二阶多智能体系统的固定时间比例一致性. 自动化学报, 2022, 48(1): 261-270. doi: 10.16383/j.aas.c190128

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190128

[2]   张岱峰, 段海滨. 恶意攻击下基于分布式稀疏优化的安全状态估计. 自动化学报, 2021, 47(4): 813-824. doi: 10.16383/j.aas.c200276

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200276

[3]   时侠圣, 杨涛, 林志赟, 王雪松. 基于连续时间的二阶多智能体分布式资源分配算法. 自动化学报, 2021, 47(8): 2050-2060. doi: 10.16383/j.aas.c200968

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200968

[4]   付维明, 秦家虎, 朱英达. 基于扩散方法的分布式随机变分推断算法. 自动化学报, 2021, 47(1): 92-99. doi: 10.16383/j.aas.c200445

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200445

[5]   滕菲, 单麒赫, 李铁山. 智能船舶综合能源系统及其分布式优化调度方法. 自动化学报, 2020, 46(9): 1809-1817. doi: 10.16383/j.aas.c200176

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200176

[6]   黄博南, 王勇, 李玉帅, 刘鑫蕊, 杨超. 基于分布式神经动态优化的综合能源系统多目标优化调度. 自动化学报. doi: 10.16383/j.aas.c200168

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200168

[7]   王闯, 韩非, 申雨轩, 李学贵, 董宏丽. 基于事件触发的全信息粒子群优化器及其应用. 自动化学报. doi: 10.16383/j.aas.c200621

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200621

[8]   席磊, 周礼鹏. 分布式多区域多能微网群协同AGC算法. 自动化学报, 2020, 46(9): 1818-1830. doi: 10.16383/j.aas.c200105

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200105

[9]   潘子肖, 雷德明. 基于问题性质的分布式低碳并行机调度算法研究. 自动化学报, 2020, 46(11): 2427-2438. doi: 10.16383/j.aas.c180581

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180581

[10]   李玉帅, 李天义, 高炜, 高文忠. 基于异步动态事件触发通信策略的综合能源系统分布式协同优化运行方法. 自动化学报, 2020, 46(9): 1831-1843. doi: 10.16383/j.aas.c200172

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200172

[11]   陈世明, 管俊杰, 高彦丽, 裴惠琴, 邱昀. 组合连通拓扑下基于事件触发的多智能体快速一致性算法. 自动化学报, 2018, 44(12): 2269-2277. doi: 10.16383/j.aas.2018.c160839

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c160839

[12]   祁波, 孙书利. 带未知通信干扰和丢包补偿的多传感器网络化不确定系统的分布式融合滤波. 自动化学报, 2018, 44(6): 1107-1114. doi: 10.16383/j.aas.2017.c160652

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160652

[13]   杨旭升, 张文安, 俞立. 适用于事件触发的分布式随机目标跟踪方法. 自动化学报, 2017, 43(8): 1393-1401. doi: 10.16383/j.aas.2017.c150777

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c150777

[14]   刘莉, 万九卿. 视觉传感网络分布式在线数据关联. 自动化学报, 2014, 40(1): 117-125. doi: 10.3724/SP.J.1004.2014.00117

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.00117

[15]   汤文俊, 张国良, 曾静, 孙一杰, 吴晋. 一种适用于稀疏无线传感器网络的改进分布式UIF算法. 自动化学报, 2014, 40(11): 2490-2498. doi: 10.3724/SP.J.1004.2014.02490

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.02490

[16]   张勇刚, 王程程, 魏野, 李宁, 周卫东. 一种空间分布式变阶数自适应网络滤波算法. 自动化学报, 2014, 40(7): 1355-1365. doi: 10.3724/SP.J.1004.2014.01355

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.01355

[17]   余宏旺, 郑毓蕃. 多智能体系统在分布式采样控制下的动力学行为. 自动化学报, 2012, 38(3): 357-365. doi: 10.3724/SP.J.1004.2012.00357

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2012.00357

[18]   苏兆品, 蒋建国, 梁昌勇, 张国富. 一种基于P学习的分布式并行多任务分配算法. 自动化学报, 2011, 37(7): 865-872. doi: 10.3724/SP.J.1004.2011.00865

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2011.00865

[19]   文成林, 潘泉, 张洪才, 戴冠中. 多传感器多模型动态系统多尺度分布式融合估计算法. 自动化学报, 2000, 26(增刊B): 66-70.

http://www.aas.net.cn/cn/article/id/14730

[20]   梁锋. 大系统的分布式控制. 自动化学报, 1990, 16(6): 538-541.

http://www.aas.net.cn/cn/article/id/14745