A formula for the optimal value in the Monge–Kantorovich problem with a smooth cost function, and a characterization of cyclically monotone mappings

V. L. Levin

Sbornik. Mathematics, Tome 71 (1992) no. 2, pp. 533-548

Résumé

The general Monge–Kantorovich problem consists in the computation of the optimal value $$ \mathscr A(c,\rho):=\inf\biggl\{\int_{X\times X}c(x,y)\mu(d(x,y))\colon\mu\in V_+(X\times X),\ (\pi_1-\pi_2)\mu=\rho\biggr\}, $$ where the cost function $c\colon X\times X\to \mathbf R^1$ and the measure $\rho$ on $X$ with $\rho X=0$ are assumed to be given, $V_+(X\times X)$ is the cone of finite positive Borel measures on $X\times X$, and $\pi_1$ and $\pi_2$ are the projections on the first and second coordinates, which assign to a measure $\mu$ the corresponding marginal measures. An explicit formula is obtained for $\mathscr A(c,\rho)$ in the case when $X$ is a domain in $\mathbf R^n$ and $c$ is bounded, vanishes on the diagonal, and is continuously differentiable in a neighborhood of the diagonal. Conditions for the set $$ Q_0(c):=\{u\colon X\to\mathbf R^1:u(x)-u(y)\leqslant c(x,y)\ \ \forall\,x,y\in X\} $$ to be nonempty are investigated, and with their help new characterizations of cyclically monotone mappings are obtained.

Bibliographie

[1] Levin V. L., Milyutin A. A., “Zadacha o peremeschenii mass s razryvnoi funktsiei stoimosti i massovaya postanovka problemy dvoistvennosti vypuklykh ekstremalnykh zadach”, UMN, 34:3 (1979), 3–68 | MR | Zbl

[2] Levin V. L., “Zadacha o peremeschenii mass v topologicheskom prostranstve i veroyatnostnye mery na proizvedenii dvukh prostranstv, obladayuschie zadannymi marginalnymi merami”, DAN SSSR, 276:5 (1984), 1059–1064 | MR | Zbl

[3] Levin V. L., “Izmerimye selektory mnogoznachnykh otobrazhenii i zadacha o peremeschenii mass”, DAN SSSR, 292:5 (1987), 1048–1053 | MR | Zbl

[4] Kantorovich L. V., Rubinshtein G. Sh., “Ob odnom funktsionalnom prostranstve i nekotorykh ekstremalnykh zadachakh”, DAN SSSR, 115:6 (1957), 1058–1061 | Zbl

[5] Kantorovich L. V., Rubinshtein G. Sh., “Ob odnom prostranstve vpolne additivnykh funktsii”, Vestn. LGU. Seriya matem., mekh. i astr., 7:8 (1958), 52–59 | Zbl

[6] Kantorovich L. V., Akilov G. P., Funktsionalnyi analiz, Nauka, M., 1984 | MR | Zbl

[7] Vallander S. S., “Vychislenie rasstoyaniya po Vassershteinu mezhdu raspredeleniyami veroyatnostei na pryamoi”, Teoriya veroyatnostei i ee primeneniya, 18:4 (1973), 824–827 | MR | Zbl

[8] Rüschendorf L., “The Wasserstein distance and approximation theorems”, Z. Wahrscheinlichkeitstheor. verw. Gebiete. Heft I, 70 (1985), 117–129 | DOI | MR | Zbl

[9] Vershik A. M., Temelt V., “Nekotorye voprosy approksimatsii optimalnogo znacheniya beskonechnomernykh zadach lineinogo programmirovaniya”, Sib. matem. zhurn., 9:4 (1968), 790–803 | MR | Zbl

[10] Vershik A. M., “Neskolko zamechanii o beskonechnomernykh zadachakh lineinogo programmirovaniya”, UMN, 25:5 (1970), 117–124

[11] Levin V. L., “Dvoistvennost i approksimatsiya v zadache o peremeschenii mass”, Matematicheskaya ekonomika i funktsionalnyi analiz, Nauka, M., 1974, 94–108

[12] Levin V. L., “Zadacha Monzha - Kantorovicha o peremeschenii mass”, Metody funktsionalnogo analiza v matematicheskoi ekonomike, Nauka, M., 1978, 23–55 | MR

[13] Anderson E. J., Philpott A. B., “An algorithm for a continuous version of the assignment problem”, Semi-infinite programming and applications, Lecture notes in economics and mathematical systems, 215, Springer-Verlag, Berlin-Heidelberg-New York-Tokyo, 1983, 108–117 | MR

[14] Anderson E. J., Philpott A. B., “Duality and an algorithm for a class of continuous transportation problems”, Mathematics of operation research, 9:2 (1984), 222–231 | DOI | MR | Zbl

[15] Gordevskii V. D., Lysenko Yu. V., Ovcharenko I. E., Pavlenko L. D., “Primenenie metodov funktsionalnogo analiza k zadacham obrabotki izobrazhenii”, Vestn. Kharkovskogo Universiteta. Dinamicheskie sistemy, 1989, no. 334, 16–25 | MR | Zbl

[16] Rachev S. T., “Zadacha Monzha - Kantorovicha o peremeschenii mass i ee primeneniya v stokhastike”, Teoriya veroyatnostei i ee primeneniya, 29:4 (1984), 625–653 | MR | Zbl

[17] Rockafellar R. T., “Characterization of the subdifferentials of convex functions”, Pacif. J. math., 17 (1966), 497–510 | MR | Zbl

[18] Rokafellar R., Vypuklyi analiz, Mir, M., 1973

[19] Kuratovskii K., Topologiya, t. 1, Mir, M., 1966 | MR

[20] Levin V. L., Vypuklyi analiz v prostranstvakh izmerimykh funktsii i ego primenenie v matematike i ekonomike, Nauka, M., 1985 | MR

[21] Ortega Dzh., Reinboldt V., Iteratsionnye metody resheniya nelineinykh sistem uravnenii so mnogimi neizvestnymi, Mir, M., 1975 | MR