A Newton algorithm for semi-discrete optimal transport with storage fees and quantitative convergence of cells

We introduce and prove convergence of a damped Newton algorithm to approximate solutions of the semi-discrete optimal transport problem with storage fees, corresponding to a problem with hard capacity constraints. This is a variant of the optimal transport problem arising in queue penalization problems, and has applications to data clustering. Our result is novel as it does not require any connectedness assumptions on the support of the source measure, in contrast with previous results. Furthermore we find some stability results of the associated Laguerre cells. All of our results come with quantitative rates

• Publication year

  2019

• Venue

  SIAM Journal on Optimization

• Publication date

  2019-08-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/20m1357226arXiv 1908.11533
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Quantitative Stability in the Geometry of Semi-discrete Optimal Transport

  2020cited by this paper
• An optimal transport problem with storage fees

  2019influential reference
• Optimal monopoly pricing with congestion and random utility via partial mass transport

  2018cited by this paper
• Computational Optimal Transport

  2018cited by this paper
• An iterative method for generated Jacobian equations

  2017cited by this paper
• An algorithm for optimal transport between a simplex soup and a point cloud

  2017cited by this paper
• An iterative method for generated Jacobian equations

  2017influential reference
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration

  2017cited by this paper
• Optimal transport and a bilevel location-allocation problem

  2017cited by this paper
• Pointwise rates of convergence for the Oliker–Prussner method for the Monge–Ampère equation

  2016cited by this paper
• Convergence of a Newton algorithm for semi-discrete optimal transport

  2016influential reference
• Discretization of the 3D Monge-Ampere operator, between Wide Stencils and Power Diagrams

  2015cited by this paper
• Optimal transport and a bilevel location-allocation problem

  2015cited by this paper
• Convergence of Entropic Schemes for Optimal Transport and Gradient Flows

  2015cited by this paper
• An efficient numerical algorithm for the L2 optimal transport problem with periodic densities

  2015cited by this paper
• Unbalanced optimal transport: Dynamic and Kantorovich formulations

  2015cited by this paper
• Optimal Entropy-Transport problems and a new Hellinger–Kantorovich distance between positive measures

  2015cited by this paper
• Multi-index Mittag-Leffler Functions

  2014cited by this paper
• A Numerical Algorithm for L2 Semi-Discrete Optimal Transport in 3D

  2014cited by this paper
• Sinkhorn Distances: Lightspeed Computation of Optimal Transport

  2013cited by this paper
• An iterative scheme for solving the optimal transportation problem

  2012cited by this paper
• Numerical solution of the Optimal Transportation problem using the Monge-Ampère equation

  2012cited by this paper
• Approximation of convex bodies by inscribed simplices of maximum volume

  2011cited by this paper
• A Multiscale Approach to Optimal Transport

  2011cited by this paper
• Two Numerical Methods for the elliptic Monge-Ampère equation

  2010cited by this paper
• An Interpolating Distance Between Optimal Transport and Fisher–Rao Metrics

  2010cited by this paper
• Fast finite difference solvers for singular solutions of the elliptic Monge-Ampère equation

  2010cited by this paper
• Convergent Finite Difference Solvers for Viscosity Solutions of the Elliptic Monge-Ampère Equation in Dimensions Two and Higher

  2010cited by this paper
• On the regularity of solutions of optimal transportation problems

  2009cited by this paper
• Optimal Transport: Old and New

  2008cited by this paper
• Optimum and equilibrium in a transport problem with queue penalization effect

  2008cited by this paper
• Introduction to Topology

  2008cited by this paper
• Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian

  2008cited by this paper
• Capacitated facility location problem with general setup cost

  2006cited by this paper
• On the second boundary value problem for Monge-Ampère type equations and optimal transportation

  2006cited by this paper
• Regularity of Potential Functions of the Optimal Transportation Problem

  2005cited by this paper
• Numerical Analysis/Partial Differential Equations Numerical solution of the Monge-Ampère equation by a Newton's algorithm

  2005cited by this paper
• On the design of a reflector antenna II

  2004cited by this paper
• On the Numerical Solution of the Problem of Reflector Design with Given Far-Field Scattering Data

  1999cited by this paper
• Minkowski-Type Theorems and Least-Squares Clustering

  1998cited by this paper
• Uniformly convex and uniformly smooth convex functions

  1995cited by this paper
• CONVEX BODIES: THE BRUNN–MINKOWSKI THEORY

  1994cited by this paper
• Digraphs

  1992influential reference
• The regularity of mappings with a convex potential

  1992cited by this paper
• Eigenvalues, diameter, and mean distance in graphs

  1991cited by this paper
• Polar Factorization and Monotone Rearrangement of Vector-Valued Functions

  1991cited by this paper
• Convergence of approximation schemes for fully nonlinear second order equations

  1990cited by this paper
• A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory

  1975cited by this paper
• On Convex Polyhedra

  1970cited by this paper
• Hyperspheres Associated with an n-Simplex

  1967cited by this paper

• Efficient numerical strategies for entropy-regularized semi-discrete optimal transport

  2026cites this paper
• Memory Efficient And Minimax Distribution Estimation Under Wasserstein Distance Using Bayesian Histograms

  2023influential citation
• OPTIMAL TRANSPORT MAPS

  2023cites this paper
• Superconvergence of the effective Cauchy stress in computational homogenization of inelastic materials

  2022cites this paper
• Strong c-concavity and stability in optimal transport

  2022cites this paper
• Symmetrized semi-discrete optimal transport

  2022cites this paper
• Data driven gradient flows

  2022cites this paper
• A new implementation of the geometric method for solving the Eady slice equations

  2022cites this paper
• Lorenz map, inequality ordering and curves based on multidimensional rearrangements

  2022cites this paper
• Semi-discrete optimal transport methods for the semi-geostrophic equations

  2022cites this paper
• Unbalanced Optimal Transport, from Theory to Numerics

  2022cites this paper
• Accurate Baryon Acoustic Oscillations reconstruction via semi-discrete optimal transport

  2021cites this paper
• A discrete method for the initialization of semi-discrete optimal transport problem

  2021cites this paper
• A damped Newton algorithm for generated Jacobian equations

  2021influential citation
• Semi-discrete optimal transport: hardness, regularization and numerical solution

  2021cites this paper
• Metasurfaces and Optimal transport

  2021cites this paper
• Convergence of a Lagrangian discretization for barotropic fluids and porous media flow

  2021cites this paper
• Asymptotic analysis of domain decomposition for optimal transport

  2021cites this paper
• A stochastic Gauss-Newton algorithm for regularized semi-discrete optimal transport

  2021cites this paper
• Optimal transportation, modelling and numerical simulation

  2021influential citation
• Approximate continuous optimal transport with copulas

  2021cites this paper
• Computational Semi-Discrete Optimal Transport with General Storage Fees

  2020influential citation
• Fast methods for computing centroidal Laguerre tessellations for prescribed volume fractions with applications to microstructure generation of polycrystalline materials

  2020cites this paper
• Quantitative Stability in the Geometry of Semi-discrete Optimal Transport

  2020influential citation
• A fast semi-discrete optimal transport algorithm for a unique reconstruction of the early Universe

  2020cites this paper
• Examples of Hidden Convexity in Nonlinear PDEs

  2020cites this paper
• Semi-discrete optimal transport methods for the semi-geostrophic equations

  2020cites this paper
• Convergence Rates for Discretized Monge–Ampère Equations and Quantitative Stability of Optimal Transport

  2020influential citation
• Optimal transport: discretization and algorithms

  2020cites this paper
• Quantitative Stability and Error Estimates for Optimal Transport Plans

  2020cites this paper
• Multivariate goodness-of-fit tests based on Wasserstein distance

  2020cites this paper
• Lagrangian schemes for Wasserstein gradient flows

  2020cites this paper
• Two Stage Algorithm for Semi-Discrete Optimal Transport on Disconnected Domains

  2019cites this paper
• Tackling Algorithmic Bias in Neural-Network Classifiers using Wasserstein-2 Regularization

  2019cites this paper
• Laguerre tessellations and polycrystalline microstructures: a fast algorithm for generating grains of given volumes

  2019influential citation
• Courbes et applications optimales à valeurs dans l'espace de Wasserstein

  2019cites this paper
• 3/4-Discrete Optimal Transport

  2018cites this paper
• Crowd motion and evolution PDEs under density constraints

  2018cites this paper
• Convergence Rates for Discretized Monge–Ampère Equations and Quantitative Stability of Optimal Transport

  2018cites this paper
• Approches variationnelles pour le stippling : distances L 2 ou transport optimal ?

  2017influential citation
• The Sinkhorn algorithm, parabolic optimal transport and geometric Monge–Ampère equations

  2017cites this paper