GENETIC COLUMN GENERATION: FAST COMPUTATION OF HIGH-DIMENSIONAL MULTIMARGINAL OPTIMAL TRANSPORT PROBLEMS

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We introduce a simple, accurate, and extremely efficient method for numerically solving multimarginal optimal transport (MMOT) problems arising in density functional theory. The method relies on (i) the sparsity of optimal plans (for N marginals discretized by ζ gridpoints each, general Kantorovich plans require ζ N gridpoints, but the support of optimizers is of size O(ζ . N) [G. Friesecke and D. Vögler, SIAM J. Math. Anal., 50 (2018), pp. 3996-4019], (ii) the method of column generation (CG) from discrete optimization which is novel in the optimal transport context, and (iii) ideas from machine learning. The well-known bottleneck in CG consists in generating new candidate columns efficiently; we prove that in our context, finding the best new column is an NP-complete problem. To overcome this bottleneck we use a genetic learning method tailor-made for MMOT in which the dual state within CG plays the role of an ``adversary" in loose similarity to Wasserstein generative adversarial networks (GANs). On a sequence of benchmark problems with up to 120 gridpoints and up to 30 marginals, our method always finds the exact optimizers. Moreover, empirically the number of computational steps needed to find them appears to scale only polynomially when both N and ζ are simultaneously increased (while keeping their ratio fixed to mimic a thermodynamic limit of the particle system).

Original languageEnglish
Pages (from-to)A1632-A1654
JournalSIAM Journal on Scientific Computing
Volume44
Issue number3
DOIs
StatePublished - 2022

Keywords

  • column generation
  • genetic algorithm
  • high dimension
  • optimal transport

Fingerprint

Dive into the research topics of 'GENETIC COLUMN GENERATION: FAST COMPUTATION OF HIGH-DIMENSIONAL MULTIMARGINAL OPTIMAL TRANSPORT PROBLEMS'. Together they form a unique fingerprint.

Cite this