Kantorovich Dual Problem (for general costs): Difference between revisions
Jump to navigation
Jump to search
| Line 6: | Line 6: | ||
(Kantorovich Duality) Let X and Y be Polish spaces, let <math>\mu \in \mathcal{P}(X)</math> and <math>\nu \in \mathcal{P}(Y)</math>, and let a cost function <math> c:X \times Y \rightarrow[0,+\infty] </math> be lower semi-continuous. | (Kantorovich Duality) Let X and Y be Polish spaces, let <math>\mu \in \mathcal{P}(X)</math> and <math>\nu \in \mathcal{P}(Y)</math>, and let a cost function <math> c:X \times Y \rightarrow[0,+\infty] </math> be lower semi-continuous. | ||
Whenever <math> \pi \in \mathcal{P}(X \times Y) </math> and <math> (\varphi, \psi) \in L^{1}(d\mu) \times L^{1}(d\nu) </math>, define | Whenever <math> \pi \in \mathcal{P}(X \times Y) </math> and <math> (\varphi, \psi) \in L^{1}(d\mu) \times L^{1}(d\nu) </math>, define <br> | ||
<br> | |||
<math> I[\pi]= \int_{X\times Y} c(x,y) d\pi(x,y), \quad J(\varphi,\psi)=\int_{X}\varphi(x)d\mu(x)+\int_{Y}\psi(y) d\nu(y) </math>. | <math> I[\pi]= \int_{X\times Y} c(x,y) d\pi(x,y), \quad J(\varphi,\psi)=\int_{X}\varphi(x)d\mu(x)+\int_{Y}\psi(y) d\nu(y) </math>. | ||
| Line 14: | Line 14: | ||
<math> \pi[A\times Y]=\mu(A) </math>, <math> \pi[X\times B]=\nu(B) </math>, <br> | <math> \pi[A\times Y]=\mu(A) </math>, <math> \pi[X\times B]=\nu(B) </math>, <br> | ||
and define <math> \Phi_{c} </math> to be the set of all measurable functions <math> (\varphi, \psi) \in L^{1}(d\mu) \times L^{1}(d\nu) </math> satisfying <math> \varphi(x)+\psi(y) \leq c(x,y) </math> for <math> d\mu </math> almost everywhere in X and <math> d\nu </math> almost everywhere in Y. Then <math> inf_{\Pi(\mu,\nu)} I[\pi] = sup_{\Phi_{c}} J(\varphi,\psi) </math>. | and define <math> \Phi_{c} </math> to be the set of all measurable functions <math> (\varphi, \psi) \in L^{1}(d\mu) \times L^{1}(d\nu) </math> satisfying <math> \varphi(x)+\psi(y) \leq c(x,y) </math> for <math> d\mu </math> almost everywhere in X and <math> d\nu </math> almost everywhere in Y. Then <math> inf_{\Pi(\mu,\nu)} I[\pi] = sup_{\Phi_{c}} J(\varphi,\psi) </math>. <br> | ||
Moreover, the infimum <math> inf_{\Pi(\mu,\nu)} I[\pi] </math> is attained. It is possible to restrict <math> \varphi </math> and <math> \psi </math> to be continuous and bounded. | Moreover, the infimum <math> inf_{\Pi(\mu,\nu)} I[\pi] </math> is attained. It is possible to restrict <math> \varphi </math> and <math> \psi </math> to be continuous and bounded. | ||
Revision as of 23:15, 16 May 2020
Introduction
The main advantage of Kantorovich Problem, in comparison to Monge problem, is in the convex constraint property. It is possible to formulate the dual problem.
Statement of Theorem
(Kantorovich Duality) Let X and Y be Polish spaces, let and , and let a cost function be lower semi-continuous.
Whenever and , define
![{\displaystyle c:X\times Y\rightarrow [0,+\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b86eb4eb62728fa63010b95eb2c285d7d6a18649)
.
![{\displaystyle I[\pi ]=\int _{X\times Y}c(x,y)d\pi (x,y),\quad J(\varphi ,\psi )=\int _{X}\varphi (x)d\mu (x)+\int _{Y}\psi (y)d\nu (y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe572f66aca1d528fc4ced0547d7fc298e00b502)
Define to be the set of Borel probability measures on such that for all measurable sets and ,
, ,
![{\displaystyle \pi [A\times Y]=\mu (A)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d027029dfcbb54d2291e6cc3849e36a9f971b19)
![{\displaystyle \pi [X\times B]=\nu (B)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a697f291cc41bd1dde9d75e59465165aa8d7470)
and define to be the set of all measurable functions satisfying for almost everywhere in X and almost everywhere in Y. Then .
![{\displaystyle inf_{\Pi (\mu ,\nu )}I[\pi ]=sup_{\Phi _{c}}J(\varphi ,\psi )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a50255b1ee21717bcd40bc7ebe8097fd41a56f5)
Moreover, the infimum is attained. It is possible to restrict and to be continuous and bounded.
![{\displaystyle inf_{\Pi (\mu ,\nu )}I[\pi ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08af0947e4105f1b4f0fb9836742135d6c03735d)
Proof of Theorem
References
</ references>
- ↑ C. Villani, Topics in Optimal Transportation, Chapter 1. (pages 17-21)
- ↑ https://link-springer-com.proxy.library.ucsb.edu:9443/book/10.1007/978-3-319-20828-2 F. Santambrogio, Optimal Transport for Applied Mathematicians, Chapter 1.] (pages 9-16)