A Newton algorithm for semidiscrete optimal transport with storage fees
From MaRDI portal
(Redirected from A Newton algorithm for semidiscrete optimal transport with storage fees)
Abstract: 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 is the first numerical method with proven convergence for this variant problem; additionally the algorithm applies to the classical semi-discrete optimal transport problem but does not require any connectedness assumptions on the support of the source measure, in contrast with existing results. Furthermore we find some stability results of the associated Laguerre cells. All of our results come with quantitative rates. We also present some numerical examples.
Recommendations
- Computational semi-discrete optimal transport with general storage fees
- Convergence of a Newton algorithm for semi-discrete optimal transport
- scientific article; zbMATH DE number 7670331
- Asymptotics for semidiscrete entropic optimal transport
- Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case
Cites work
- A new optimal transport distance on the space of finite Radon measures
- A numerical algorithm for \(L_2\) semi-discrete optimal transport in 3D
- An algorithm for optimal transport between a simplex soup and a point cloud
- An efficient numerical algorithm for the \(L^{2}\) optimal transport problem with periodic densities
- An interpolating distance between optimal transport and Fisher-Rao metrics
- An iterative method for generated Jacobian equations
- An iterative scheme for solving the optimal transportation problem
- Capacitated facility location problem with general setup cost
- Computational optimal transport. With applications to data sciences
- Convergence of a Newton algorithm for semi-discrete optimal transport
- Convergence of entropic schemes for optimal transport and gradient flows
- Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampère equation in dimensions two and higher
- Convex Polyhedra
- Discretization of the 3D Monge-Ampere operator, between wide stencils and power diagrams
- Fast finite difference solvers for singular solutions of the elliptic Monge-Ampère equation
- scientific article; zbMATH DE number 4205918 (Why is no real title available?)
- scientific article; zbMATH DE number 1257371 (Why is no real title available?)
- Minkowski-type theorems and least-squares clustering
- Numerical solution of the Monge--Ampère equation by a Newton's algorithm
- Numerical solution of the optimal transportation problem using the Monge-Ampère equation
- On the design of a reflector antenna. II
- On the numerical solution of the equation \(\frac{\partial ^ 2z\partial ^ 2z}{\partial x^ 2\partial y^ 2}-(\frac{\partial ^ 2z}{\partial x\partial y})^ 2=f\) and its discretizations. I
- On the regularity of solutions of optimal transportation problems
- On the second boundary value problem for Monge-Ampère type equations and optimal transportation
- Optimal entropy-transport problems and a new Hellinger-Kantorovich distance between positive measures
- Optimal monopoly pricing with congestion and random utility via partial mass transport
- Optimal Transport
- Optimal transport and a bilevel location-allocation problem
- Optimal transport in competition with reaction: the Hellinger-Kantorovich distance and geodesic curves
- Optimum and equilibrium in a transport problem with queue penalization effect
- Pointwise rates of convergence for the Oliker-Prussner method for the Monge-Ampère equation
- Polar factorization and monotone rearrangement of vector‐valued functions
- Regularity of potential functions of the optimal transportation problem
- The Regularity of Mappings with a Convex Potential
- Unbalanced optimal transport: dynamic and Kantorovich formulations
- Uniformly convex and uniformly smooth convex functions
- Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian
Cited in
(5)- Computational semi-discrete optimal transport with general storage fees
- A damped Newton algorithm for generated Jacobian equations
- Convergence of a Newton algorithm for semi-discrete optimal transport
- scientific article; zbMATH DE number 7670331 (Why is no real title available?)
- Approximation theory, computing, and deep learning on the Wasserstein space
This page was built for publication: A Newton algorithm for semidiscrete optimal transport with storage fees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5162652)
