2025-11-10T02:45:53.697948

Optimal transport paths with capacity induced cost function

Xia, Sun

This article generalizes the study of ramified optimal transport with capacity constraint in transport multi-paths by generalizing the $\mathbf{M}_Î±$ cost to $\mathbf{M}_{Î±,c}$, which incorporates capacity constraints into the cost function. Equipped with $\mathbf{M}_{Î±,c}$ cost, we prove the existence of optimal transport path, $\mathbf{M}_{Î±,c}$ related inequalities, decomposition of any general transport paths, and occurrence of direct line segments in an optimal transport path.

academic

Optimal transport paths with capacity induced cost function

基本信息

论文ID: 2510.10557
标题: Optimal transport paths with capacity induced cost function
作者: Haotian Sun, Qinglan Xia
分类: math.OC (Optimization and Control)
发表时间: 2025年10月12日
论文链接: https://arxiv.org/abs/2510.10557v1

摘要

本文通过将 $M_α$ 成本推广为 $M_{α,c}$ 来推广对具有容量约束的分支最优传输的研究，该成本将容量约束纳入成本函数中。配备 $M_{α,c}$ 成本，我们证明了最优传输路径的存在性、 $M_{α,c}$ 相关不等式、任意一般传输路径的分解，以及最优传输路径中直线段的出现。

研究背景与动机

问题背景

该研究要解决的核心问题是分支最优传输中的容量约束问题。传统的Monge-Kantorovich传输问题使用传输映射和传输计划来刻画测度之间的传输，其总成本独立于连接源点和目标点的实际"路径"。

研究动机

现有方法的局限性：在先前的工作11中，作者使用"多路径"来处理容量约束的传输问题，但这种方法存在收敛性问题，如文中Example 1.2所示，满足 $θ(x) ≤ c$ 条件的传输路径无法保证收敛。
多路径方法的缺陷：尽管多路径方法解决了收敛问题，但仍存在缺陷。如Remark 1.3和Figure 3所示，存在可容许的传输路径，其每条边上的权重小于等于c，且其边界等于多路径边界的和，但其 $M_α$ 成本小于等于多路径的 $M_α$ 成本。
方法创新的必要性：需要更新容量约束分支传输问题的刻画方法，使得可容许传输路径的集合相比多路径"扩展"，同时仍在某种意义上"包含" $θ(x) ≤ c$ 条件。

核心贡献

提出了新的成本函数 $M_{α,c}$ ：将传统的 $M_α$ 成本推广为 $M_{α,c}$ 成本，将容量约束直接纳入成本函数中
证明了最优传输路径的存在性：在新的成本函数下建立了最优传输路径存在性定理
建立了 $M_{α,c}$ 相关不等式：包括次可加性、单调性等重要性质
提供了传输路径的分解理论：证明了任意传输路径可以分解为权重等于容量整数倍的路径和权重小于容量的路径之和
分析了最优路径中直线段的出现：证明了在最优传输路径中，权重等于容量整数倍的部分往往通过直线段进行传输

方法详解

任务定义

给定两个等质量的Radon测度 $μ^-$ 和 $μ^+$ ，支撑在 $\mathbb{R}^m$ 中的紧集上，参数 $α ∈ [0,1]$ 和容量约束 $c > 0$ ，寻找最小化 $M_{α,c}$ 成本的传输路径 $T ∈ \text{Path}(μ^-, μ^+)$ 。

核心成本函数设计

对于任意 $T = τ(M, θ(x), ξ(x)) ∈ \text{Path}(μ^-, μ^+)$ ，新的传输成本定义为：

$M_{α,c}(T) := c^α \cdot \int_M \left\lfloor \frac{θ(x)}{c} \right\rfloor + \left(\frac{θ(x)}{c} - \left\lfloor \frac{θ(x)}{c} \right\rfloor\right)^α dH^1$

其中 $\lfloor θ(x)/c \rfloor$ 表示不超过 $θ(x)/c$ 的最大整数。

成本函数的关键性质

1. 边界行为

当 $c → ∞$ 时： $\lim_{c→∞} M_{α,c}(T) = M_α(T)$ （回到传统 $M_α$ 成本）
当 $c → 0$ 时：成本主要由整数部分 $c^α \int_M \lfloor θ(x)/c \rfloor dH^1$ 决定

2. 辅助函数性质

定义辅助函数 $H_{c,α}(x) := \lfloor x/c \rfloor + (x/c - \lfloor x/c \rfloor)^α$ ，具有以下性质：

当 $α ∈ (0,1]$ 时， $H_{c,α}(x)$ 严格递增、凹函数且连续
当 $α = 0$ 时， $H_{c,α}(x)$ 递增、分段常数，在整数点有跳跃不连续性
次可加性： $H_{c,α}(x_1 + x_2) ≤ H_{c,α}(x_1) + H_{c,α}(x_2)$

技术创新点

1. 容量约束的隐式处理

与显式约束 $θ(x) ≤ c$ 不同，新方法通过成本函数隐式处理容量约束，避免了收敛性问题。

2. 整数-分数分解思想

成本函数中的 $\lfloor θ(x)/c \rfloor$ 项表示"总"权重在每点被细分为若干组件，每个组件权重不超过 $c$ 。

3. 与多路径方法的兼容性

Proposition 3.6证明了对于多路径 $\vec{T} ∈ \text{Path}_c(μ^-, μ^+)$ ，有 $M_{α,c}(T) ≤ M_α(\vec{T})$ ，其中 $T = \sum_{k=1}^∞ T_k$ 。

理论结果

存在性定理

定理3.4：给定支撑在紧集上的等质量Radon测度 $μ^-, μ^+$ ，对于任意 $α ∈ [0,1]$ 和 $c > 0$ ，存在 $T^* ∈ \text{Path}(μ^-, μ^+)$ 使得 $M_{α,c}(T^*) ≤ M_{α,c}(T)$ 对所有 $T ∈ \text{Path}(μ^-, μ^+)$ 成立。

重要不等式

引理3.3：对于任意可求长1-电流 $T$ ，有 $M(T) ≤ c^{1-α}M_{α,c}(T) ≤ M(T) + c \cdot \text{size}(T)$

命题3.5：对于 $h ∈ \mathbb{R}$ ，有

当 $0 ≤ h ≤ 1$ 时： $M_{α,c}(hT) ≤ h^α M_{α,c}(T)$
当 $h ≥ 1$ 时： $h^α M_{α,c}(T) ≤ M_{α,c}(hT)$

路径分解定理

定理4.3：给定传输路径 $T$ 和其上的任意环 $R$ ，若满足条件 $\max_{x∈N} \left(\frac{θ(x)}{c} - \left\lfloor \frac{θ(x)}{c} \right\rfloor\right) + \min_{x∈N} \left(\frac{θ(x)}{c} - \left\lfloor \frac{θ(x)}{c} \right\rfloor\right) ≤ 1$ 则可找到无环传输路径 $T_1, T_2$ 使得：