We introduce and prove convergence of a damped Newton algorithm to
approximate solutions of the semi-discrete optimal transport problem with
storage fees, corresponding to a problem with hard capacity constraints. This
is a variant of the optimal transport problem arising in queue penalization
problems, and has applications to data clustering. Our result is novel as it is
the first numerical method with proven convergence for this variant problem;
additionally the algorithm applies to the classical semi-discrete optimal
transport problem but does not require any connectedness assumptions on the
support of the source measure, in contrast with existing results. Furthermore
we find some stability results of the associated Laguerre cells. All of our
results come with quantitative rates. We also present some numerical examples.

本文介绍和证明了一种阻尼牛顿算法的收敛性，以近似解决存储费用、硬容量约束下的半离散最优输运问题，并探讨了其在队列罚函数问题、数据聚类等方面的应用，是第一种基于数值方法并具有收敛性的解决该变体问题的算法，同时不需要任何关于源测度支集的连通性假设并提出相关的拉格尔细胞稳定性结果，所有结果均附带定量的速率分析和数值例子。