引用本文

刘奕葶, 马铭莙, 付俊. 基于有向图的分布式连续时间非光滑耦合约束凸优化分析. 自动化学报, 2024, 50(1): 66−75 doi: 10.16383/j.aas.c210808

Liu Yi-Ting, Ma Ming-Jun, Fu Jun. Distributed continuous-time non-smooth convex optimization analysis with coupled constraints over directed graphs. Acta Automatica Sinica, 2024, 50(1): 66−75 doi: 10.16383/j.aas.c210808

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

关键词

多智能体网络，分布式优化，加权平衡有向图，耦合不等式约束 

摘要

研究一类分布式优化问题, 其目标是在满足耦合不等式约束和局部可行集约束的情况下使非光滑全局代价函数值最小. 首先, 对原有的分布式连续时间投影算法进行拓展, 结合线性代数理论分析, 设计一个适用于强连通加权平衡有向通信网络拓扑图的算法. 其次, 在局部代价函数和耦合不等式约束函数是非光滑凸函数的假设条件下, 利用Moreau-Yosida函数正则化使目标函数和约束函数近似光滑可微. 然后, 根据强连通加权平衡有向图的分布式连续时间投影算法构造李雅普诺夫函数, 证明该算法下的平衡解是分布式优化问题最优解, 并对算法进行收敛性分析. 最后, 通过数值仿真验证算法的有效性.

文章导读

在多智能体网络中, 分布式优化是决策和数据处理的重要研究方向, 近年来得到广泛研究[1-3]. 每个智能体都有一个局部目标函数, 通过各智能体与其邻居进行信息交互, 共同协作实现由局部目标函数之和构成的全局目标函数最小. 随着近年来互联网、大数据等新兴技术的发展, 资源分配在网络系统中得到广泛的应用, 如电力系统中的经济调度、机器人研究、智能交通、能源制造、无线网络利用率最大化等[4-8], 使系统具有更高的功能效率、稳定性、安全性和可靠性.

分布式优化是通过各智能体间协调合作来实现优化任务, 每个智能体只能访问自己的局部目标函数和局部约束集, 与优化问题相关信息分别存储在各智能体中, 这充分保证了信息的隐私安全[2]. 其次, 各智能体与其邻居节点进行信息交换即可, 不必将数据信息传递到中心节点, 更加节约了通信成本, 也避免了集中式算法会引入的通信单点故障和传感器故障等, 极大地提高了系统的鲁棒性, 也避免了对于处理大规模的复杂优化问题时, 集中式算法会由于智能体之间的通信、计算等限制变得低效[9].

大多数的分布式算法是基于无向通信网络实现的, 如文献[10]提出的分布式精确收敛的一阶算法是通过前两次迭代的状态和梯度信息来更新节点的状态. 分布式不精确梯度方法和梯度跟踪算法中每个节点采用相同的步长, 变量的更新规则中并未用到动态一致性算法, 最终跟踪的梯度不是全局平均梯度. 之后有研究提出在无向图网络下, 改进分布式不精确梯度方法和梯度跟踪技术, 使其在不同节点采用不同步长, 加速优化算法[11-12].

而许多实际问题中的通信网络往往是有向的, 如无线电传感器网络、手机通讯网络等[13]. 有向图中算法收敛是一项具有挑战性的工作, 如文献[12]中所提算法只适用于无向网络, 在有向网络下其算法不具备收敛性. 文献[14]考虑在强连通加权平衡有向图上智能体的资源分配问题. 当局部目标函数强凸时, 其满足等式路径约束和局部凸集的约束条件下, 分布式连续时间投影算法的输出状态可渐近收敛到资源配置问题的最优解. 对局部凸集约束条件进行松弛并提出可以在强连通加权不平衡有向图上的自适应连续时间梯度算法, 其中局部目标函数及其梯度分别满足强凸性和Lipachitz条件, 并证明其指数收敛到问题的最优解. 文献[15]结合Push-Sum算法的核心思想, 提出满足一致强连通时变有向图网络下有效收敛的Subgradient-Push算法. 假设每个节点知道其对应的出度信息, 在次梯度有界的标准假设下使每个节点收敛并且都能找到最优值.

在实际应用中, 当系统对实时优化有较高要求时, 通常会考虑有向网络下的分布式连续时间算法, 其对系统的稳定性及灵活性的高要求可以用来解决资源分配问题[16-19]. 文献[20-21]中提出的分布式投影算法分别用于解决无向图和加权平衡有向图的资源分配问题. 文献[20]在满足线性等式约束和局部可行集约束的前提下, 基于差分投影提出的连续时间算法, 可以不通过初始化对无向网络下的各智能体进行决策分配. 文献[21]考虑了满足局部可行集约束的非光滑代价函数在强连通加权平衡有向网络下的分布式资源分配问题. 利用微分包含和LaSalle集值不变性原理, 证明了解的唯一性和算法的收敛性. 但文献[20-21]所提的连续时间算法对于分布式资源分配仍存在一定的局限性. 文献[20]的算法对加权平衡有向图的有效性仍需探索; 文献[21]中算法在运行前需计算智能体在切锥上的投影, 增加了各智能体之间的交互和计算时间.

分布式优化问题中最简单的情况是无约束优化[22-23]. 如文献[22]通过构造李雅普诺夫函数并进行稳定性分析, 使提出的连续时间分布式算法能够指数收敛到全局最小值. 在无向网络下的分布式连续时间非光滑凸优化问题中[24], 只考虑局部可行集约束, 通过算法在切锥上的投影, 使其在满足局部可行集的约束条件下使算法收敛. 此外, 文献[25]中提出了一种分布式连续时间多智能体系统, 使目标函数在满足不等式路径约束、等式路径约束和局部可行集的约束下算法收敛, 找到全局目标函数的最小值. 上述研究中大多没有考虑耦合约束, 然而耦合路径约束出现在许多实际应用中, 具有重大研究价值.

具有耦合约束的分布式优化, 其中各个智能体的决策变量的可行域会受到其他智能体的影响. 然而在实际应用中, 网络拓扑图中没有中心点时, 耦合约束并不能够满足对各个智能体的资源分配[26]. 在文献[26]中考虑具有耦合的非线性约束, 提出一个改进的拉格朗日函数, 引入局部乘子来解耦约束, 并使用非光滑罚函数保证算法的正确性, 使其鞍点不仅能得到优化问题的最优解, 其原对偶次梯度的算法也是完全分布的. 文献[27]研究解决不等式约束的优化问题, 通过Caratheodory意义上原始对偶动力学的解的存在的唯一性和连续性, 建立在原始对偶动力学下全局渐近收敛的分布式算法.

本文基于文献[28]中提出的分布式连续时间投影算法进行延展, 通过投影的定义及性质, 结合线性代数理论分析, 找到了证明算法的平衡解为分布式优化问题最优解的充分必要条件, 并且可以适用于强连通加权平衡有向通信网络拓扑图. 在满足耦合不等式约束和局部可行集约束的情况下使非光滑全局目标函数最小, 找到分布式优化问题的最优解. 大多数分布式优化问题考虑的是无约束、等式约束或不等式约束[23-25, 29-31], 与文献[24]中的局部可行集约束相比, 我们考虑的耦合不等式路径约束更具有通用性, 难度更高且计算更复杂, 适用范围更广. 本文研究了分布式优化在强连通有向通信拓扑图下的连续时间投影算法, 和文献[12]中无向网络下的离散时间系统相比, 可以实现实时优化, 稳定性更高. 本文通过Moreau-Yosida正则化近似函数解决非光滑目标函数最优问题, 比文献[24]和文献[26]中提出的方法更易于实现. 结合文献[28]中所提算法找到在强连通加权平衡网络下, 满足耦合不等式路径约束和局部可行集约束的最优解.

本文结构安排如下. 第1节介绍本文考虑的分布式优化问题和预备知识; 第2节提出应用在强连通有向图的分布式连续时间投影算法, 并分析证明算法的平衡解为优化问题最优解的充分必要条件; 第3节通过数值实验验证理论结果; 第4节总结本文的主要结论和未来研究方向.

图 1  加权平衡有向交互图

图 2  状态xi的轨迹图

图 3  状态τi的轨迹图

本文研究了在强连通加权平衡的有向通信拓扑网络中, 目标函数和约束为凸函数, 满足耦合不等式路径约束和局部可行集约束的情况下, 找到了证明算法的平衡解为分布式优化问题最优解的充分必要条件, 并且所提分布式连续时间投影算法渐近收敛到全局最小值点. 结合文献[28]中的分布式连续时间投影算法设计, 基于在智能体局部可行集上的投影, 通过近似函数将非光滑的目标函数和约束近似为连续可微的凸函数, 构造李雅普诺夫函数并证明算法收敛到分布式优化问题的最优解. 与加权平衡有向图相比, 分布式算法在加权不平衡有向图的设计对系统性能、资源分配等具有更普遍的意义, 其收敛性分析也具有更大的挑战. 未来的研究方向集中在将分布式投影算法拓展到加权不平衡有向图网络下, 并考虑放缩强连通的假设条件至一致联合连通时算法收敛的问题.

作者简介

刘奕葶

东北大学流程工业综合自动化国家重点实验室硕士研究生. 主要研究方向为分布式优化, 耦合不等式路径约束. E-mail: 13840581163@163.com

马铭莙

东北大学流程工业综合自动化国家重点实验室博士研究生. 主要研究方向为分布式动态优化, 切换系统控制. E-mail: mingjun_mmj@163.com

付俊

东北大学流程工业综合自动化国家重点实验室教授. 主要研究方向为动态优化, 切换系统, 非线性控制. 本文通信作者. E-mail: junfu@mail.neu.edu.cn