从混合到撕裂：基于消息传递的去中心化优化中的图分解

arXiv:2610.03709v1 公告类型：cross 摘要：我们研究无向图上光滑强凸函数之和的最小化问题，其中每个函数由一个智能体持有，且通信仅限于图中的邻居。现有的去中心化方法，无论是基于 gossip 还是基于生成树上的路由，通常都利用网络混合或聚合信息，以支持预先设定的局部优化更新。这种以通信为中心的观点缺少一个通用框架，无法利用图结构来共同设计优化子问题，以及智能体通过协作计算和通信协同求解这些子问题的过程。我们从第一性原理出发构建了这样一个框架，共同设计一致性约束的线性表示、所得对偶变量的分块（联合优化），以及协同求解各个分块子问题的智能体连通簇和其所分配的子图。GATE（Graph-Tearing message passing）是该框架的一个初步实例：每条边对应一个变量，并采用树分块。在每次迭代中，智能体通过最小化两个端点的代价到达消息之和来更新其所分配的边变量，并对所得结果进行松弛。消息则通过遵循树递归的局部最小化过程进行更新。为降低每次迭代的计算和通信成本，我们进一步提出 GATE-S，这是一种代理变体，采用易处理的局部模型和轻量级消息参数化。我们证明了算法的线性收敛性，其收敛速率明确体现了函数正则性、网络拓扑结构与所选划分之间的相互作用，从而揭示了图分解的影响。我们通过数值实验验证理论结果，并评估算法的效率。