返回学习路线

最优输运单元验收题及解答 ​

任务 ​

给定

$$\mu =\frac{1}{2}{\delta }_0+\frac{1}{2}{\delta }_2,\nu =\frac{1}{4}{\delta }_1+\frac{3}{4}{\delta }_3.$$

请用平方距离成本完成线性规划、对偶证书和分位数三种相互核验；判断是否有 Monge 映射；再用相对熵正则化和 Sinkhorn 计算，分别报告边缘残差、原始搬运成本、正则目标及正则化偏差。

原始问题与证书 ​

按源点 $0,2$、目标点 $1,3$ 排列，质量向量为 $a=(1/2,1/2)$、$b=(1/4,3/4)$，成本矩阵为

$$C=\left(\begin{array}{cc}1& 9\\ 1& 1\end{array}\right).$$

完整线性规划为 $\underset{P\ge 0}{min}⟨C,P⟩$，约束 $P\mathbf{1}=a$、$P^T\mathbf{1}=b$。解边缘方程，得到

$$P(s)=\left(\begin{array}{cc}s& 1/2-s\\ 1/4-s& 1/4+s\end{array}\right),0\le s\le 1/4.$$

成本 $5-8s$ 在 $s=1/4$ 达到最小值 $3$，所以

$$P^{\ast }=\left(\begin{array}{cc}1/4& 1/4\\ 0& 1/2\end{array}\right).$$

取对偶势 $\phi =(0,-8)$、$\psi =(1,9)$。其路线势和矩阵为 $\left(\begin{array}{cc}1& 9\\ -7& 1\end{array}\right)\le C$，对偶目标 $a^T\phi +b^T\psi =-4+1/4+27/4=3$。计划和势均可行，原始与对偶值相同，所以构成完整最优性证书。负势不妨碍可行性。

分位数与映射 ​

公共分位数轴在 $1/4,1/2$ 处分成三段，配对依次为 $(0,1)$、$(0,3)$、$(2,3)$，质量为 $1/4,1/4,1/2$。因此

$$W_1=\frac{1}{4}\cdot 1+\frac{1}{4}\cdot 3+\frac{1}{2}\cdot 1=\frac{3}{2},$$$$W_2^2=\frac{1}{4}\cdot 1^2+\frac{1}{4}\cdot 3^2+\frac{1}{2}\cdot 1^2=3,W_2=\sqrt{3}.$$

分位数得到的平方成本与线性规划、对偶证书完全一致。这里不存在确定 Monge 映射：两个源原子各有质量 $1/2$，任何目标区域收到的质量只能为 $0,1/2,1$，无法给目标点 $1$ 恰好 $1/4$。Kantorovich 计划必须拆分源点零的质量。

熵正则化的解析检查 ​

采用目标 $⟨C,P⟩+\epsilon \mathrm{KL}(P\Vert a{b}^T)$。正则计划可写成

$$P_{\epsilon }=\left(\begin{array}{cc}1/4-\eta & 1/4+\eta \\ \eta & 1/2-\eta \end{array}\right),0<\eta <1/4.$$

行列缩放不改变交叉比，因此

$$\frac{(1/4-\eta )(1/2-\eta )}{(1/4+\eta )\eta }=e^{8/\epsilon }.$$

记 $R=e^{8/\epsilon }$、$B=3/4+R/4$，数值稳定的正根形式为

$$\eta =\frac{1/4}{B+\sqrt{B^2+(R-1)/2}}.$$

该公式给出独立于迭代停止规则的核验答案。未正则搬运成本为 $3+8\eta$，所以原始成本偏差恰为 $8\eta$。

Sinkhorn 执行结果 ​

以 $v^{(0)}=(1,1)$，核矩阵 $K_{ij}=e^{-C_{ij}/\epsilon }$，交替更新 $u=a/(Kv)$、$v=b/(K^{T}u)$。每轮后检查两组边缘的 $L^1$ 残差，要求其最大值小于 ${10}^{-12}$。

在 $\epsilon =1$ 时，31 轮后得到下列计划。矩阵为显示而舍入，残差由未舍入结果计算：

$$P_1\approx \left(\begin{array}{cc}0.249832549& 0.250167451\\ 0.000167451& 0.499832549\end{array}\right).$$

行残差约为 $5.58\times {10}^{-13}$，列残差在本次双精度计算中为零。原始搬运成本约为 $3.001339605$，相对于原始最优值的偏差约为 $0.001339605$；包含相对熵的正则目标约为 $3.215593963$。三个目标量不能互换。

同样标准下，$\epsilon =1/2$ 用 38 轮，原始成本偏差约为 $4.50\times {10}^{-7}$；$\epsilon =2$ 用 25 轮，偏差约为 $0.067336985$。这次计算展示了更小正则参数降低偏差，却未必减少轮数。轮数是本例的实际执行结果，不是一般复杂度定理。

通过标准 ​

• 明确写出所有边缘约束，并给出可行参数区间
• 用成本函数和对偶证书分别证明最优值为 $3$
• 分位数扫描得到同一计划，同时区分 $W_2$ 与 $W_2^2$
• 用原子质量论证 Monge 不可行，而非只说映射“比较困难”
• Sinkhorn 同时检查行列误差；保存完整精度结果供复核
• 将正则化偏差与迭代可行性误差分开，并说明所用熵常数约定

本题数值由随附验证脚本实际执行，并用交叉比的解析根交叉检查。理论来源见本单元各篇正文的原始论文与教材链接。