在时变不平衡有向图中进行分布式在线凸优化，同时考虑多个耦合约束

《IEEE Transactions on Systems, Man, and Cybernetics: Systems》：Distributed Online Convex Optimization Over Time-Varying Unbalanced Digraphs With Multiple Coupled Constraints

针对时变不平衡有向图中多时变耦合约束的分布式在线凸优化问题，提出新型时变分布 primal-dual push-pull 算法，通过构造多耦合约束模型和转换矩阵实现全局约束优化，理论证明算法在动态 regret 和约束违反方面达到最优下界，并通过数值实验验证算法有效性。

　　

摘要：

本文旨在解决在时变（TV）不平衡有向图中受到多重耦合约束的分布式在线凸优化（DOCO）问题。现有的全局约束模型和耦合约束模型（其约束数量与节点数量相关）无法充分反映多重耦合约束优化问题的特性。为了解决这一问题，本文构建了一个新的多重耦合约束模型，该模型仅包含部分节点。此外，实际的时变场景通常具有复杂的网络连接性，这需要使用多种矩阵来融合各种信息。考虑到网络连接性的要求，本文提出了一种新颖的时变分布式原始-对偶推拉（TDPP）算法，该算法能够将两种类型的权重矩阵转换为全折叠行随机（RS）矩阵，以解决多重耦合约束问题。在一些通用且必要的假设和条件下，通过严格的理论分析可以实现对期望的次线性动态遗憾和约束违反量的控制。最后，通过两个数值示例验证了TDPP算法相较于类似算法的优越性和有效性。

引言

分布式在线凸优化（DOCO）已在智能电网、机器人运动规划、网络资源分配等多个领域得到研究[1]。与传统分布式优化不同，在线学习方法被适当地视为建模序列决策问题的有效工具。这些问题可以被视为学习者与对手之间的持续博弈。在此过程中，学习者通过协作来最小化全局成本函数，并在每个时刻选择相应的行动。随后，学习者会获得局部成本函数的相关信息。DOCO的评价标准包括针对恒定和动态最优值的静态和动态遗憾[2]。例如，在[3]中提出了一种分布式自适应次梯度算法，用于求解时变图上的分布式优化问题。形式上，动态遗憾比静态遗憾更适合不确定和变化莫测的情景。张等人[4]采用动态遗憾来评估所提出算法在时变优化器下的成本。随后，在[5]中提出了一种分布式在线算法来解决伪凸优化问题。此外，在[6]中，动态遗憾也被扩展为非凸优化问题的评估标准。