A simple counterexample to the Monge ansatz in multimarginal optimal transport, convex geometry of the set of Kantorovich plans, and the Frenkel-Kontorova model

DOI10.1137/18M1207326zbMATH Open1429.49048arXiv1808.04318WikidataQ124815394 ScholiaQ124815394MaRDI QIDQ5243245FDOQ5243245

Authors: Gero Friesecke 

Publication date: 18 November 2019

Published in: SIAM Journal on Mathematical Analysis (Search for Journal in Brave)

Abstract: It is known from clever mathematical examples cite{Ca10} that the Monge ansatz may fail in continuous two-marginal optimal transport (alias optimal coupling alias optimal assignment) problems. Here we show that this effect already occurs for finite assignment problems with $N=3$ marginals, $ell=3$ 'sites', and symmetric pairwise costs, with the values for $N$ and $ell$ both being optimal. Our counterexample is a transparent consequence of the convex geometry of the set of symmetric Kantorovich plans for $N=ell=3$, which -- as we show -- possess 22 extreme points, only 7 of which are Monge. These extreme points have a simple physical meaning as irreducible molecular packings, and the example corresponds to finding the minimum energy packing for Frenkel-Kontorova interactions. Our finite example naturally gives rise, by superposition, to a continuous one, where failure of the Monge ansatz manifests itself as nonattainment and formation of 'microstructure'.

Full work available at URL: https://arxiv.org/abs/1808.04318

Recommendations

• Counterexamples in multimarginal optimal transport with Coulomb cost and spherically symmetric data
• Geometry of Kantorovich polytopes and support of optimizers for repulsive multi-marginal optimal transport on finite state spaces
• Equality between Monge and Kantorovich multimarginal problems with Coulomb cost
• Breaking the Curse of Dimension in Multi-Marginal Kantorovich Optimal Transport on Finite State Spaces
• The geometry of optimal transportation

zbMATH Keywords

optimal transportBirkhoff polytopeextreme pointFrenkel-Kontorova modelmulti-index assignment problemnonattainment

Mathematics Subject Classification ID

Variational problems in a geometric measure-theoretic setting (49Q20) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Variational inequalities (49J40) Optimality conditions for solutions belonging to restricted classes (Lipschitz controls, bang-bang controls, etc.) (49K30)

Cites Work

• Barycenters in the Wasserstein space
• Optimal Transport
• Convex optimization theory.
• Title not available (Why is that?)
• On the vertices of the \(d\)-dimensional Birkhoff polytope
• Monge problem for \(n\) probabilities
• Remarks on the semi-classical Hohenberg-Kohn functional
• Uniqueness and Monge solutions in the multimarginal optimal transportation problem
• Optimal transportation for the determinant
• Optimal maps for the multidimensional Monge-Kantorovich problem
• Title not available (Why is that?)
• Symmetric Monge-Kantorovich problems and polar decompositions of vector fields
• Multimarginal Optimal Transport Maps for One–dimensional Repulsive Costs
• Hedonic price equilibria, stable matching, and optimal transport: Equivalence, topology, and uniqueness
• A stochastic control approach to no-arbitrage bounds given marginals, with an application to lookback options
• Model-independent bounds for option prices -- a mass transport approach
• Notions of convexity
• Title not available (Why is that?)
• Optimal transport with proximal splitting
• Regularized discrete optimal transport
• Density functional theory and optimal transportation with Coulomb cost
• Matching for teams
• Solutions to multi-marginal optimal transport problems concentrated on several graphs
• Infinite-body optimal transport with Coulomb cost
• Multidimensional stochastic matrices and patterns
• Nonexistence of optimal transport maps for the multimarginal repulsive harmonic cost
• Combinatorial properties of noninteger vertices of a polytope in a three-index axial assignment problem
• Optimal transportation theory with repulsive costs
• Breaking the Curse of Dimension in Multi-Marginal Kantorovich Optimal Transport on Finite State Spaces

Cited In (8)

• Multi-marginal optimal transportation problem for cyclic costs
• A general framework for multi-marginal optimal transport
• Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems
• The GenCol Algorithm for High-Dimensional Optimal Transport: General Formulation and Application to Barycenters and Wasserstein Splines
• Universal diagonal estimates for minimizers of the Levy-Lieb functional
• Breaking the Curse of Dimension in Multi-Marginal Kantorovich Optimal Transport on Finite State Spaces
• A quantitative rigidity result for a two-dimensional Frenkel-Kontorova model
• Applications of optimal transportation in the natural sciences. Abstracts from the workshop held February 21--27, 2021 (online meeting)

This page was built for publication: A simple counterexample to the Monge ansatz in multimarginal optimal transport, convex geometry of the set of Kantorovich plans, and the Frenkel-Kontorova model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5243245)