Geometry of Kantorovich polytopes and support of optimizers for repulsive multi-marginal optimal transport on finite state spaces

DOI10.1016/J.JMAA.2021.125147zbMATH Open1466.49044arXiv1901.04568OpenAlexW3137286444MaRDI QIDQ2033155FDOQ2033155

Authors: Daniela Vögler 

Publication date: 14 June 2021

Published in: Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Abstract: We consider symmetric multi-marginal Kantorovich optimal transport problems on finite state spaces with uniform-marginal constraint. These problems consist of minimizing a linear objective function over a high-dimensional polytope, here referred to as Kantorovich polytope. The presented results are of split nature, computational and theoretical. Within the computational part only small numbers of marginals $N$ and marginal sites $ell$ are considered. This restriction allows us to computationally determine all extreme points of the Kantorovich polytope and investigate how many of them are in compliance with the in optimal transport typical Monge ansatz. Singling out the results for $ell=3$ discretization points and pairwise symmetric cost functions enables us to visually compare Kantorovich's to Monge's ansatz space for a varying number of marginals. Finally we present a necessary support-condition for optimizers which is inspired by the insights the said model problem on three sites provided. This result is not limited to the case of $ell=3$ sites and applies to symmetric pair-costs whose diagonal entries lie above a cost-specific threshold. In case $N$ and $ell$ display certain relationships the discussed condition provides an optimizer in Monge-form and implies its uniqueness as a solution of the considered Kantorovich optimal transport problem.

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

Recommendations

• Breaking the Curse of Dimension in Multi-Marginal Kantorovich Optimal Transport on Finite State Spaces
• Problèmes de transport multi-marginal de Monge-Kantorovich : une caractérisation des solutions
• Solutions to multi-marginal optimal transport problems concentrated on several graphs
• Multi-marginal optimal transport on the Heisenberg group
• Equality between Monge and Kantorovich multimarginal problems with Coulomb cost

zbMATH Keywords

optimal transportdensity functional theory\(N\)-representabilityBirkhoff-von Neumann theoremMonge's ansatzsupport-condition for optimizers

Mathematics Subject Classification ID

Optimal transportation (49Q22)

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
• Title not available (Why is that?)
• Optimal maps for the multidimensional Monge-Kantorovich problem
• Title not available (Why is that?)
• 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?)
• Title not available (Why is that?)
• Density functional theory and optimal transportation with Coulomb cost
• On the local structure of optimal measures in the multi-marginal optimal transportation problem
• 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
• Counterexamples in multimarginal optimal transport with Coulomb cost and spherically symmetric data
• Breaking the Curse of Dimension in Multi-Marginal Kantorovich Optimal Transport on Finite State Spaces
• Semidefinite relaxation of multimarginal optimal transport for strictly correlated electrons in second quantization
• Convex relaxation approaches for strictly correlated density functional theory

Cited In (3)

• Hausdorff distances between couplings and optimal transportation
• Breaking the Curse of Dimension in Multi-Marginal Kantorovich Optimal Transport on Finite State Spaces
• A simple counterexample to the Monge ansatz in multimarginal optimal transport, convex geometry of the set of Kantorovich plans, and the Frenkel-Kontorova model

Uses Software

• Matlab

This page was built for publication: Geometry of Kantorovich polytopes and support of optimizers for repulsive multi-marginal optimal transport on finite state spaces

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