科学网-时变非平衡有向图下变分不等式的分布式求解算法-邹铁枫的博文

时变非平衡有向图下变分不等式的分布式求解算法

2025-7-9 08:59

阅读：343

本次分享“Distributed algorithm for solving variational inequalities over time-varying unbalanced digraphs (时变非平衡有向图下变分不等式的分布式求解算法)”。

变分不等式是研究优化和均衡问题的重要工具，在经济、交通、能源、通信等领域有广泛的应用。求解变分不等式问题的经典算法大都是集中式的，即假定所有数据存储和处理操作都在同一个计算单元上执行。在大数据时代，数据量爆炸性增长，这些集中式算法受单机存储和计算瓶颈的限制难以部署和实现。此外，许多实际问题的数据可能广泛散布于不同的物理设备或地理位置，无法使用传统的并行框架进行有效处理。因此，开发多节点协同的分布式算法求解变分不等式问题尤为重要，本文将围绕这一主题展开。

Distributed algorithm for solving variational inequalities over time-varying unbalanced digraphs（时变非平衡有向图下变分不等式的分布式求解算法）

作者：Yichen Zhang1, Yutao Tang1, Zhipeng Tu2, Yiguang Hong3

机构：1 北京邮电大学；2 华为技术有限公司；3 同济大学

引用信息：Zhang, Y., Tang, Y., Tu, Z. et al. Distributed algorithm for solving variational inequalities over time-varying unbalanced digraphs. Control Theory Technol. 22, 431–441 (2024). https://doi.org/10.1007/s11768-024-00223-9

全文链接：https://rdcu.be/dKM9g

摘要

本文研究了一种时变非平衡有向图下变分不等式的分布式计算模型。其中，每个节点仅可访问完整映射的一部分，并获取约束集的局部信息。作者通过构造一组辅助向量补偿图的非平衡性，提出了一种基于一致性的分布式投影算法。该算法仅需各节点进行局部计算和通信。作者在一致强联合连通非平衡图和异质局部约束集条件下证明了算法的收敛性。数值仿真验证了本文算法的有效性。

引言

随着先进感知和通信技术的蓬勃发展，大规模优化和均衡问题的分布式求解已成为当前信息领域的研究热点。众所周知，变分不等式能为优化和均衡问题的研究提供统一的数学框架。因此，开发设计变分不等式的分布式求解算法具有重要的研究意义。

尽管早在 20 世纪 80 年代就有人作了初步尝试，但这一主题重新得到关注主要得益于变分不等式在分布式优化研究中的应用。典型的分布式优化问题可以等价地写成一个映射为可分形式的变分不等式问题，而每个节点仅知道该映射的一部分。通过将变分不等式的经典求解算法加以推广，即可开发出不同的分布式优化算法。

另一方面，变分不等式的决策变量可能分配在不同的节点，继而带来一定的分布式特性。比如，不完全信息的非合作博弈中就有类似问题。通常，这样得到的变分不等式不具备可分结构，其在一般有向图下的求解问题更具挑战性。

为此，本文提出了一种新的变分不等式的分布式计算模型。在该模型中，每个节点负责维护所有决策变量的一个子集，同时仅能访问完整映射的部分分量，并获取约束集的局部信息。本文考虑节点间交互拓扑是一般时变非平衡有向图的情况。为求解给定变分不等式，作者首先将它们等价地分解为一族维数较小但相互耦合的变分不等式，随后引入辅助向量补偿图的非平衡性，最终开发了一种基于一致性的分布式投影算法，并在一致强联合连通图假设下讨论了选取不同步长时该算法的收敛特性。

本文的主要贡献如下：

提出了一种新的变分不等式的分布式计算模型。该模型所关注的分布式特性源自变分不等式决策变量在不同节点间的分配，而不是已有文献中讨论的映射的可分结构。
开发了一种新的基于一致性的分布式投影算法，实现了一致强联合连通有向图下变分不等式的求解目标。特别地，该算法无需要求图的平衡性，即可有效用于求解许多文献中讨论的非合作博弈的纳什均衡搜索问题。

结论

本文针对变分不等式的决策变量可能分配在不同节点这一问题，提出了一种新的变分不等式的分布式计算模型。作者通过引入辅助向量补偿图的非平衡性，设计了一种基于一致性的分布式投影算法，并证明了该算法在时变非平衡有向图下求解给定变分不等式问题的有效性。下一步，作者可能会考虑如何去掉映射的单调性假设或者设计通信高效的分布式算法求解该问题。

作者介绍

Yichen Zhang，2021年于北京邮电大学获测控技术与仪器专业学士学位。现在本校攻读控制科学与工程硕士学位。研究兴趣包括分布式优化和多智能体系统。

Yutao Tang，2009年和2014年分别在哈尔滨工程大学和中国科学院获得应用数学学士学位和运筹学与控制论博士学位。现任北京邮电大学人工智能学院教授。研究兴趣包括非线性控制、分布式优化、移动机器人和机器学习。

Zhipeng Tu，2018年和2023年分别在西安交通大学和中国科学院获数学与应用数学学士学位和系统理论博士学位。现就职于华为技术有限公司网络技术实验室。研究兴趣包括分布式优化、机器学习和并行训练。

Yiguang Hong，1987年和1990年于北京大学获学士和硕士学位，1993年于中国科学院获博士学位。现任同济大学电子与信息工程学院教授，上海自主智能无人系统科学中心副主任。曾任中国科学院系统控制重点实验室主任，中国科学院国家数学与交叉科学中心信息交叉部主任。他还是IEEE Fellow、人工智能学会会士、自动化学会会士。研究兴趣包括非线性控制、多智能体系统、分布式优化和博弈、机器学习和社交网络。

期刊简介

640 spr.jpg

欢迎扫码进入期刊主页

Control Theory and Technology (CTT), 中文名《控制理论与技术》, 创刊于2003年，原刊名为Journal of Control Theory and Applications，2014年刊名更改为Control Theory and Technology。由华南理工大学与中国科学院数学与系统科学研究院联合主办，主要报道系统控制科学中具有新观念、新思想的理论研究成果及其在各个领域中的应用。目前被 ESCI (JIF 1.5)、EI、Scopus (CiteScore 3.2)、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 （欢迎扫码关注期刊微信公众号）