Skip to main content

2015 | OriginalPaper | Buchkapitel

An Efficient Numerical Approximation for the Monge-Kantorovich Mass Transfer Problem

verfasst von : M. L. Avendaño-Garrido, J. R. Gabriel-Argüelles, L. Quintana-Torres, E. Mezura-Montes

Erschienen in: Machine Learning, Optimization, and Big Data

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The approximation scheme for the Monge-Kantorovich mass transfer problem on compact spaces proposed in [7] is improved. The upgrade presented is inspired on a meta-heuristic algorithm called Scatter Search in order to reduce the dimensionality of the problem. The new approximation scheme solves finite linear programs similar to the transport problem but with lower dimension. A numerical example is presented and compared with the scheme studied in [7].

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Anderson, E., Nash, P.: Linear Programming in Infinite-dimensional Spaces. Wiley, New York (1987)MATH Anderson, E., Nash, P.: Linear Programming in Infinite-dimensional Spaces. Wiley, New York (1987)MATH
2.
Zurück zum Zitat Anderson, E., Philpott, A.: Duality and an algorithm for a class of continuous transportation problems. Math. Oper. Res. 9, 222–231 (1984)MATHMathSciNetCrossRef Anderson, E., Philpott, A.: Duality and an algorithm for a class of continuous transportation problems. Math. Oper. Res. 9, 222–231 (1984)MATHMathSciNetCrossRef
3.
Zurück zum Zitat Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows. Wiley-Interscience, New Jersey (2010)MATH Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows. Wiley-Interscience, New Jersey (2010)MATH
4.
Zurück zum Zitat Bosc, D.: Numerical approximation of optimal transport maps. SSRN (2010) Bosc, D.: Numerical approximation of optimal transport maps. SSRN (2010)
5.
Zurück zum Zitat Deng, Y., Du, W.: Kantorovich metric in computer science: a brief survey. Electron. Notes Theoret. Comput. Sci. 353(3), 73–82 (2009)CrossRef Deng, Y., Du, W.: Kantorovich metric in computer science: a brief survey. Electron. Notes Theoret. Comput. Sci. 353(3), 73–82 (2009)CrossRef
6.
Zurück zum Zitat Evans, S., Matsen, F.: The phylogenetic kantorovich-rubinstein metric for environmental sequence samples. J. Roy. Stat. Soc.: Ser. B (Stat. Methodol.) 74(3), 569–592 (2012)MathSciNetCrossRef Evans, S., Matsen, F.: The phylogenetic kantorovich-rubinstein metric for environmental sequence samples. J. Roy. Stat. Soc.: Ser. B (Stat. Methodol.) 74(3), 569–592 (2012)MathSciNetCrossRef
7.
Zurück zum Zitat Gabriel, J., González-Hernández, J., López-Martínez, R.: Numerical approximations to the mass transfer problem on compact spaces. IMA J. Numer. Anal. 30, 1121–1136 (2010)MATHMathSciNetCrossRef Gabriel, J., González-Hernández, J., López-Martínez, R.: Numerical approximations to the mass transfer problem on compact spaces. IMA J. Numer. Anal. 30, 1121–1136 (2010)MATHMathSciNetCrossRef
8.
Zurück zum Zitat Glover, F.: A template for scatter search and path relinking. In: Hao, J.-K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.) AE 1997. LNCS, vol. 1363, pp. 1–51. Springer, Heidelberg (1998) CrossRef Glover, F.: A template for scatter search and path relinking. In: Hao, J.-K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.) AE 1997. LNCS, vol. 1363, pp. 1–51. Springer, Heidelberg (1998) CrossRef
9.
Zurück zum Zitat González-Hernández, J., Gabriel, J., Hernández-Lerma, O.: On solutions to the mass transfer problem. SIAM J. Optim. 17, 485–499 (2006)MATHMathSciNetCrossRef González-Hernández, J., Gabriel, J., Hernández-Lerma, O.: On solutions to the mass transfer problem. SIAM J. Optim. 17, 485–499 (2006)MATHMathSciNetCrossRef
10.
Zurück zum Zitat Haker, S., Zhu, L., Tannenbaum, A., Angenent, S.: Optimal mass transport for registration and warping. Int. J. Comput. Vision 63, 225–240 (2004)CrossRef Haker, S., Zhu, L., Tannenbaum, A., Angenent, S.: Optimal mass transport for registration and warping. Int. J. Comput. Vision 63, 225–240 (2004)CrossRef
11.
Zurück zum Zitat Hanin, L., Rachev, S., Yakovlev, A.: On the optimal control of cancer radiotherapy for non-homogeneous cell population. Adv. Appl. Probab. 25, 1–23 (1993)MATHMathSciNetCrossRef Hanin, L., Rachev, S., Yakovlev, A.: On the optimal control of cancer radiotherapy for non-homogeneous cell population. Adv. Appl. Probab. 25, 1–23 (1993)MATHMathSciNetCrossRef
12.
13.
Zurück zum Zitat Kantorovich, L.: On a problem of monge. J. Math. Sci. 133(4), 225–226 (2006) Kantorovich, L.: On a problem of monge. J. Math. Sci. 133(4), 225–226 (2006)
15.
Zurück zum Zitat Levin, V.: Optimality conditions and exact solutions to the two-dimensional monge-kantorovich problem. J. Math. Sci. 133(4), 1456–1463 (2006)MATHMathSciNetCrossRef Levin, V.: Optimality conditions and exact solutions to the two-dimensional monge-kantorovich problem. J. Math. Sci. 133(4), 1456–1463 (2006)MATHMathSciNetCrossRef
16.
Zurück zum Zitat Martí, R., Laguna, M., Glover, F.: Principles of scatter search. Eur. J. Oper. Res. 169, 359–372 (2006)MATHCrossRef Martí, R., Laguna, M., Glover, F.: Principles of scatter search. Eur. J. Oper. Res. 169, 359–372 (2006)MATHCrossRef
17.
Zurück zum Zitat Mèrigot, Q.: A multiscale approach to optimal transport. Computer Graphics Forum 30(5), 1583–1592 (2011)CrossRef Mèrigot, Q.: A multiscale approach to optimal transport. Computer Graphics Forum 30(5), 1583–1592 (2011)CrossRef
18.
Zurück zum Zitat Monge, G.: Mémoire sur la théorie des déblais et des remblais. De l’Imprimerie Royale, Paris (1781) Monge, G.: Mémoire sur la théorie des déblais et des remblais. De l’Imprimerie Royale, Paris (1781)
19.
Zurück zum Zitat Rachev, S.: Probability Metrics and the Stability of Stochastic Models. Wiley, New York (1991) MATH Rachev, S.: Probability Metrics and the Stability of Stochastic Models. Wiley, New York (1991) MATH
20.
Zurück zum Zitat Rachev, S., Rüschendorf, L.: Mass Transportation Problems, vol.I and II. Springer, New York (1998) Rachev, S., Rüschendorf, L.: Mass Transportation Problems, vol.I and II. Springer, New York (1998)
21.
Zurück zum Zitat Villani, C.: Optimal Transport: Old and New, vol. 338. Springer, Heidelberg (2008) Villani, C.: Optimal Transport: Old and New, vol. 338. Springer, Heidelberg (2008)
Metadaten
Titel
An Efficient Numerical Approximation for the Monge-Kantorovich Mass Transfer Problem
verfasst von
M. L. Avendaño-Garrido
J. R. Gabriel-Argüelles
L. Quintana-Torres
E. Mezura-Montes
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-27926-8_20