@Article{CSIAM-AM-4-4,
author = {Wu, Tianhao and Qihao, Cheng and Zihao, Wang and Zhang, Chaorui and Bo, Bai and Zhongyi, Huang and Wu, Hao},
title = {The Double Regularization Method for Capacity Constrained Optimal Transport},
journal = {CSIAM Transactions on Applied Mathematics},
year = {2023},
volume = {4},
number = {4},
pages = {776--796},
abstract = {<p style="text-align: justify;">Capacity constrained optimal transport is a variant of optimal transport,
which adds extra constraints on the set of feasible couplings in the original optimal
transport problem to limit the mass transported between each pair of source and sink.
Based on this setting, constrained optimal transport has numerous applications, e.g.,
finance, network flow. However, due to the large number of constraints in this problem, existing algorithms are both time-consuming and space-consuming. In this paper, inspired by entropic regularization for the classical optimal transport problem,
we introduce a novel regularization term for capacity constrained optimal transport.
The regularized problem naturally satisfies the capacity constraints and consequently
makes it possible to analyze the duality. Unlike the matrix-vector multiplication in
the alternate iteration scheme for solving classical optimal transport, in our algorithm,
each alternate iteration step is to solve several single-variable equations. Fortunately,
we find that each of these equations corresponds to a single-variable monotonic function, and we convert solving these equations into finding the unique zero point of
each single-variable monotonic function with Newton’s method. Theoretical analysis
further provides a convergence guarantee to our algorithm. Extensive numerical experiments demonstrate that our proposed method has a significant advantage in terms
of accuracy, efficiency, and memory consumption compared with existing methods.</p>},
issn = {2708-0579},
doi = {https://doi.org/10.4208/csiam-am.SO-2022-0044},
url = {https://global-sci.com/article/82306/the-double-regularization-method-for-capacity-constrained-optimal-transport}
}