Skip to content
Licensed Unlicensed Requires Authentication Published by De Gruyter June 20, 2018

An approximation scheme for the Kantorovich–Rubinstein problem on compact spaces

  • Martha Lorena Avendaño-Garrido EMAIL logo , J. Rigoberto Gabriel-Argüelles , Ligia-Torres Quintana and Juan González-Hernández

Abstract

This paper presents an approximation scheme for the Kantorovich–Rubinstein mass transshipment (KR) problem on compact spaces. A sequence of finite-dimensional linear programs, minimal cost network flow problems with bounds, are introduced and it is proven that the limit of the sequence of the optimal values of these problems is the optimal value of the KR problem. Numerical results are presented approximating the Kantorovich metric between distributions on [0, 1].

MSC 2010: 49M25; 90C05; 90C08
  1. Funding: The work was supported by CONACyT Mexico.

References

[1] E. J. Anderson and P. Nash. Linear Programming in Infinite-Dimensional Spaces. Wiley, Chichester, 1987.Search in Google Scholar

[2] E. J. Anderson and A. B. Philpott. Duality and an algorithm for a class of continuous transportation problems. Math. Operations Research, 9:222–231, 1984.10.1287/moor.9.2.222Search in Google Scholar

[3] C. Bardaro and I. Mantellini. Asymptotic formulae for multivariate kantorovich type generalized sampling series. Acta Mathematica Sinica, 27(7):1247–1258, 2011.10.1007/s10114-011-0227-0Search in Google Scholar

[4] C. Bardaro and I. Mantellini. On convergence properties for a class of kantorovich discrete operators. Numer. Functional Anal. Optimiz., 33(4):374–396, 2012.10.1080/01630563.2011.652270Search in Google Scholar

[5] M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali. Linear Programming and Network Flows. Wiley-Interscience, New Jersey, 2010.10.1002/9780471703778Search in Google Scholar

[6] J. Benamou, B. D. Froese, and A. M. Oberman. Two numerical methods for the elliptic Monge-Ampère equation. ESAIMMath. Modelling Numer. Analysis, 44:737–758, 2010.10.1051/m2an/2010017Search in Google Scholar

[7] J. D. Benamou. Numerical resolution of an unbalanced mass transport problem. ESAIM Math. Modelling Numer. Analysis, 37:851–868, 2003.10.1051/m2an:2003058Search in Google Scholar

[8] J. D. Benamou and Y. Brenier. A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numerische Mathematik, 84:375–393, 2000.10.1007/s002110050002Search in Google Scholar

[9] V. I. Bogachev. Measure Theory, volume 2. Springer, Berlin, 2007.10.1007/978-3-540-34514-5Search in Google Scholar

[10] D. Bosc. Numerical approximation of optimal transport maps. SSRN, 2010.10.2139/ssrn.1730684Search in Google Scholar

[11] L. A. Caffarelli, M. Feldman, and R. J. McCann. Constructing optimal maps for Monge’s transport problem as a limit of strictly convex costs. J. Amer. Math. Society, 15:1–26, 2002.10.1090/S0894-0347-01-00376-9Search in Google Scholar

[12] F. Cluni, D. Costarelli, A. M. Minotti, and G. Vinti. Applications of sampling kantorovich operators to thermographic images for seismic engineering. J. Comput. Analysis Applic., 19(1):602 – 617, 2015.Search in Google Scholar

[13] D. Costarelli, A. Minotti, and G. Vinti. Approximation of discontinuous signals by sampling kantorovich series. J. Math. Analysis Applic., 450(2):1083–1103, 2017.10.1016/j.jmaa.2017.01.066Search in Google Scholar

[14] D. Costarelli and G. Vinti. Degree of approximation for nonlinear multivariate sampling kantorovich operators on some functions spaces. Numer. Funct. Analysis Optim., 36(8):964–990, 2015.10.1080/01630563.2015.1040888Search in Google Scholar

[15] D. Costarelli and G. Vinti. Approximation by max-product neural network operators of kantorovich type. Results Mathematics,69(3):505–519, 2016.10.1007/s00025-016-0546-7Search in Google Scholar

[16] J. Dedecker, C. Prieur, and R. P. de Fitte. Parametrized Kantorovich–Rubinstein theorem and application to the coupling of random variables. Lecture Notes in Statistics, 187:105–121, 2006.10.1007/0-387-36062-X_5Search in Google Scholar

[17] X. Deng, X. Cai, and J. Zou. Two-level space–time domain decomposition methods for three-dimensional unsteady inverse source problems. J. Sci. Computing, 67(3):860–882, 2016.10.1007/s10915-015-0109-1Search in Google Scholar

[18] H. Föllmer and A. Schied. Stochastic Finance: An Introduction in Discrete Time. Walter de Gruyter & Co., Berlin, 2004.10.1515/9783110212075Search in Google Scholar

[19] J. R. Gabriel, J. González-Hernández, and R. R. López-Martínez. Numerical approximations to the mass transfer problem on compact spaces. IMA J. Numer. Analysis, 30:1121–1136, 2010.10.1093/imanum/drn076Search in Google Scholar

[20] J. González-Hernández, J. Gabriel, and O. Hernández-Lerma. On solutions to the mass transfer problem. SIAM J. Optimization, 17:485–499, 2006.10.1137/050623991Search in Google Scholar

[21] K. Guittet. On the time-continuous mass transport problem and its approximation by augmented lagrangian techniques. SIAM J. Numer. Analysis, 41:382–399, 2003.10.1137/S0036142901386069Search in Google Scholar

[22] S. Haker, L. Zhu, A. Tannenbaum, and S. Angenent. Optimal mass transport for registration and warping. Int. J. Comput. Vision, 63:225–240, 2004.10.1023/B:VISI.0000036836.66311.97Search in Google Scholar

[23] L. Hanin and S. T. Rachev. An extension of the Kantorovich–Rubinstein mass-transshipment problem. Numer. Functi. Analysis Optim., 16:701–735, 1995.10.1080/01630569508816639Search in Google Scholar

[24] L. G. Hanin and S. T. Rachev. Mass-transshipment problems and ideal metrics. J. Comput. Appl. Math., 56:183–196, 1994.10.1016/0377-0427(94)90387-5Search in Google Scholar

[25] L. H. Hanin, S. T. Rachev, and A. Y. Yakovlev. On the optimal control of cancer radiotherapy for non-homogeneous cell population. Advances Appl. Probability, 25:1–23, 1993.10.2307/1427493Search in Google Scholar

[26] H. Heitsch and W. Romisch. A note on scenario reduction for two-stage stochastic programs. Operations Research Letters, 35:731–738, 2007.10.1016/j.orl.2006.12.008Search in Google Scholar

[27] O. Hernández-Lerma and J. R. Gabriel. Strong duality of the Monge–Kantorovich mass transfer problem in metric spaces. Mathematische Zeitschrift, 239:579–591, 2002.10.1007/s002090100325Search in Google Scholar

[28] O. Hernández-Lerma and J. Lasserre. Approximation schemes for infinite linear programs. SIAM J. Optimization, 8:973– 988, 1998.10.1137/S1052623497315768Search in Google Scholar

[29] D. Jiang, H. Feng, and J. Zou. Overlapping domain decomposition methods for linear inverse problems. Inverse Problems Imaging, 9(1):163–188, 2015.10.3934/ipi.2015.9.163Search in Google Scholar

[30] V. L. Levin. On the mass transfer problem. Soviet Math. Doklady, 6:1349–1353, 1975.Search in Google Scholar

[31] Q. Mérigot. A multiscale approach to optimal transport. Computer Graphics Forum, 30(5):1583–1592, 2011.10.1111/j.1467-8659.2011.02032.xSearch in Google Scholar

[32] K. R. Parthasarathy. Probability Measures on Metric Spaces. Academic Press, New York, 1972.Search in Google Scholar

[33] S. T. Rachev. Probability Metrics and the Stability of Stochastic Models. Wiley, New York, 1991.Search in Google Scholar

[34] S. T. Rachev, L. Klebanov, S. V. Stoyanov, and F. Fabozzi. The Methods of Distances in the Theory of Probability and Statistics. Springer, New York, 2013.10.1007/978-1-4614-4869-3Search in Google Scholar

[35] S. T. Rachev and R. L. Rüscherdof. Mass Transportation Problems, volume 1,2. Springer, New York, 1998.Search in Google Scholar

[36] L. Saumier, B. Khouider, and M. Agueh. Optimal transport for particle image velocimetry. Commun. Math. Sci., 13(1):269– 296, 2015.10.4310/CMS.2015.v13.n1.a13Search in Google Scholar

[37] A. Vershik. Kantorovich metric: initial history and little-known applications. J. Math. Sci., 133:1410–1417, 2006.10.1007/s10958-006-0056-3Search in Google Scholar

[38] Cédric Villani. Topics in Optimal Transportation. Number 58. American Mathematical Society, Providence, Rhode Island, 2003.Search in Google Scholar

[39] Cédric Villani. Optimal Transport: Old and New, volume 338. Springer Science & Business Media, Berlin, 2008.Search in Google Scholar

[40] H. Xiang and J. Zou. Randomized algorithms for large-scale inverse problems with general tikhonov regularizations. Inverse Problems, 31(8):085008, 2015.10.1088/0266-5611/31/8/085008Search in Google Scholar

[41] Y. Xu and J. Zou. Convergence of an adaptive finite element method for distributed flux reconstruction. Math. Comput., 84(296):2645–2663, 2015.10.1090/mcom/2961Search in Google Scholar

Received: 2017-1-17
Revised: 2017-5-25
Accepted: 2017-5-25
Published Online: 2018-6-20
Published in Print: 2018-6-26

© 2018 Walter de Gruyter GmbH Berlin/Boston

Downloaded on 26.10.2024 from https://www.degruyter.com/document/doi/10.1515/jnma-2017-0008/html
Scroll to top button