Soluciones duales del problema de transporte óptimo 1D

Question

Sean $\mu$ y $\nu$ dos medidas de probabilidad en la línea real con momento finito $p$ para $p\in [1, \infty)$. Estoy interesado en las funciones $f:\mathbb{R}\rightarrow \mathbb{R}$ y $g:\mathbb{R}\rightarrow \mathbb{R}$ que resuelven el dual del problema de transporte óptimo $$OT(\mu, \nu) = \max\left\{ \int f\,d\mu + \int g\,d\nu,\, \Big|\,f\in L^1(\mu), \, g\in L^1(\nu) \, \text{y}\, f(x)+g(y)\leq h(x-y)\, \right\},$$ para una función convexa arbitraria $h:\mathbb{R}\rightarrow \mathbb{R}$. En particular, me gustaría saber cómo lucen $f$ (y $g$) si $\mu$ y $\nu$ son medidas discretas (o en general no absolutamente continuas). ¡Gracias de antemano por cualquier ayuda! :)

Actualización: Si $\mu$ y $\nu$ son discretas, entonces, si definimos $f(x_1)=0$, una de las soluciones dobles está dada por $$f(x_{i}) = \sum_{t=1}^{i-1} h(G^{-1}(F(x_t)) - x_{t+1}) - h(G^{-1}(F(x_t)), x_{t}) \quad \text{con} \quad i = 2, \dots, n,$$

donde $F$ es la función de distribución acumulada de $\mu$ y $G^{-1}$ es la función cuantil de $\nu$. Esto funciona incluso si no hay mapa de transporte entre $\mu$ y $\nu$. Además, si $\mu$ y $\nu$ son continuas y tienen un soporte conectado y $h$ es diferenciable, entonces: $$f(x) = - \int_{-\infty}^x h'(G^{-1}(F(t)) - t)\, dt.$$ (Más sobre la motivación de esto vendrá pronto en forma de respuesta).

Answer 1

Supongamos que $\mu$ es discreta y tiene puntos de soporte $x_1, \dots, x_n\in \mathbb{R}$. Sea $F$ la c.d.f. de $\mu$ y $F^{-1}$ y $G^{-1}$ las funciones cuantil de $\mu$ y $\nu$ respectivamente. Se sabe entonces que un plan de transporte óptimo está dado por la distribución de $(F^{-1}(U), G^{-1}(U))\sim \pi^*$ donde$U\sim \mathrm{Unif}[0, 1]$. Ahora consideremos el conjunto $$\Gamma = \bigcup_{i=1}^n \left(\{x_i\}\times [G^{-1}\circ F(x_{i-1}), G^{-1}\circ F(x_i)]\right).$$ Dado que $G^{-1}$ y $F$ son crecientes, tenemos que para todo $(x_1, y_1), (x_2, y_2)\in \Gamma$, se cumple que si $x_1 < x_2$ entonces $y_1\leq y_2$. Como se puede demostrar fácilmente, esto es equivalente a decir que el conjunto es cíclicamente monotono-c. Además, $\Gamma$ es cerrado y $\mathrm{supp}\, \pi^* = (F^{-1}, G^{-1})[0, 1] \subset \Gamma$.

Según el Paso 3 del Teorema 5.10 en Optimal Transport old and new de Villani, entonces sabemos que existe una función c-convexa $f$ tal que su c-subdiferencial satisface $\Gamma \subset \partial_c f$. Para construir ahora $f$ explícitamente, podemos usar de forma recursiva la caracterización del subdiferencial $$(x, y) \in \partial_c f \quad \text{si y solo si}\quad f(x) + f^c(y) = c(x, y),$$ donde $f^c$ es la c-transformación de $f$. Ahora fijamos $f(x_1)=0$. Entonces, dado que $(x_1, G^{-1}\circ F(x_1))\in \partial_c f$, encontramos que $$f^c(G^{-1}\circ F(x_1))=c(x_1, y_1).$$ Procediendo por inducción, asumamos que conocemos los valores de $f(x_i)$ y $f^c(G^{-1}\circ F(x_i))$. Entonces podemos usar que $(x_{i+1}, G^{-1}\circ F(x_i)) \in \Gamma \subset \partial_c f$ para derivar: $$f(x_{i+1}) = c(x_{i+1}, G^{-1}\circ F(x_i)) - f^c(G^{-1}\circ F(x_i))$$ y luego ya que $(x_{i+1}, G^{-1}\circ F(x_{i+1})) \in \Gamma \subset \partial_c f$, $$f^c(G^{-1}\circ F (x_{i+1})) = c(x_{i+1}, G^{-1}\circ F(x_{i+1})) - f(x_{i+1}).$$ Por inducción, luego obtenemos $$f(x_{i}) = \sum_{t=1}^{i-1} h(G^{-1}(F(x_t))- x_{t+1}) - h(G^{-1}(F(x_t))- x_{t}) \quad \text{con} \quad i = 2, \dots, n.$$