Optimal transport problems regularized by generic convex functions: A geometric and algorithmic approach

2020/11/27 by Tsutsui, Daiji
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2011.13683

Abstract

In order to circumvent the difficulties in solving numerically the discrete optimal transport problem, in which one minimizes the linear target function P↦⟨ C,P⟩:=∑_i,jC_ijP_ij, Cuturi introduced a variant of the problem in which the target function is altered by a convex one Φ(P)=⟨ C,P⟩-λH(P), where H is the Shannon entropy and λ is a positive constant. We herein generalize their formulation to a target function of the form Φ(P)=⟨ C,P⟩+λf(P), where f is a generic strictly convex smooth function. We also propose an iterative method for finding a numerical solution, and clarify that the proposed method is particularly efficient when f(P)=(1)/(2)‖P‖².

Related

• Characterizing and computing solutions to regularized semi-discrete optimal transport via an ordinary differential equation
• Optimal transport: discretization and algorithms
• Algorithms for Euclidean-regularised Optimal Transport
• Relaxation of optimal transport problem via strictly convex functions
• An ordinary differential equation for entropic optimal transport and its linearly constrained variants