Year: 2023
Author: Tianhao Wu, Qihao Cheng, Zihao Wang, Chaorui Zhang, Bo Bai, Zhongyi Huang, Hao Wu
CSIAM Transactions on Applied Mathematics, Vol. 4 (2023), Iss. 4 : pp. 776–796
Abstract
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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/csiam-am.SO-2022-0044
CSIAM Transactions on Applied Mathematics, Vol. 4 (2023), Iss. 4 : pp. 776–796
Published online: 2023-01
AMS Subject Headings: Global Science Press
Copyright: COPYRIGHT: © Global Science Press
Pages: 21
Keywords: Capacity constraint optimal transport regularization Sinkhorn algorithm.