Computational semi-discrete optimal transport with general storage fees

DOI10.1016/J.JMAA.2021.125287zbMATH Open1468.49028arXiv2007.03830OpenAlexW3159488756MaRDI QIDQ2038176FDOQ2038176

Authors: Mohit Bansil 

Publication date: 9 July 2021

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

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.

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

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

zbMATH Keywords

optimal transportNewton methodLaguerre cell

Mathematics Subject Classification ID

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

Cites Work

• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Optimal Transport
• On the regularity of solutions of optimal transportation problems
• Convex Analysis
• Regularity of potential functions of the optimal transportation problem
• 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 second boundary value problem for Monge-Ampère type equations and optimal transportation
• Optimum and equilibrium in a transport problem with queue penalization effect
• Discretization of the 3d monge−ampere operator, between wide stencils and power diagrams
• Convergence of a Newton algorithm for semi-discrete optimal transport
• A Numerical Algorithm forL₂Semi-Discrete Optimal Transport in 3D
• Approximation of convex functions
• Lectures on convex optimization
• An Algorithm for Optimal Transport between a Simplex Soup and a Point Cloud

Cited In (1)

• Title not available (Why is that?)

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)