次优传输的统计力学

《Physica A: Statistical Mechanics and its Applications》：Statistical mechanics of the Sub-Optimal Transport

　　

摘要

统计力学是分析优化问题的强大框架，能够为匹配、最优传输及其他组合问题提供解析结果。然而，这些方法通常针对零温极限，在该极限下系统坍缩到最优构型，即所谓的基态。真实系统中的构型往往处于中间状态，其中熵与成本最小化之间存在真实的竞争，产生结构化但次优的构型。次优传输模型通过加权二分图的系综来捕捉这一竞争：耦合参数??在熵主导的稠密构型与成本主导的稀疏结构之间进行插值。这一交叉在数值上已被观测到，但缺乏解析理解。在本文中，我们发展了一种平均场理论来刻画这一转变。我们证明，当在固定有限??下取热力学极限时，节点相关的拉格朗日乘子涨落对自由能密度的贡献变为次主导，从而将完全约束模型的主导阶热力学简化为有效的单约束问题。所得自由能对耦合参数是解析的，证实了这是一种平滑交叉而非相变。我们推导了热力学可观测量和权重分布的闭式表达式，并通过数值模拟进行了验证。这些结果建立了次优传输模型的首个解析描述，将统计力学方法扩展到了基态分析之外。

引言

统计力学为分析优化问题提供了强大的框架，使得既能开发高效算法，也能对最优解进行解析刻画。这种联系自然产生：任何优化问题都可以转化为能量最小化问题，其中成本（目标）函数充当哈密顿量。这种对应关系发展出了一套丰富的解析技术（包括副本方法、腔方程和平均场理论），最初是为处理自旋玻璃等无序系统而设计的 [1], [2]。

这些方法也被成功应用于在图上定义的广泛组合优化问题类。其中研究最多的包括匹配问题，其目标是跨两个集合以最小成本配对元素。Mézard和Parisi应用副本方法计算了低温极限和热力学极限下最优匹配的期望成本 [3], [4]，而Aldous在同一极限下找到了严格推导 [5]。相关问题包括稳定婚姻问题和室友问题，其中偏好施加了额外的稳定性约束 [6]，以及旅行商问题，即寻找穿越一组城市的最优环 [7], [8]。最近，[9] 将匹配在巨正则框架内重新表述，恢复了经典的Mézard-Parisi结果，同时与本文描述的模型共享一些数学工具。

最优传输（OT）通过将二元分配替换为受边际约束的连续质量分布，扩展了这一系列问题 [10], [11]。OT寻求一个耦合，指定多少质量沿每条边流动，同时满足规定的行和列和。[12], [13], [14] 使用鞍点方法为离散OT发展了一种统计物理方法，推导出了一个与熵正则化方法 [15] 竞争的算法。

这些分析的共同特征在于：它们针对的是零温极限，在该极限下系统坍缩到单一最优构型，该构型可进行精确处理。然而，真实系统中的构型很少能达到完美优化。次优但具有结构的构型——既非完全随机也非完全优化——经常出现。为零温问题开发的解析工具不能直接适用于这种中间状态，因为先于热力学极限取该极限恰恰消除了感兴趣的次优性：热力学极限与零温极限不可交换。能够描述有限温度下系统、其中熵与成本最小化之间存在真实竞争的统计力学框架，在文献中仍是一个空白。

次优传输（SubOT）模型 [16] 提供了一个自然的环境来解决这一挑战。该模型定义了一个加权二分图的系综，其中耦合参数??在熵主导（稠密、随机）与成本主导（稀疏、结构化）构型之间连续插值。数值模拟揭示了这些状态之间的明确交叉，但在统计力学框架内没有解析理论能捕捉这一转变。提供这样的理论将阐明大尺度结构组织如何从随机性与优化之间的竞争中涌现。

在本文中，我们推导了SubOT模型的平均场理论，以解析方式刻画了从稠密到稀疏的交叉。从具有节点级强度约束的配分函数出发，我们证明在热力学极限优先的极限下，局部拉格朗日乘子涨落的贡献相对于??(????)集体自由能是次广延的。这将完整模型的主导阶热力学简化为有效的单约束问题。所得自由能对??是解析的，证实了这一转变是平滑交叉而非真正的相变。

微妙之处在于热力学极限与零温（??→∞）极限之间的相互作用。如下文所示，在固定系统尺寸下，局部拉格朗日乘子的涨落随??增大而增大；而在固定有限??下，它们随系统尺寸增大而被逐渐抑制。因此，??→∞和??,??→∞的极限不可交换。由于我们关注有限??状态，这种不可交换性促使我们采用热力学极限优先的处理方式，其中局部涨落消失，受控的平均场描述成为可能。

我们通过将预测的热力学可观测量（平均能量、响应性和权重分布）与不同系统尺寸和成本分布下的数值解进行比较来验证该理论。我们的结果建立了次优传输的首个解析描述，并展示了平均场方法如何可以扩展到基态分析之外。

章节摘要

SubOT模型以及统计力学与最大熵之间的关系

SubOT模型通过在二分网络上最大化香农熵并施加边际约束，来定义质量构型上的概率分布。该框架通过强度向量（??,??）施加质量守恒，确保每个节点的总质量守恒：

∑?????????=????，∑?????????=????

这些约束定义了一个随机加权二分图的系综，其中每个???????代表连接一层中节点??与另一层中节点??的链路上的质量。成本矩阵???????

均匀成本分布情况下的平均场分析

在本节中，我们通过两个步骤发展解析处理。首先，我们用单一全局质量约束替换完整的节点级约束集，在大系统平均场极限下获得闭式解。然后，我们恢复两层的局部约束，并证明当先取热力学极限时，相关的局部涨落仅贡献次广延量，因此不改变主导阶自由能。简化后的模型因此提供了

系综中的权重分布以及大??状态下的分析

SubOT模型提供了一个框架，将可观测的权重模式与底层优化约束联系起来。值得注意的是，驱动这些模式的成本结构可能是未知或不确定的。然而，权重分布????(??)和成本分布????(??)是内在关联的：成本分布的特性直接表现为权重统计中的可观测特征。在本节中我们证明，对于短尾成本分布，权重分布

结论

在本文中，我们从统计力学的角度研究了次优传输问题，发展了一个解析框架来理解SubOT模型的宏观行为。我们的主要目标是超越纯粹的数值观测，推导一个可处理的理论描述，能够解释作为耦合参数??函数的稠密到稀疏结构转变。

我们从通过松弛研究一个简化模型开始……

CRediT作者贡献声明

Riccardo Piombo：写作—审阅与编辑，写作—原始草稿，方法论，形式化分析。
Lorenzo Buffa：写作—审阅与编辑，软件，方法论，数据管理。
Dario Mazzilli：写作—审阅与编辑，写作—原始草稿，方法论。
Aurelio Patelli：写作—审阅与编辑，写作—原始草稿，监督，方法论，形式化分析，概念化。

利益冲突声明

作者声明他们没有已知的竞争性财务利益或个人关系可能影响本论文所报告的工作。

致谢

D.M.、A.P.和R.P.感谢意大利大学与研究部（MUR）于2022年2月2日发布的第104号招标公告下的国家复苏与韧性计划（NRRP）第4任务、第2分量的投资1.1项所提供的财政支持，由欧盟—NextGenerationEU资助——项目名称"WECARE – WEaving Complexity And the gReen Economy"——CUP 20223W2JKJ，由意大利大学与研究部（MUR）提供。

Riccardo Piombo | Lorenzo Buffa | Dario Mazzilli | Aurelio Patelli
恩里科·费米研究中心 - CREF，Via Panisperna 89号，罗马，00184号，意大利