We introduce a simple, accurate, and extremely efficient method fornumerically solving the multi-marginal optimal transport (MMOT) problems . The method relies on (i) the sparsity ofoptimal plans [for $N$ marginals discretized by $\ell$ gridpoints each] and ideas from machine learning . The well-known bottleneck in CGconsists in generating new candidate columns efficiently; we prove that in ourcontext, finding the best new column is an NP-complete problem . To overcomethis bottleneck we use a genetic learning method tailormade for MMOT in which the dual state within CG plays the role of an “adversary”, in loose similarityto Wasserstein GANs . On a sequence of benchmark problems with up to 120gridpoints and up to 30 marginals, our method always found the exactoptimizers. The number of computational steps appears to scale only polynomially

Author(s) : Gero Friesecke, Andreas S. Schulz, Daniela Vögler

Links : PDF - Abstract

Code :