The Double Regularization Method for Capacity Constrained Optimal Transport (CSIAM Transactions on Applied Mathematics, 2023)
Capacity constrained optimal transport is a variant of optimal transport,which adds extra constraints on the set of feasible couplings in the original optimaltransport 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 consequentlymakes it possible to analyze the duality. Unlike the matrix-vector multiplication inthe 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 ofeach single-variable monotonic function with Newton’s method. Theoretical analysisfurther provides a convergence guarantee to our algorithm. Extensive numerical experiments demonstrate that our proposed method has a significant advantage in termsof accuracy, efficiency, and memory consumption compared with existing methods.
Keywords: Capacity constraint; optimal transport; regularization; Sinkhorn algorithm.