博文

网络中的无梯度分布式在线优化

已有 237 次阅读 2025-5-19 09:04 |个人分类:文章推荐|系统分类:博客资讯

编辑荐语

本期将给大家分享“Gradient-free distributed online optimization in networks (网络中的无梯度分布式在线优化)”。如您对本期相关内容有好的理解与建议，欢迎评论区留言。

近年来，多智能体网络与分布式算法在工程中备受关注，特别是分布式凸优化算法，其广泛应用于电力调度、覆盖控制和资源分配等领域。传统研究多假设目标函数时间不变，但实际场景中目标函数常随时间变化，催生了分布式在线凸优化问题，算法性能通过遗憾函数评估。已有算法多依赖投影算子以假设估计值有界，但计算资源消耗高。本文提出无梯度且无投影的分布式在线凸优化算法，并在时变网络上实现 O(log(T)) 遗憾值及估计一致性，同时还引入了一种随机性差分来替代梯度信息，并基于此设计了一种随机差分无梯度分布式在线凸优化算法。

Gradient-free distributed online optimization in networks网络中的无梯度分布式在线优化Yuhang Liu1 · Wenxiao Zhao2,3 · Nan Zhang1 · Dongdong Lv1 · Shuai Zhang1

机构：1 国网信息通信有限公司，信息通信研究院；2 中国科学院数学与系统科学研究院；3 中国科学院大学数学科学学院

引用：Liu, Y., Zhao, W., Zhang, N. et al. Gradient-free distributed online optimization in networks. Control Theory Technol. (2025).https‍://doi.org/10.1007/s11768-025-00242-0

全文链接：https://rdcu.be/‍eaH3M

摘要

本文研究了时变网络上的分布式在线优化问题，其中网络中的每个个体都有其自身的时变目标函数，目标是最小化累积的总体损失。此外，本文关注不使用梯度信息和投影算子的分布式算法，以提高适用性和计算效率。通过引入确定性差分和随机性差分来替代目标函数的梯度信息，并去除传统算法中的投影算子，本文设计了两种无梯度且无需投影步骤的分布式在线优化算法，这些算法能够节省大量计算资源，同时对适用性要求更低。本文证明了这两种算法均能在局部强凸目标下分别实现估计的一致性和 O(log(T)) 的遗憾值。最后，提供了一个仿真实例以验证理论结果。

引言

近年来，多智能体网络和分布式算法在自然科学与工程领域受到了广泛关注。在各种分布式算法中，分布式凸优化算法因其在实际场景中的广泛适用性而备受重视，例如电力网络中的经济调度、多智能体系统中的覆盖控制、无线传感器网络中的资源分配等。在分布式凸优化问题中，网络中的每个代理都有其独立的目标函数（仅自己可见），并旨在协同优化整个网络的全局目标函数。目前已有大量关于分布式凸优化算法的研究成果，包括带约束的分布式凸优化、随机框架下的算法、抵御对抗性攻击的算法、以及连续时间中的算法等。

需要注意的是，上述文献均假设目标函数是时不变的。然而，在许多实际场景中，例如电力系统中随时间变化负载的分布式控制和移动目标的分布式跟踪，网络系统中的不确定性显著影响问题，导致目标函数成为时间变化的函数。因此，本文聚焦于目标函数随时间变化的分布式凸优化问题，称为分布式在线凸优化。针对时变目标函数的优化算法通常通过遗憾函数（regret function）来评估其性能，遗憾函数衡量了估计值的损失与最佳固定点损失之间的累积差异。一般来说，如果算法的遗憾值相对于时间指标 T 是次线性的，则认为该算法是可接受的。

已有若干研究基于遗憾函数探讨了分布式在线凸优化问题。有研究提出了一种分布式投影次梯度算法，对于凸目标和强凸目标分别建立了O(\sqrt{T})和 O(log(T))的遗憾值。另一项研究提出了一种分布式对偶平均算法，取得了O(\sqrt{T})的遗憾值。

需要注意的是，上述大部分研究成果都依赖于每个时间步上的投影操作，将估计值投影到一个紧集上，这隐含地假设估计值始终是有界的。然而，这一假设预先要求估计序列具有统一边界，这在考虑整个状态空间的非紧性时有所局限，并且会消耗更多计算资源。相比之下，一些研究移除了估计序列具有统一边界的假设。具体而言，一项研究提出了一类结合次梯度下降和分布式反馈的算法，并给出了O(log(T))的遗憾值。在另一项研究中，建立了一种具有遗憾值O(\sqrt{T})的分布式镜像下降算法。还有研究设计了推和算法（push-sum algorithm），并证明了O(log(T))的遗憾值。

尽管文献中讨论的算法各不相同，但它们通常依赖于目标函数的梯度或次梯度信息，而这在某些应用中可能是计算昂贵或不切实际的。因此，研究者开始关注无梯度分布式优化的理论研究，包括关于时不变目标函数的研究以及关于时间变化目标函数的研究。这些算法通过将目标函数值的观测值引入差分中，以此替代算法设计中的梯度信息。例如，有研究提出了具有时不变非凸目标函数的无梯度分布式优化。还有研究探讨分布式在线资源分配问题，其中个体之间的优化变量是不同的。有文献研究了动态环境下的 Byzantine 攻击下的分布式在线优化。值得注意的是，一些文献研究了投影分布式在线凸优化问题，其中所有代理具有相同的优化变量。其中一项研究设计了两种替代梯度信息的差分方式，并提出了两类无梯度的投影分布式在线算法。

本文将研究无梯度且无投影步骤的分布式在线凸优化算法，论文的主要贡献总结如下：

我们首先引入一种基于目标函数值观测的确定性差分，并设计了一种无梯度且无投影步骤的分布式在线凸优化算法。需要注意的是，先前的研究中提出的无梯度算法依赖于投影步骤将估计值限制在紧集上，而这种方法消耗更多计算资源并具有一定的应用局限性。
在网络为时变网络的假设下，我们证明了所设计的分布式算法对于局部强凸目标函数实现了O(log(T))的遗憾值，并建立了所有个体估计值的一致性。
我们还引入了一种随机性差分来替代梯度信息，并基于此设计了一种随机差分无梯度分布式在线凸优化算法。同样地，我们证明了该算法实现了估计值的一致性和O(log(T))的遗憾值。

结论

本文提出了两类用于分布式在线凸优化的无梯度算法，这两类算法均省略了投影步骤。作者证明了算法能够实现估计值的一致性以及遗憾值的次线性。未来的研究中将探索对优化变量施加更复杂的约束、网络拓扑的变化，以及设计对网络攻击具有鲁棒性的算法。

作者介绍

Yuhang Liu，2018年获得山东大学数学学院学士学位，并于2023年获得中国科学院数学与系统科学研究院（AMSS）系统科学研究所（ISS）博士学位。她目前是国网信息通信集团有限公司（北京）的工程师。她的研究兴趣主要集中在分布式/集中式在线优化和博弈方法。

Wenxiao Zhao，2008年获得中国科学院数学与系统科学研究院（AMSS）系统科学研究所（ISS）运筹学与控制论博士学位。目前，他是中国科学院数学与系统科学研究院的研究员。他的研究兴趣主要包括系统辨识与自适应控制、变量和特征选择以及分布式随机优化。

Nan Zhang，2018年获得北京科技大学博士学位。目前，她是国网信息通信集团有限公司（北京）的高级工程师。她当前的研究方向包括电力系统自动化技术、电力物联网以及边缘计算等。

Dongdong Lv毕业于辽宁工程技术大学，获得硕士学位。目前，他是国网信息通信集团有限公司（北京）的工程师，主要从事电力物联网和电力智能终端技术的研究。

Shuai Zhang，2018年获得华北电力大学博士学位。目前，他是国网信息通信集团有限公司（北京）的高级工程师。他当前的研究方向包括电力物联网、边缘计算以及智能传感器与终端技术。

期刊简介

640 spr.jpg

欢迎扫码进入期刊主页

Control Theory and Technology (CTT), 中文名《控制理论与技术》, 创刊于2003年，原刊名为Journal of Control Theory and Applications，2014年刊名更改为Control Theory and Technology。由华南理工大学与中国科学院数学与系统科学研究院联合主办，主要报道系统控制科学中具有新观念、新思想的理论研究成果及其在各个领域中的应用。目前被 ESCI (JIF 1.7)、EI、Scopus (CiteScore 3.1，更新于2025年4月5日)、CSCD、INSPEC、ACM 等众多数据库收录, 并于2013–2018年获得两期中国科技期刊国际影响力提升计划项目资助。2017–2021年连续获得“中国最具国际影响力学术期刊”和“中国国际影响力优秀学术期刊”称号，获得广东省高水平科技期刊建设项目(2021-2024年)，2022-2024年进入中国科协自动化学科领域高质量科技期刊目录。

官网：https://link.springer.com/journal/11768 (即http://www.springer.com/11768)

https://jcta.ijournals.cn/cta_en/ch/index.aspx

投稿：https://mc03.manuscriptcentral.com/ctt

微信：ControlTheoryTech （欢迎扫码关注期刊微信公众号）