🔢 mathematics

Convex Relaxations for the Optimization of Markov Processes

本文通过将优化给定分布之间的马尔可夫过程的问题重构为序列耦合问题，并开发基于局部边际分布和簇矩的凸松弛方法，以提供可计算的界限并恢复低阶统计量，从而解决在优化此类过程时面临的维度灾难问题，其应用范围包括动态最优传输和伊辛模型。

原作者： Hongyi Zhang, Yuehaw Khoo, Tianyun Tang

发布于 2026-07-13

📖 1 分钟阅读🧠 深度阅读

原作者： Hongyi Zhang, Yuehaw Khoo, Tianyun Tang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图引导一团巨大的、不可见的云团从一种形状变成另一种形状。也许它最初是一个完美的球体，而你需要把它变成一个扭曲的椒盐卷饼。但问题在于，你不能通过挥挥手指就瞬间改变形状。你必须一步一个脚印，在特定的时间段内，一个粒子接一个粒子地移动这些气体。而且，你希望以最节能的方式完成这项任务。

这就是作者们正在解决的问题。他们称之为“优化马尔可夫过程”（optimizing Markov processes），但我们可以称之为**“伟大的云团塑形挑战”**。

大问题：粒子太多，脑力不够

主要的障碍是数学家们所说的“维度诅咒”。想象一下，你的云团不仅仅存在于三维空间，而是存在于 50 个维度（甚至更多）中。要追踪每一个粒子并精确知道每一个粒子相对于其他每一个粒子的位置，你需要写下一份极其庞大的数字清单，规模大到世界上任何计算机都无法承载。这就像试图同时记住地球上每一片沙滩上每一粒沙子的位置一样。

论文指出，试图通过追踪整个云团来解决这个问题是一个死胡同。相反，作者们提出了一个聪明的技巧：不要盯着整个云团看；只需观察它们的邻里关系。

解决方案：邻里观察

与其试图绘制整个宇宙的地图，作者建议将云团分解成小而易于管理的集群。把它想象成一座城市。你不需要了解整个国家的交通流量才能理解某个特定街区的移动情况。你只需要知道你所在的街区的人是如何移动的，以及他们如何与相邻的下一个街区进行互动。

作者们开发了一种称为凸松弛（convex relaxation）的方法。用通俗的话说，这意味着他们把一个超级困难、混乱的谜题变成了一个更平滑、更容易解决的谜题，从而给出一个“最佳猜测”答案。

运作方式： 他们只追踪“局部边缘分布”（local marginals）。这是一种高级说法，意思是指他们只追踪小群粒子的统计数据（比如一对邻居或一个小集群），而不是整个人群。
结果： 他们得到了一个“下界”（lower bound）。想象一下，你正在尝试寻找穿过迷宫的最短路径。你看不见整个迷宫，所以你计算出你可能行驶的最短绝对距离。你可能还没有找到确切的路径，但你知道你不可能比这个数值做得更好。论文表明，他们的方法为移动云团的成本提供了一个非常紧凑且可计算的下界。

特殊情况：“贝南姆-布里耶”高速公路

论文重点介绍了一个被称为动态最优传输（Dynamic Optimal Transport）的特殊版本问题。这就像一条超级高速公路，云团根据物理定律（特别是流体力学）进行移动。

发现： 作者证明了，如果你将这种方法应用于这类特定问题，你得到的不仅仅是一个下界；你实际上恢复了精确的“速度场”。你可以把它想象成一张风图，它告诉你在每个点上空气应该以多快的速度和什么方向吹动，才能让云团从形状 A 变为形状 B。
信心来源： 他们不仅仅是靠直觉猜测，而是通过数学证明，当你在网格点上观察时，他们这种离散的、分步的方法可以恢复出与著名的连续物理公式（贝南姆-布里耶公式）完全相同的结果。

“拟合”技巧：从统计学到电影

真正酷的部分在这里。数学能给出云团在每一步的统计数据（例如“这个角落里 50% 的粒子正在向左移动”），但它不会给你一部粒子移动的电影。这就像你有一张人群的照片，但不知道每个人具体在往哪里走。

为了解决这个问题，他们开发了一种核函数拟合程序（kernel-fitting procedure）。

类比： 想象你有一张模糊的舞池照片。你知道舞者的平均位置。现在，你想找到一个特定的舞蹈动作（一个“核函数”），如果把这个动作教给一个机器人，它就能模仿这张模糊的照片。
应用： 他们在 Ising 模型上测试了这一点，Ising 模型就像是微型磁铁（自旋）的网格，它们可以指向向上或向下。他们想要将一个磁铁网格从一种状态（所有磁铁都喜欢对齐，即铁磁态）移动到另一种状态（磁铁喜欢交替排列，即反铁磁态）。
结果： 他们利用数学得到了“模糊的照片”（局部统计数据），然后“拟合”了一种特定类型的磁更新规则（称为 Glauber 动力学）。在他们的模拟中，那个“机器人舞蹈”（拟合后的 Glauber 动力学）几乎完美地匹配了那张模糊的照片。

他们没做什么（以及他们排除了什么）

了解这篇论文没有声称什么非常重要：

并非魔法： 他们并不声称能为所有可能出现的情况瞬间解决问题。他们特别关注那些相互作用是“局部”的（邻居影响邻居）且稀疏的情况。如果每个粒子都以复杂且密集的方式影响每一个其他粒子，他们的方法仍然会面临困难。
并非对一切都“奏效”： 他们并没有说他们的方法在所有情况下都优于其他方法。例如，他们将自己的方法与一种“基于粒子的反向传播”方法（类似于训练神经网络来猜测路径）进行了比较。在他们针对 15 维度的特定测试中，他们的方法在预测云团形状方面比粒子法更快且更准确。但他们将其呈现为一个具体的实验结果，而非普遍规律。
没有“未来”保证： 他们并未声称这会立即治愈疾病或建造新引擎。他们明确指出，将此扩展到更广泛的受控动力学类别仍是一个“开放的研究方向”。他们是在打基础，而不是在完工。

数据与证明

实验： 他们运行了维度高达 50 的模拟。
时间步长： 他们在进行高斯测试时使用了 10 个时间步长的网格，在进行 Ginzburg–Landau 测试时使用了 5 个时间步长。
Ising 模型： 他们在 1D（一维）链条（30 个自旋）和 2D（二维）网格（4x4，即 16 个自旋）上进行了测试。
速度： 在一项测试中，他们的算法在约 99.55 秒（对于静态参考）和 539.09 秒（对于动态版本）内解决了问题，这明显快于他们对比的基于粒子的训练方法。

核心结论

作者构建了一套新的工具，让我们能够通过忽略“追踪一切”这一不可能的任务，转而专注于局部邻里关系，从而穿越“维度诅咒”。他们证明了对于某些物理问题，这种捷径能给出正确的答案。对于其他复杂的系统（如磁性自旋），它提供了一个非常好的下界，并提供了一种重建模型的方法，使其能够模拟出相应的行为。

他们并没有解决整个宇宙，但他们找到了一种非常聪明的方法，可以在不需要像行星一样大的超级计算机的情况下，解决其中巨大的一块。

技术摘要：马尔可夫过程优化的凸松弛方法

问题陈述
本文研究了在给定状态空间 $\Omega$ 上，在两个预设概率分布 $\mu$ 和 $\nu$ 之间进行插值的马尔可夫过程优化问题，旨在最小化累积成本。该过程由一系列中间律 $\{\rho_s\}_{s=0}^T$ 和马尔可夫转移核 $\{K_s\}_{s=0}^{T-1}$ 定义。目标是最小化单步成本之和：
$\inf \sum_{s=0}^{T-1} \int_{\Omega} \int_{\Omega} c_s(x, y) K_s(x, dy) d\rho_s(x)$
受限于初始和终止约束（ $\rho_0 = \mu, \rho_T = \nu$ ）以及马尔可夫演化约束（ $\rho_{s+1} = (K_s)_* \rho_s$ ）。

主要的计算挑战在于维度灾难。在高维状态空间中，表示连续状态的完整联合分布（耦合 $\pi_s$ ）是不可行的。本文重点讨论了当可容许的转移核满足特定约束（例如支持集约束、局部更新规则）且成本函数具有局部分解性质时的情形。

方法论
作者提出了一个基于序列耦合表述和凸松弛的框架，该框架利用了局部性和稀疏交互结构。

序列耦合重构：
问题从优化转移核转变为优化一系列联合耦合 $\pi_s(dx, dy) = \rho_s(dx)K_s(x, dy)$ 。约束条件被重写为这些耦合的边缘分布形式。中间分布被吸收进耦合中，其中 $\rho_{s+1}$ 是 $\pi_s$ 的右边缘，同时也是 $\pi_{s+1}$ 的左边缘。
凸松弛：
为了避免表示完整的耦合 $\pi_s$ ，作者开发了两种仅保留低阶局部信息的凸松弛方法：
- 边缘松弛（Marginal Relaxation）： 将完整耦合替换为其在由簇图 $\mathcal{G} = (\mathcal{C}, \mathcal{E})$ $G = (C, E)$ 定义的一组坐标簇 $\mathcal{C}$ $C$ 及簇对上的局部边缘分布。该松弛强制执行：
  - 簇边缘分布与簇对边缘分布之间的一致性。
  - 跨时间步的质量守恒（投影到保留的簇对上）。
  - 局部正定性与全局正定性约束（后者确保局部边缘分布可以扩展为全局非负测度，通常通过对类矩矩阵施加正定（PSD）约束来实现）。
  - 投影到局部边缘分布上的容许性约束。
- 簇矩松弛（Cluster Moment Relaxation）： 该方法不使用完整的边缘分布，而是使用针对簇上预设基函数（如单项式）的有限组矩。这适用于连续状态空间。决策变量是矩矩阵。约束包括矩一致性、质量守恒以及全局正定性（对组合后的矩矩阵施加 PSD 约束）。
这两种框架都产生了凸优化问题（对于具有仿射约束的有限状态，为线性规划；对于连续状态或一般约束，为半正定规划 (SDP)）。这些方法提供了原问题的可计算下界，并能恢复中间分布的低阶统计量。
动力学恢复：
- 动态最优传输（Benamou–Brenier）： 当状态空间是凸的、成本为动能型（ $\|x-y\|^2$ ）且不存在核约束时，该问题回归为 Benamou–Brenier 测地线。作者表明，松弛问题的对偶变量近似于 Benameli–Brenier 的对偶势函数。通过对这些势函数求导，可以恢复近似的速度场，从而诱导出一个流（flow）及相应的马尔可夫核。
- 一般约束过程： 对于一般的约束（例如 Ising 模型的单自旋更新），该方法将参数化族的核（例如 Glauber 动力学）拟合到恢复的局部统计量上。具体做法是通过最小化预测的下一步边缘分布（通过参数化核）与从松弛中恢复的边缘分布之间的平方误差来进行。

核心贡献

表述： 本文将马尔可夫过程优化重新构建为序列耦合表述，并提出了一种通过利用稀疏局部信息（边缘分布或矩）而非完整联合分布来应对高维问题的凸松弛框架。
动态最优传输的联系： 它证明了动态最优传输是该框架的一个特例。至关重要的是，它提供了一种从松弛解的对偶变量中恢复底层 Benamou–Brenier 速度场的程序，弥合了静态松弛与动态流之间的鸿沟。
约束动力学的泛化： 该框架超越了无约束传输，能够处理带有硬约束的一般马尔可夫过程。作者通过将恢复的局部统计量拟合到 Glauber 动力学中，展示了如何在 Ising 模型之间的传输中实现这一过程，从而将恢复的局部统计量转化为可实现的马尔可夫核。

结果
论文通过数值实验验证了该方法：

高斯传输： 在 50 维高斯设置下，矩松弛准确地恢复了中间均值、协方差和仿射速度场。该方法表现出极高的计算效率（通过 SDP 在数秒内求解），并且在轨迹沿线的协方差误差方面比基于粒子的反向传播方法更精确。
Ginzburg–Landau 传输： 该方法成功实现了从高斯分布到 10 维非高斯 Ginzburg–Landau 分布的传输。通过从恢复的矩中进行最大熵重构，捕捉到了分布的逐渐变形过程，包括局部和长程相关性。
Ising 模型： 该方法处理了铁磁与反铁磁 Ising 模型（1D 和 2D）之间的约束传输。边缘松弛（作为 LP 求解）恢复了局部自旋边缘分布，随后将其用于拟合非齐次时间 Glauber 动力学。拟合的动力学成功重现了恢复的边缘分布，并生成了有效的样本轨迹。

意义与主张
论文声称其框架通过避免指数级的全状态表示成本，为高维马尔可夫过程优化提供了一种可行的替代方案。它提供了：

可计算的下界： 松弛法提供了原最优成本的严格下界。
可恢复的统计量： 该方法可以恢复中间律的低阶统计量（均值、协方差、矩）。
动力学重构： 与静态传输方法不同，该框架允许从松弛解中重构底层动力学（速度场或转移核）。
通用性： 它将动态最优传输和约束随机控制（如 Glauber 动力学）统一在一个单一的凸优化框架之下，适用于离散和连续状态空间。

作者谦虚地指出，虽然该方法可以恢复局部统计量和近似动力学，但中间分布中局部性的精确保持仍是一个开放的理论问题，且该框架目前仅限于特定类型的约束和成本结构。