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

DOI10.1016/J.JMAA.2021.125147MaRDI QIDQ2033155zbMATH OpenOpenAlexFDO

Authors Daniela Vögler

Publication date 14 June 2021

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Optimal transportation (49Q22)

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.

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

Cites work

• scientific article; zbMATH DE number 1266748 (Why is no real title available?)
• scientific article; zbMATH DE number 2066995 (Why is no real title available?)
• scientific article; zbMATH DE number 1894374 (Why is no real title available?)
• scientific article; zbMATH DE number 3078983 (Why is no real title available?)
• scientific article; zbMATH DE number 3095897 (Why is no real title available?)
• A stochastic control approach to no-arbitrage bounds given marginals, with an application to lookback options
• Barycenters in the Wasserstein space
• Breaking the Curse of Dimension in Multi-Marginal Kantorovich Optimal Transport on Finite State Spaces
• Combinatorial properties of noninteger vertices of a polytope in a three-index axial assignment problem
• Convex optimization theory.
• Convex relaxation approaches for strictly correlated density functional theory
• Counterexamples in multimarginal optimal transport with Coulomb cost and spherically symmetric data
• Density functional theory and optimal transportation with Coulomb cost
• Hedonic price equilibria, stable matching, and optimal transport: Equivalence, topology, and uniqueness
• Infinite-body optimal transport with Coulomb cost
• Matching for teams
• Model-independent bounds for option prices -- a mass transport approach
• Monge problem for \(n\) probabilities
• Multidimensional stochastic matrices and patterns
• Multimarginal Optimal Transport Maps for One–dimensional Repulsive Costs
• Nonexistence of optimal transport maps for the multimarginal repulsive harmonic cost
• Notions of convexity
• On the local structure of optimal measures in the multi-marginal optimal transportation problem
• On the vertices of the \(d\)-dimensional Birkhoff polytope
• Optimal Transport
• Optimal maps for the multidimensional Monge-Kantorovich problem
• Optimal transportation for the determinant
• Optimal transportation theory with repulsive costs
• Remarks on the semi-classical Hohenberg-Kohn functional
• Semidefinite relaxation of multimarginal optimal transport for strictly correlated electrons in second quantization
• Solutions to multi-marginal optimal transport problems concentrated on several graphs
• Uniqueness and Monge solutions in the multimarginal optimal transportation problem

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

Describes a project that uses

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)