Approximation of optimal transport problems with marginal moments constraints

Alfonsi, Aurélien; Coyaud, Rafaël; Ehrlacher, Virginie; Lombardi, Damiano

doi:10.1090/mcom/3568

Approximation of optimal transport problems with marginal moments constraints
HTML articles powered by AMS MathViewer

by Aurélien Alfonsi, Rafaël Coyaud, Virginie Ehrlacher and Damiano Lombardi HTML | PDF

Math. Comp. 90 (2021), 689-737 Request permission

Abstract:

Optimal transport (OT) problems arise in a wide range of applications, from physics to economics. Getting a numerical approximate solution of these problems is a challenging issue of practical importance. In this work, we investigate the relaxation of the OT problem when the marginal constraints are replaced by some moment constraints. Using Tchakaloff’s theorem, we show that the moment constrained optimal transport problem (MCOT) is achieved by a finite discrete measure. Interestingly, for multimarginal OT problems, the number of points weighted by this measure scales linearly with the number of marginal laws, which is encouraging to bypass the curse of dimension. This approximation method is also relevant for Martingale OT problems. We show the convergence of the MCOT problem toward the corresponding OT problem. In some fundamental cases, we obtain rates of convergence in $O(1/n)$ or $O(1/n^2)$ where $n$ is the number of moments, which illustrates the role of the moment functions. Last, we present algorithms exploiting the fact that the MCOT is reached by a finite discrete measure and provide numerical examples of approximations.

References

Martial Agueh and Guillaume Carlier, Barycenters in the Wasserstein space, SIAM J. Math. Anal. 43 (2011), no. 2, 904–924. MR 2801182, DOI 10.1137/100805741
Aurélien Alfonsi, Jacopo Corbetta, and Benjamin Jourdain, Sampling of one-dimensional probability measures in the convex order and computation of robust option price bounds, Int. J. Theor. Appl. Finance 22 (2019), no. 3, 1950002, 41. MR 3951948, DOI 10.1142/S021902491950002X
Aurélien Alfonsi, Jacopo Corbetta, and Benjamin Jourdain, Sampling of probability measures in the convex order by Wasserstein projection, arXiv e-prints (2017Sep), arXiv:1709.05287, available at 1709.05287.
Charalambos D. Aliprantis and Kim C. Border, Infinite dimensional analysis, 3rd ed., Springer, Berlin, 2006. A hitchhiker’s guide. MR 2378491
Christian Bayer and Josef Teichmann, The proof of Tchakaloff’s theorem, Proc. Amer. Math. Soc. 134 (2006), no. 10, 3035–3040. MR 2231629, DOI 10.1090/S0002-9939-06-08249-9
Mathias Beiglböck, Pierre Henry-Labordère, and Friedrich Penkner, Model-independent bounds for option prices—a mass transport approach, Finance Stoch. 17 (2013), no. 3, 477–501. MR 3066985, DOI 10.1007/s00780-013-0205-8
Mathias Beiglböck, Pierre Henry-Labordère, and Nizar Touzi, Monotone martingale transport plans and Skorokhod embedding, Stochastic Process. Appl. 127 (2017), no. 9, 3005–3013. MR 3682121, DOI 10.1016/j.spa.2017.01.004
Mathias Beiglböck and Marcel Nutz, Martingale inequalities and deterministic counterparts, Electron. J. Probab. 19 (2014), no. 95, 15. MR 3272328, DOI 10.1214/EJP.v19-3270
Jean-David Benamou and Yann Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Math. 84 (2000), no. 3, 375–393. MR 1738163, DOI 10.1007/s002110050002
Jean-David Benamou and Guillaume Carlier, Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations, J. Optim. Theory Appl. 167 (2015), no. 1, 1–26. MR 3395203, DOI 10.1007/s10957-015-0725-9
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré, Iterative Bregman projections for regularized transportation problems, SIAM J. Sci. Comput. 37 (2015), no. 2, A1111–A1138. MR 3340204, DOI 10.1137/141000439
Georg Berschneider and Zoltán Sasvári, On a theorem of karhunen and related moment problems and quadrature formulae, Spectral theory, mathematical system theory, evolution equations, differential and difference equations, 2012, pp. 173–187.
Dimitri P. Bertsekas and David A. Castañon, The auction algorithm for the transportation problem, Ann. Oper. Res. 20 (1989), no. 1-4, 67–96. Network optimization and applications. MR 1015946, DOI 10.1007/BF02216923
Guillaume Carlier, Optimal transportation and economic applications, Lecture Notes (2012).
Maria Colombo, Luigi De Pascale, and Simone Di Marino, Multimarginal optimal transport maps for one-dimensional repulsive costs, Canad. J. Math. 67 (2015), no. 2, 350–368. MR 3314838, DOI 10.4153/CJM-2014-011-x
Codina Cotar, Gero Friesecke, and Brendan Pass, Infinite-body optimal transport with Coulomb cost, Calc. Var. Partial Differential Equations 54 (2015), no. 1, 717–742. MR 3385178, DOI 10.1007/s00526-014-0803-0
Hadrien De March, Entropic approximation for multi-dimensional martingale optimal transport, arXiv preprint arXiv:1812.11104 (2018).
Jean-François Delmas and Benjamin Jourdain, Modèles aléatoires, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 57, Springer-Verlag, Berlin, 2006 (French). Applications aux sciences de l’ingénieur et du vivant. [Applications to engineering and the life sciences]. MR 2250271
D. C. Dowson and B. V. Landau, The Fréchet distance between multivariate normal distributions, J. Multivariate Anal. 12 (1982), no. 3, 450–455. MR 666017, DOI 10.1016/0047-259X(82)90077-X
Gero Friesecke and Daniela Vögler, Breaking the curse of dimension in multi-marginal Kantorovich optimal transport on finite state spaces, SIAM J. Math. Anal. 50 (2018), no. 4, 3996–4019. MR 3829511, DOI 10.1137/17M1150025
Alfred Galichon, A survey of some recent applications of optimal transport methods to econometrics, The Econometrics Journal 20 (2017), no. 2, C1–C11, available at https://onlinelibrary.wiley.com/doi/pdf/10.1111/ectj.12083.
Thomas O. Gallouët and Quentin Mérigot, A Lagrangian scheme à la Brenier for the incompressible Euler equations, Found. Comput. Math. 18 (2018), no. 4, 835–865. MR 3833643, DOI 10.1007/s10208-017-9355-y
Gaoyue Guo and Jan Obloj, Computational Methods for Martingale Optimal Transport problems, arXiv e-prints (2017Oct), arXiv:1710.07911, available at 1710.07911.
Pierre Henry-Labordère, Model-free hedging, Chapman & Hall/CRC Financial Mathematics Series, CRC Press, Boca Raton, FL, 2017. A martingale optimal transport viewpoint. MR 3699668
Benjamin Jourdain and Julien Reygner, Propogation of chaos for rank-based interacting diffusions and long time behaviour of a scalar quasilinear parabolic equation, Stoch. Partial Differ. Equ. Anal. Comput. 1 (2013), no. 3, 455–506. MR 3327514, DOI 10.1007/s40072-013-0014-2
Quentin Mérigot, A multiscale approach to optimal transport, Computer Graphics Forum 30 (2011), no. 5, 1583–1592.
Luca Nenna, Numerical methods for multi-marginal optimal transportation, Ph.D. Thesis, 2016.
Gabriel Peyré and Marco Cuturi, Computational optimal transport, Foundations and Trends® in Machine Learning 11 (2019), no. 5-6, 355–607.
Elijah Polak, Optimization: Algorithms and Consistent Approximations, Vol. 124, Springer Science & Business Media, 1997.
Filippo Santambrogio, Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015. Calculus of variations, PDEs, and modeling. MR 3409718, DOI 10.1007/978-3-319-20828-2
Bernhard Schmitzer, A sparse multiscale algorithm for dense optimal transport, J. Math. Imaging Vision 56 (2016), no. 2, 238–259. MR 3535020, DOI 10.1007/s10851-016-0653-9
Michael Seidl, Paola Gori-Giorgi, and Andreas Savin, Strictly correlated electrons in density-functional theory: A general formulation with applications to spherical densities, Physical Review A 75 (2007), no. 4, 042511.
Meisam Sharify, Stéphane Gaubert, and Laura Grigori, Solution of the optimal assignment problem by diagonal scaling algorithms, arXiv preprint arXiv:1104.3830 (2011).
V. Strassen, The existence of probability measures with given marginals, Ann. Math. Statist. 36 (1965), 423–439. MR 177430, DOI 10.1214/aoms/1177700153
Cédric Villani, Optimal transport, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 338, Springer-Verlag, Berlin, 2009. Old and new. MR 2459454, DOI 10.1007/978-3-540-71050-9