{"ID":2823647,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.24676","arxiv_id":"2512.24676","title":"A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2512.24676","url_pdf":"https://arxiv.org/pdf/2512.24676v2","authors":"[\"Kuangyu Ding\",\"Marie Maros\",\"Gesualdo Scutari\"]","published":"2025-12-31T07:05:37Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.IT\",\"cs.LG\"]","methods":"[]","has_code":false}