An approximation scheme for the Kantorovich-Rubinstein problem on compact spaces. (English) Zbl 1394.49030
Summary: 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:
| 49M25 | Discrete approximations in optimal control |
| 90C05 | Linear programming |
| 90C08 | Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) |
Keywords:
mass transshipment problem; minimal cost network flow problem; approximation scheme; Kantorovich metricReferences:
| [1] | E. J. Anderson and P. Nash. Linear Programming in Infinite-Dimensional Spaces. Wiley, Chichester, 1987. · Zbl 0632.90038 |
| [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. · Zbl 0538.90057 |
| [3] | C. Bardaro and I. Mantellini. Asymptotic formulae for multivariate kantorovich type generalized sampling series. Acta Mathematica Sinica, 27(7):1247-1258, 2011. · Zbl 1303.41008 |
| [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. · Zbl 1267.41021 |
| [5] | M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali. Linear Programming and Network Flows. Wiley-Interscience, New Jersey, 2010. · Zbl 1200.90002 |
| [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. · Zbl 1192.65138 |
| [7] | J. D. Benamou. Numerical resolution of an unbalanced mass transport problem. ESAIM Math. Modelling Numer. Analysis, 37:851-868, 2003. · Zbl 1037.65063 |
| [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. · Zbl 0968.76069 |
| [9] | V. I. Bogachev. Measure Theory, volume 2. Springer, Berlin, 2007. · Zbl 1120.28001 |
| [10] | D. Bosc. Numerical approximation of optimal transport maps. SSRN, 2010. |
| [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. · Zbl 1053.49032 |
| [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. · Zbl 1369.94021 |
| [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. · Zbl 1373.41018 |
| [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. · Zbl 1327.41008 |
| [15] | D. Costarelli and G. Vinti. Approximation by max-product neural network operators of kantorovich type. Results Mathematics,69(3):505-519, 2016. · Zbl 1355.41009 |
| [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. · Zbl 1106.60027 |
| [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. · Zbl 1342.49044 |
| [18] | H. Föllmer and A. Schied. Stochastic Finance: An Introduction in Discrete Time. Walter de Gruyter & Co., Berlin, 2004. · Zbl 1126.91028 |
| [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. · Zbl 1210.65109 |
| [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. · Zbl 1165.49313 |
| [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. · Zbl 1039.65050 |
| [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. · Zbl 1477.68510 |
| [23] | L. Hanin and S. T. Rachev. An extension of the Kantorovich-Rubinstein mass-transshipment problem. Numer. Functi. Analysis Optim., 16:701-735, 1995. · Zbl 0834.60024 |
| [24] | L. G. Hanin and S. T. Rachev. Mass-transshipment problems and ideal metrics. J. Comput. Appl. Math., 56:183-196, 1994. · Zbl 0834.60003 |
| [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. · Zbl 0767.60011 |
| [26] | H. Heitsch and W. Romisch. A note on scenario reduction for two-stage stochastic programs. Operations Research Letters, 35:731-738, 2007. · Zbl 1169.90420 |
| [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. · Zbl 1003.90026 |
| [28] | O. Hernández-Lerma and J. Lasserre. Approximation schemes for infinite linear programs. SIAM J. Optimization, 8:973- 988, 1998. · Zbl 0912.90219 |
| [29] | D. Jiang, H. Feng, and J. Zou. Overlapping domain decomposition methods for linear inverse problems. Inverse Problems Imaging, 9(1):163-188, 2015. · Zbl 1307.65157 |
| [30] | V. L. Levin. On the mass transfer problem. Soviet Math. Doklady, 6:1349-1353, 1975. · Zbl 0338.90044 |
| [31] | Q. Mérigot. A multiscale approach to optimal transport. Computer Graphics Forum, 30(5):1583-1592, 2011. |
| [32] | K. R. Parthasarathy. Probability Measures on Metric Spaces. Academic Press, New York, 1972. · Zbl 0153.19101 |
| [33] | S. T. Rachev. Probability Metrics and the Stability of Stochastic Models. Wiley, New York, 1991. · Zbl 0744.60004 |
| [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. · Zbl 1280.60005 |
| [35] | S. T. Rachev and R. L. Rüscherdof. Mass Transportation Problems, volume 1,2. Springer, New York, 1998. · Zbl 0990.60500 |
| [36] | L. Saumier, B. Khouider, and M. Agueh. Optimal transport for particle image velocimetry. Commun. Math. Sci., 13(1):269- 296, 2015. · Zbl 1309.76169 |
| [37] | A. Vershik. Kantorovich metric: initial history and little-known applications. J. Math. Sci., 133:1410-1417, 2006. · Zbl 1090.28009 |
| [38] | Cédric Villani. Topics in Optimal Transportation. Number 58. American Mathematical Society, Providence, Rhode Island, 2003. · Zbl 1106.90001 |
| [39] | Cédric Villani. Optimal Transport: Old and New, volume 338. Springer Science & Business Media, Berlin, 2008. · Zbl 1156.53003 |
| [40] | H. Xiang and J. Zou. Randomized algorithms for large-scale inverse problems with general tikhonov regularizations. Inverse Problems, 31(8):085008, 2015. · Zbl 1327.65077 |
| [41] | Y. Xu and J. Zou. Convergence of an adaptive finite element method for distributed flux reconstruction. Math. Comput., 84(296):2645-2663, 2015. · Zbl 1321.65163 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
