提出一种在图结构非线性规划中可证明收敛的消息传递新范式。
A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing
- 将图分解为树簇，通过消息传递并行求解局部子问题。
- 支持低维近似代理，减少通信开销且保持有限步内更新。
- 首次在环状图上实现收敛，适合大规模分布式优化场景。
研究具有局部变量耦合的有限和非线性规划问题，其耦合关系由（超）图编码。本文提出一种符合图结构的分解框架，以严格、可实现且可证明的方式引入消息传递于连续优化。将（超）图划分为树簇（超树因子图），每轮迭代中，各代理并行求解局部子问题：目标函数拆分为簇内项（由簇树上的单次最小-和消息传递汇总的成本到未来消息表示）与簇间耦合项（采用雅可比风格，使用最新的跨簇变量）。为降低计算/通信开销，方法支持图合规的代理，用紧凑的低维参数化替代精确消息或局部求解；在超图中，同一原则可实现代理超边分裂，缓解重叠超边带来的负担，同时保持有限时间内的簇内消息更新及高效计算/通信。我们建立了凸与非凸目标下的收敛性，给出依赖拓扑与划分的显式收敛速率，量化曲率与耦合影响，指导聚类设计与可扩展性。据我们所知，这是首个在含环图上收敛的消息传递方法。
原文摘要 · Abstract (English)
We study finite-sum nonlinear programs with localized variable coupling encoded by a (hyper)graph. We introduce a graph-compliant decomposition framework that brings message passing into continuous optimization in a rigorous, implementable, and provable way. The (hyper)graph is partitioned into tree clusters (hypertree factor graphs). At each iteration, agents update in parallel by solving local subproblems whose objective splits into an {\it intra}-cluster term summarized by cost-to-go messages from one min-sum sweep on the cluster tree, and an {\it inter}-cluster coupling term handled Jacobi-style using the latest out-of-cluster variables. To reduce computation/communication, the method supports graph-compliant surrogates that replace exact messages/local solves with compact low-dimensional parametrizations; in hypergraphs, the same principle enables surrogate hyperedge splitting, to tame heavy hyperedge overlaps while retaining finite-time intra-cluster message updates and efficient computation/communication. We establish convergence for (strongly) convex and nonconvex objectives, with topology- and partition-explicit rates that quantify curvature/coupling effects and guide clustering and scalability. To our knowledge, this is the first convergent message-passing method on loopy graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。