Computational semi-discrete optimal transport with general storage fees

DOI10.1016/J.JMAA.2021.125287MaRDI QIDQ2038176zbMATH OpenOpenAlexFDO

Authors Mohit Bansil

Publication date 9 July 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

optimal transportNewton methodLaguerre cell

Mathematics Subject Classification ID

Optimal transportation (49Q22) Methods of quasi-Newton type (90C53) Newton-type methods (49M15)

Abstract: We propose and analyze a modified damped Newton algorithm to solve the semi-discrete optimal transport with storage fees. We prove global linear convergence for a wide range of storage fee functions, the main assumption being that each warehouse's storage costs are independent. We show that if $F$ is an arbitrary storage fee function that satisfies this independence condition then $F$ can be perturbed into a new storage fee function so that our algorithm converges. We also show that the optimizers are stable under these perturbations. Furthermore, our results come with quantitative rates.

Recommendations

• A Newton algorithm for semidiscrete optimal transport with storage fees
• scientific article; zbMATH DE number 7670331
• Convergence of a Newton algorithm for semi-discrete optimal transport
• Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case
• Semi-discrete optimal transport: hardness, regularization and numerical solution

Cites work

• 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
• Approximation of convex functions
• Convergence of a Newton algorithm for semi-discrete optimal transport
• Convex Analysis
• Discretization of the 3D Monge-Ampere operator, between wide stencils and power diagrams
• Lectures on convex optimization
• 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 Transport
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Optimum and equilibrium in a transport problem with queue penalization effect
• Regularity of potential functions of the optimal transportation problem

Cited in

(3)

• A Newton algorithm for semidiscrete optimal transport with storage fees
• scientific article; zbMATH DE number 7670331 (Why is no real title available?)
• Convergence of a Newton algorithm for semi-discrete optimal transport

This page was built for publication: Computational semi-discrete optimal transport with general storage fees

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