Teoría del transporte (matemáticas)

Supongamos que tenemos una colección de${\displaystyle m}$minas que extraen mineral de hierro y una colección de${\displaystyle n}$fábricas que utilizan el mineral de hierro que producen las minas. Supongamos, a modo de ejemplo, que estas minas y fábricas forman dos subconjuntos disjuntos.${\displaystyle M}$y${\displaystyle F}$del plano euclidiano${\displaystyle \mathbb {R} ^{2}}$Supongamos también que tenemos una función de coste .${\displaystyle c:\mathbb {R} ^{2}\times \mathbb {R} ^{2}\to [0,\infty )}$, de modo que${\displaystyle c(x,y)}$es el costo de transportar un envío de hierro desde${\displaystyle x}$a${\displaystyle y}$Para simplificar, ignoramos el tiempo que se tarda en realizar el transporte. También suponemos que cada mina puede abastecer solo a una fábrica (sin división de envíos) y que cada fábrica requiere exactamente un envío para estar en funcionamiento (las fábricas no pueden trabajar a la mitad o al doble de su capacidad). Habiendo hecho las suposiciones anteriores, un plan de transporte es una biyección.${\displaystyle T:M\to F}$En otras palabras, cada mina${\displaystyle m\in M}$suministra precisamente una fábrica objetivo${\displaystyle T(m)\in F}$y cada fábrica se abastece de una sola mina. Deseamos encontrar el plan de transporte óptimo , el plan${\displaystyle T}$cuyo costo total

${\displaystyle c(T):=\sum _{m\in M}c(m,T(m))}$

es el menos probable de todos los posibles planes de transporte desde${\displaystyle M}$a${\displaystyle F}$Este caso especial y motivador del problema del transporte es una instancia del problema de asignación . Más específicamente, es equivalente a encontrar un emparejamiento de peso mínimo en un grafo bipartito .

Esto se puede generalizar al caso continuo, donde existen infinitas minas y fábricas distribuidas en la recta real, o en general en cualquier espacio métrico. Este caso se suele representar como "cambiar la forma de un montón de tierra" y, por lo tanto, se denomina el problema del terraplén .

El siguiente ejemplo sencillo ilustra la importancia de la función de coste para determinar el plan de transporte óptimo. Supongamos que tenemos${\displaystyle n}$Libros de igual ancho en un estante (la línea real ), dispuestos en un único bloque contiguo. Deseamos reorganizarlos en otro bloque contiguo, pero desplazados un ancho de libro hacia la derecha. Se presentan dos candidatos obvios para el plan de transporte óptimo:

1. mover todo${\displaystyle n}$libros un ancho de libro hacia la derecha ("muchos movimientos pequeños");
2. mueve el libro de más a la izquierda${\displaystyle n}$Mueva los libros a la derecha y deje todos los demás libros fijos ("un gran movimiento").

Si la función de coste es proporcional a la distancia euclidiana (${\displaystyle c(x,y)=\alpha \|x-y\|}$para algunos${\displaystyle \alpha >0}$) entonces estos dos candidatos son óptimos . Si, por otro lado, elegimos la función de costo estrictamente convexa proporcional al cuadrado de la distancia euclidiana (${\displaystyle c(x,y)=\alpha \|x-y\|^{2}}$para algunos${\displaystyle \alpha >0}$), entonces la opción "muchos movimientos pequeños" se convierte en el único minimizador.

Cabe señalar que las funciones de coste anteriores solo consideran la distancia horizontal recorrida por los libros, no la distancia horizontal recorrida por el dispositivo utilizado para recoger cada libro y colocarlo en su posición. Si se considera esta última, entonces, de los dos planes de transporte, el segundo siempre es óptimo para la distancia euclidiana, mientras que, siempre que haya al menos 3 libros, el primer plan de transporte es óptimo para la distancia euclidiana al cuadrado.

La siguiente formulación del problema de transporte se atribuye a FL Hitchcock : ^{[ 7 ]}

Supongamos que hay${\displaystyle m}$fuentes${\displaystyle x_{1},\ldots ,x_{m}}$para una mercancía, con${\displaystyle a(x_{i})}$unidades de suministro en${\displaystyle x_{i}}$y${\displaystyle n}$fregaderos${\displaystyle y_{1},\ldots ,y_{n}}$para el producto, con la demanda${\displaystyle b(y_{j})}$en${\displaystyle y_{j}}$. Si${\displaystyle c(x_{i},\ y_{j})}$es el costo unitario de envío de${\displaystyle x_{i}}$a${\displaystyle y_{j}}$encontrar un flujo que satisfaga la demanda de los suministros y minimice el costo del flujo. Este desafío en logística fue abordado por DR Fulkerson ^{[ 8 ]} y en el libro Flows in Networks (1962) escrito con LR Ford Jr. ^{[ 9 ]}

A Tjalling Koopmans también se le atribuyen formulaciones sobre la economía del transporte y la asignación de recursos.

El problema del transporte, tal como se plantea en la literatura moderna o más técnica, presenta algunas diferencias debido al desarrollo de la geometría riemanniana y la teoría de la medida . El ejemplo de las minas y las fábricas, por simple que parezca, resulta un punto de referencia útil al considerar el caso abstracto. En este contexto, contemplamos la posibilidad de no desear mantener todas las minas y fábricas en funcionamiento, permitiendo que las minas abastezcan a más de una fábrica y que las fábricas reciban hierro de más de una mina.

Dejar${\displaystyle X}$y${\displaystyle Y}$Sean dos espacios métricos separables tales que cualquier medida de probabilidad en${\displaystyle X}$(o${\displaystyle Y}$) es una medida de Radon (es decir, son espacios de Radon ). Sea${\displaystyle c:X\times Y\to [0,\infty )}$Sea una función medible de Borel . Dadas las medidas de probabilidad.${\displaystyle \mu }$en${\displaystyle X}$y${\displaystyle \nu }$en${\displaystyle Y}$La formulación de Monge del problema de transporte óptimo consiste en encontrar un mapa de transporte.${\displaystyle T:X\to Y}$que realiza el ínfimo

${\displaystyle \inf \left\{\left.\int _{X}c(x,T(x))\,\mathrm {d} \mu (x)\right|T_{*}(\mu )=\nu \right\},}$

dónde${\displaystyle T_{*}(\mu )}$denota el impulso hacia adelante de${\displaystyle \mu }$por${\displaystyle T}$Un mapa${\displaystyle T}$El mapa que alcanza este ínfimo ( es decir, lo convierte en un mínimo en lugar de un ínfimo) se denomina "mapa de transporte óptimo".

La formulación de Monge del problema de transporte óptimo puede estar mal planteada, porque a veces no hay${\displaystyle T}$satisfactorio${\displaystyle T_{*}(\mu )=\nu }$: esto sucede, por ejemplo, cuando${\displaystyle \mu }$es una medida de Dirac pero${\displaystyle \nu }$no lo es.

Podemos mejorar esto adoptando la formulación de Kantorovich del problema de transporte óptimo, que consiste en encontrar una medida de probabilidad.${\displaystyle \gamma }$en${\displaystyle X\times Y}$que alcanza el ínfimo

${\displaystyle \inf \left\{\left.\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right|\gamma \in \Gamma (\mu ,\nu )\right\},}$

dónde${\displaystyle \Gamma (\mu ,\nu )}$denota la colección de todas las medidas de probabilidad en${\displaystyle X\times Y}$con márgenes${\displaystyle \mu }$en${\displaystyle X}$y${\displaystyle \nu }$en${\displaystyle Y}$.

Dada una función de coste${\displaystyle c(x,y)}$produce una transformación de dualidad${\displaystyle \psi \mapsto \psi ^{c}}$definido por$${\displaystyle \psi ^{c}(y):=\inf _{x}(c(x,y)-\psi (x))}$$Esto generaliza la transformación de Legendre , que es el caso donde${\displaystyle c(x,y)=-xy}$con un giro de letrero.

${\displaystyle \leq 1}$.

Decimos que una función${\displaystyle \psi }$es c -convexa si${\displaystyle \psi =\varphi ^{c}}$para algunos${\displaystyle \varphi }$. Tenga en cuenta que porque${\displaystyle \varphi ^{ccc}=\varphi ^{c}}$, siempre podemos asumir que${\displaystyle \varphi }$es c -convexa. La c -convexificación de una función${\displaystyle \psi }$es${\displaystyle \psi ^{cc}}$. De forma equivalente, es la función c -convexa más pequeña.${\displaystyle \psi '}$de tal manera que${\displaystyle \psi '\geq \psi }$punto por punto. ^{[ 10 ] : Prop. 5.8} Como en el caso de la transformación convexa,${\displaystyle \psi }$es c -convexa si y solo si${\displaystyle \psi =\psi ^{cc}}$.

Si${\displaystyle \psi =\varphi ^{c}:X\to \mathbb {R} }$es c -convexo, entonces el conjunto de c -subgradientes de${\displaystyle \psi }$en${\displaystyle x\in X}$es el conjunto de${\displaystyle y\in Y}$de tal manera que${\displaystyle \psi (x)=c(x,y)-\varphi (y)}$. De manera similar para${\displaystyle Y}$.

Cuando${\displaystyle X=Y}$, el gráfico${\displaystyle (y,\psi ^{c}(y))}$se puede construir de la siguiente manera: Tome la gráfica de${\displaystyle \psi }$y dale la vuelta. En cada punto${\displaystyle (x,-\psi (x))}$, construir un gráfico de${\displaystyle y\mapsto c(x,y)}$alcanzó su punto máximo en${\displaystyle (x,-\psi (x))}$. Es decir, es la gráfica de${\displaystyle y\mapsto c(x,y)-\psi (x)}$. Obtenemos un conjunto completo de tales gráficos. Su envolvente de borde inferior es el gráfico de${\displaystyle \psi ^{c}}$.

En la misma imagen, podemos ver lo que significa para una función.${\displaystyle \varphi (y)}$ser c -convexo. Es c -convexo si y solo si su gráfica completa puede ser "tocada" por una " herramienta con punta " que se mueve y cambia de forma. Cuando la herramienta con punta está en${\displaystyle x}$, tiene forma de${\displaystyle y\mapsto c(x,y)}$y se eleva a una altura de${\displaystyle -\psi (x)}$. El gráfico de la c -convexificación${\displaystyle \varphi ^{cc}(y)}$se construye haciendo funcionar la herramienta inclinada de manera que se baje lo máximo posible, mientras aún toca el gráfico de${\displaystyle \varphi (y)}$en la parte superior. El contorno inferior barrido por la herramienta puntiaguda es el gráfico de${\displaystyle \varphi ^{cc}(y)}$. ^{[ 10 ] : Fig. 5.2}

Por ejemplo, si${\displaystyle X=Y=\mathbb {R} ^{n}}$es un espacio métrico y${\displaystyle c(x,y)=\|x-y\|}$, entonces${\displaystyle \varphi :X\to \mathbb {R} }$es c -convexa si y solo si es 1- Lipschitz . Esto se utiliza en la definición de la distancia 1-Wasserstein . Si${\displaystyle c(x,y)=\|x-y\|^{2}}$, entonces${\displaystyle \varphi }$es c -convexa si y solo si su gráfica puede ser tocada desde arriba por una herramienta con punta en forma de paraboloide .

Bajo supuestos bastante permisivos, existe un plan de transporte óptimo.

Si

• ${\displaystyle (X,\mu _{X}),(Y,\mu _{Y})}$son espacios de probabilidad polacos ,
• ${\displaystyle c:X\times Y\to \mathbb {R} \cup \{\infty \}}$es semicontinuo inferior ,
• y existen algunas funciones semicontinuas superiores${\displaystyle a\in L^{1}(\mu _{X}),b\in L^{1}(\mu _{Y})}$de tipo${\displaystyle a:X\to \mathbb {R} \cup \{-\infty \},\;b:Y\to \mathbb {R} \cup \{-\infty \}}$de tal manera que${\displaystyle c(x,y)\geq a(x)+b(y)}$,

entonces existe un plan de transporte óptimo . Es decir, existe${\displaystyle \gamma ^{*}\in \Gamma (\mu _{X},\mu _{Y})}$de tal manera que alcanza el ínfimo. ^{[ 10 ] : Teorema 4.1}

Tenga en cuenta que el ínfimo podría ser infinito si todos los planes de transporte resultan ser infinitos. Por ejemplo, si${\displaystyle X=Y=\mathbb {R} ,c(x,y)=|x-y|,\;\mu _{X}}$es la distribución de Cauchy y${\displaystyle \mu _{Y}=\delta _{0}}$.

Si

• ${\displaystyle (X,\mu _{X}),(Y,\mu _{Y})}$son espacios de probabilidad polacos,
• ${\displaystyle c:X\times Y\to \mathbb {R} }$es semicontinuo inferior,
• existen algunas funciones semicontinuas superiores${\displaystyle a\in L^{1}(\mu _{X}),b\in L^{1}(\mu _{Y})}$de tipo${\displaystyle a:X\to \mathbb {R} ,\;b:Y\to \mathbb {R} }$de tal manera que${\displaystyle c(x,y)\geq a(x)+b(y)}$,
• Existe un plan de transporte de costo finito,
• y para cualquier función c -convexa${\displaystyle \psi :X\to \mathbb {R} \cup \{\infty \}}$, para${\displaystyle \mu _{X}}$-casi todos${\displaystyle x\in X}$,${\displaystyle \psi }$tiene un único subdiferencial c en${\displaystyle x}$

entonces existe un mapa de transporte óptimo . ^{[ 10 ] : Teorema 5.30}

Una restricción de un plan de transporte óptimo sigue siendo óptima. Es decir, supongamos que${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$es óptimo y${\displaystyle 0<\gamma '<\gamma }$y definir el plan de transporte normalizado${\displaystyle {\bar {\gamma }}':=\gamma '/\gamma '(X\times Y)}$, entonces${\displaystyle {\bar {\gamma }}'}$es un plan de transporte óptimo entre sus propios marginales. ^{[ 10 ] : Teorema 4.6} Si${\displaystyle {\bar {\gamma }}'}$Si no es óptimo, entonces existe una mejora del mismo, lo que a su vez se traduce en una mejora del original.${\displaystyle \gamma }$.

La dualidad de Kantorovich establece que: ^{[ 10 ] : Teorema 5.10}

Si${\displaystyle (X,\mu _{X}),(Y,\mu _{Y})}$son espacios de probabilidad polacos ,${\displaystyle c:X\times Y\to \mathbb {R} \cup \{\infty \}}$es semicontinua inferiormente , y existen algunas funciones semicontinuas superiores.${\displaystyle a\in L^{1}(\mu _{X}),b\in L^{1}(\mu _{Y})}$de tipo${\displaystyle a:X\to \mathbb {R} ,\;b:Y\to \mathbb {R} }$de tal manera que${\displaystyle c(x,y)\geq a(x)+b(y)}$, entonces$${\displaystyle \inf _{\gamma \in \Gamma (\mu ,\nu )}\left(\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right)=\sup _{\varphi {\text{ is }}c{\text{-convex}}}\left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\varphi ^{c}(y)\,\mathrm {d} \nu (y)\right)}$$Si además,${\displaystyle c}$solo toma valores reales, existe un plan de transporte con costo finito y existen algunas funciones${\displaystyle a'\in L^{1}(\mu _{X}),b'\in L^{1}(\mu _{Y})}$de tal manera que${\displaystyle c(x,y)\leq a'(x)+b'(y)}$, entonces$${\displaystyle \min _{\gamma \in \Gamma (\mu ,\nu )}\left(\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right)=\max _{\varphi {\text{ is }}c{\text{-convex}}}\left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\varphi ^{c}(y)\,\mathrm {d} \nu (y)\right)}$$

Consideremos el segundo caso, donde podemos llegar a un plan óptimo exacto, en lugar de simplemente acercarnos cada vez más. En este caso, un plan de transporte óptimo${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$, restringe la forma de un par de precios óptimo${\displaystyle (\varphi ,\psi )}$y viceversa.

Dado dicho par de precios óptimo${\displaystyle (\varphi ,\psi )}$, ^{[ 10 ] : Observación 5.13}

• dado un plan de transporte arbitrario${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$, si todos${\displaystyle (x,y)\in \operatorname {supp} (\gamma )}$satisface la igualdad exacta${\displaystyle c(x,y)=\varphi (x)+\psi (y)}$, entonces${\displaystyle \gamma }$es un plan óptimo;
• dado un plan de transporte óptimo${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$, cualquier${\displaystyle (x,y)\in \operatorname {supp} (\gamma )}$debe satisfacer la igualdad exacta${\displaystyle c(x,y)=\varphi (x)+\psi (y)}$.

De forma más concisa, un plan de transporte es óptimo si y solo si está soportado en el conjunto de pares c -subdiferenciales de${\displaystyle (\varphi ,\psi )}$.

El transporte óptimo es estable en el siguiente sentido: ^{[ 10 ] : Teorema 5.20}

Supongamos que${\displaystyle (X,\mu ),(Y,\nu )}$son espacios de probabilidad polacos ,${\displaystyle c:X\times Y\to \mathbb {R} }$es continuo y${\displaystyle \inf c}$es finito. Dada una secuencia de funciones continuas${\displaystyle c:X\times Y\to \mathbb {R} }$convergiendo uniformemente a${\displaystyle c}$encima${\displaystyle X\times Y}$, una secuencia${\displaystyle \mu _{k}\to \mu }$débilmente, una secuencia${\displaystyle \nu _{k}\to \nu }$débilmente, y una secuencia de planes de transporte óptimos${\displaystyle \gamma _{k}\in \Gamma (\mu _{k},\nu _{k})}$Si los costos de transporte${\displaystyle \int c_{k}d\pi _{k}}$satisfacer${\displaystyle \int c_{k}d\pi _{k}<+\infty ,\;\forall k}$y${\displaystyle \liminf _{k}\int c_{k}d\pi _{k}<+\infty }$, entonces${\displaystyle \gamma _{k}}$converge débilmente a algún${\displaystyle \gamma }$, y${\displaystyle \gamma }$es un plan de transporte óptimo desde${\displaystyle \mu }$a${\displaystyle \nu }$.

De manera similar, el mapa de transporte óptimo también es estable. ^{[ 10 ] : Cor. 5.23}

Supongamos que${\displaystyle (X,\mu ),(Y,\nu )}$son espacios de probabilidad polacos ,${\displaystyle X}$es localmente compacto,${\displaystyle c:X\times Y\to \mathbb {R} }$es semicontinuo inferior, y${\displaystyle \inf c}$es finito. Dada una secuencia de funciones semicontinuas inferiores${\displaystyle c:X\times Y\to \mathbb {R} }$convergiendo uniformemente a${\displaystyle c}$encima${\displaystyle X\times Y}$, una secuencia${\displaystyle \nu _{k}\to \nu }$enclenque,

El problema del transporte óptimo tiene una interpretación económica. ^{[ 11 ]} Cédric Villani relata la siguiente interpretación de Luis Caffarelli : ^{[ 12 ]}

Supongamos que desea enviar algo de carbón desde las minas, distribuido como${\displaystyle \mu }$, a las fábricas, distribuidas como${\displaystyle \nu }$La función de coste del transporte es${\displaystyle c}$. Ahora viene un transportista y se ofrece a hacer el transporte por usted. Usted le pagaría.${\displaystyle f(x)}$por carbón para cargar el carbón en${\displaystyle x}$y pagarle${\displaystyle g(y)}$por carbón para descargar el carbón en${\displaystyle y}$Para que usted acepte el trato, el cuadro de precios debe satisfacer${\displaystyle f(x)+g(y)\leq c(x,y)}$La dualidad de Kantorovich establece que el remitente puede crear una lista de precios que te haga pagar casi lo mismo que pagarías si enviaras el paquete tú mismo.

En la interpretación, la transformación de dualidad transforma una función de costo de carga.${\displaystyle \varphi (x)}$en la función de costo de descarga óptima (para el remitente)${\displaystyle \psi (y)=\varphi ^{c}(y)}$. Si la función de costo de descarga${\displaystyle \psi (y)}$si fuera más alto en algún momento, entonces habría alguna ruta${\displaystyle x\to y}$en el cual${\displaystyle c(x,y)<\varphi (x)+\psi (y)}$, lo que significa que hay alguna ruta por la que preferirías enviar tú mismo. Pero si la función de costo de descarga fuera menor en algún punto, entonces el remitente podría haber ganado más dinero aumentando el precio allí. Por lo tanto, el remitente siempre debería elegir${\displaystyle \psi =\varphi ^{c}}$El mismo argumento aplicado nuevamente afirma que el remitente siempre debe elegir${\displaystyle \varphi =\psi ^{c}}$y por lo tanto obtenemos la mitad del límite inferior de la fórmula de dualidad:$${\displaystyle \inf _{\gamma \in \Gamma (\mu ,\nu )}\left(\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right)\geq \sup _{\varphi {\text{ is }}c{\text{-convex}}}\left(\int _{X}\varphi (x)\,\mathrm {d} \mu (x)+\int _{Y}\varphi ^{c}(y)\,\mathrm {d} \nu (y)\right),}$$La dualidad de Kantorovich establece que, de hecho, se trata de una igualdad, es decir, el remitente puede hacerte pagar tanto como tú pagarías por tu cuenta, aunque el remitente quizás nunca alcance exactamente el límite (de ahí el uso de ínfimo y supremo, en lugar de mínimo y máximo).

Supongamos que el remitente de hecho debe pagar la misma función de costo y nosotros, y puede alcanzar exactamente el ingreso máximo utilizando${\displaystyle (\varphi ,\psi )}$como su tabla de precios. Entonces, el remitente debe usar un plan óptimo, en cuyo caso apenas alcanza el punto de equilibrio sin obtener ganancias. Por el contrario, cualquier plan de envío que le permita alcanzar exactamente el punto de equilibrio debe ser óptimo.

Matriz de transporte óptima

Transporte óptimo continuo

Para${\displaystyle 1\leq p<\infty }$, dejar${\displaystyle {\mathcal {P}}_{p}(\mathbb {R} )}$denotamos el conjunto de medidas de probabilidad en${\displaystyle \mathbb {R} }$que tienen finito${\displaystyle p}$-ésimo momento . Deja${\displaystyle \mu ,\nu \in {\mathcal {P}}_{p}(\mathbb {R} )}$y dejar${\displaystyle c(x,y)=h(x-y)}$, dónde${\displaystyle h:\mathbb {R} \to [0,\infty )}$es una función convexa .

1. Si${\displaystyle \mu }$no tiene átomo , es decir, si la función de distribución acumulativa${\displaystyle F_{\mu }:\mathbb {R} \to [0,1]}$de${\displaystyle \mu }$es una función continua , entonces${\displaystyle F_{\nu }^{-1}\circ F_{\mu }:\mathbb {R} \to \mathbb {R} }$es un mapa de transporte óptimo. Es el único mapa de transporte óptimo si${\displaystyle h}$es estrictamente convexa.
2. Tenemos

${\displaystyle \min _{\gamma \in \Gamma (\mu ,\nu )}\int _{\mathbb {R} ^{2}}c(x,y)\,\mathrm {d} \gamma (x,y)=\int _{0}^{1}c\left(F_{\mu }^{-1}(s),F_{\nu }^{-1}(s)\right)\,\mathrm {d} s.}$

La demostración de esta solución aparece en Rachev y Rüschendorf (1998). ^{[ 13 ]}

En el caso donde los márgenes${\displaystyle \mu }$y${\displaystyle \nu }$son discretos, dejemos${\displaystyle \mu _{x}}$ y${\displaystyle \nu _{y}}$sean las masas de probabilidad asignadas respectivamente a${\displaystyle x\in \mathbf {X} }$y${\displaystyle y\in \mathbf {Y} }$y dejar${\displaystyle \gamma _{xy}}$sea ​​la probabilidad de un${\displaystyle xy}$asignación. La función objetivo en el problema primal de Kantorovich es entonces

${\displaystyle \sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\gamma _{xy}c_{xy}}$

y la restricción${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$se expresa como

${\displaystyle \sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X} }$

y

${\displaystyle \sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y} .}$

Para introducir esto en un problema de programación lineal , necesitamos vectorizar la matriz.${\displaystyle \gamma _{xy}}$ya sea apilando sus columnas o sus filas , lo llamamos${\displaystyle \operatorname {vec} }$esta operación. En el orden de columnas principales , las restricciones anteriores se reescriben como

${\displaystyle \left(1_{1\times |\mathbf {Y} |}\otimes I_{|\mathbf {X} |}\right)\operatorname {vec} (\gamma )=\mu }$y${\displaystyle \left(I_{|\mathbf {Y} \|}\otimes 1_{1\times |\mathbf {X} |}\right)\operatorname {vec} (\gamma )=\nu }$

dónde${\displaystyle \otimes }$es el producto Kronecker ,${\displaystyle 1_{n\times m}}$es una matriz de tamaño${\displaystyle n\times m}$con todas las entradas de unos, y${\displaystyle I_{n}}$es la matriz identidad de tamaño${\displaystyle n}$. Como resultado, establecer${\displaystyle z=\operatorname {vec} (\gamma )}$, la formulación de programación lineal del problema es

${\displaystyle {\begin{aligned}&{\text{Minimize }}&&\operatorname {vec} (c)^{\top }z\\[4pt]&{\text{subject to:}}&&z\geq 0,\\[4pt]&&&{\begin{pmatrix}1_{1\times |\mathbf {Y} |}\otimes I_{|\mathbf {X} |}\\I_{|\mathbf {Y} |}\otimes 1_{1\times |\mathbf {X} |}\end{pmatrix}}z={\binom {\mu }{\nu }}\end{aligned}}}$

que se pueden introducir fácilmente en un solucionador de programación lineal a gran escala (véase el capítulo 3.4 de Galichon (2016) ^{[ 11 ]} ).

En el caso semidiscreto,${\displaystyle X=Y=\mathbb {R} ^{d}}$y${\displaystyle \mu }$es una distribución continua sobre${\displaystyle \mathbb {R} ^{d}}$, mientras${\displaystyle \nu =\sum _{j=1}^{J}\nu _{j}\delta _{y_{i}}}$es una distribución discreta que asigna masa de probabilidad${\displaystyle \nu _{j}}$al sitio${\displaystyle y_{j}\in \mathbb {R} ^{d}}$En este caso, podemos ver ^{[ 14 ]} que los problemas primal y dual de Kantorovich se reducen respectivamente a:

${\displaystyle \inf \left\{\int _{X}\sum _{j=1}^{J}c(x,y_{j})\,d\gamma _{j}(x),\gamma \in \Gamma (\mu ,\nu )\right\}}$

para lo primordial, donde${\displaystyle \gamma \in \Gamma (\mu ,\nu )}$significa que${\displaystyle \int _{X}d\gamma _{j}(x)=\nu _{j}}$y${\displaystyle \sum _{j}d\gamma _{j}(x)=d\mu (x)}$, y:

${\displaystyle \sup \left\{\int _{X}\varphi (x)d\mu (x)+\sum _{j=1}^{J}\psi _{j}\nu _{j}:\psi _{j}+\varphi (x)\leq c(x,y_{j})\right\}}$

para el dual, que se puede reescribir como:

${\displaystyle \sup _{\psi \in \mathbb {R} ^{J}}\left\{\int _{X}\inf _{j}\left\{c(x,y_{j})-\psi _{j}\right\}d\mu (x)+\sum _{j=1}^{J}\psi _{j}\nu _{j}\right\}}$

que es un problema de optimización convexa de dimensión finita que se puede resolver mediante técnicas estándar, como el descenso de gradiente .

En el caso de que${\displaystyle c(x,y)=|x-y|^{2}/2}$, se puede demostrar que el conjunto de${\displaystyle x\in \mathbf {X} }$asignado a un sitio en particular${\displaystyle j}$es un poliedro convexo. La configuración resultante se llama diagrama de potencia . ^{[ 15 ]}

Supongamos el caso particular${\displaystyle \mu ={\mathcal {N}}(0,\Sigma _{X})}$,${\displaystyle \nu ={\mathcal {N}}(0,\Sigma _{Y})}$, y${\displaystyle c(x,y)=|y-Ax|^{2}/2}$dónde${\displaystyle A}$es invertible. Entonces uno tiene

${\displaystyle \varphi (x)=-x^{\top }\Sigma _{X}^{-1/2}\left(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{X}^{1/2}\right)^{1/2}\Sigma _{X}^{-1/2}x/2}$

${\displaystyle \psi (y)=-y^{\top }A\Sigma _{X}^{1/2}\left(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{X}^{1/2}\right)^{-1/2}\Sigma _{X}^{1/2}Ay/2}$

${\displaystyle T(x)=(A^{\top })^{-1}\Sigma _{X}^{-1/2}\left(\Sigma _{X}^{1/2}A^{\top }\Sigma _{Y}A\Sigma _{X}^{1/2}\right)^{1/2}\Sigma _{X}^{-1/2}x}$

La demostración de esta solución aparece en Galichon (2016). ^{[ 11 ]}

Dejar${\displaystyle X}$Sea un espacio de Hilbert separable .${\displaystyle {\mathcal {P}}_{p}(X)}$denotamos el conjunto de medidas de probabilidad en${\displaystyle X}$que tienen finito${\displaystyle p}$-ésimo momento; dejar${\displaystyle {\mathcal {P}}_{p}^{r}(X)}$denotan esos elementos${\displaystyle \mu \in {\mathcal {P}}_{p}(X)}$que son regulares gaussianas : si${\displaystyle g}$es cualquier medida gaussiana estrictamente positiva en${\displaystyle X}$y${\displaystyle g(N)=0}$, entonces${\displaystyle \mu (N)=0}$también.

Dejar${\displaystyle \mu \in {\mathcal {P}}_{p}^{r}(X)}$,${\displaystyle \nu \in {\mathcal {P}}_{p}(X)}$,${\displaystyle c(x,y)=|x-y|^{p}/p}$para${\displaystyle p\in (1,\infty ),p^{-1}+q^{-1}=1}$Entonces, el problema de Kantorovich tiene una solución única.${\displaystyle \kappa }$y esta solución es inducida por un mapa de transporte óptimo: es decir, existe un mapa de Borel.${\displaystyle r\in L^{p}(X,\mu ;X)}$de tal manera que

${\displaystyle \kappa =(\mathrm {id} _{X}\times r)_{*}(\mu )\in \Gamma (\mu ,\nu ).}$

Además, si${\displaystyle \nu }$tiene soporte limitado , entonces

${\displaystyle r(x)=x-|\nabla \varphi (x)|^{q-2}\,\nabla \varphi (x)}$

para${\displaystyle \mu }$-casi todos${\displaystyle x\in X}$para algunos locales Lipschitz ,${\displaystyle c}$Potencial de Kantorovich cóncavo y máximo${\displaystyle \varphi }$. (Aquí${\displaystyle \nabla \varphi }$denota la derivada de Gateaux de${\displaystyle \varphi }$.)

Sigurd Angenent , Steven Haker y Allen Tannenbaum dieron una formulación de descenso de gradiente para la solución del problema de Monge-Kantorovich . ^{[ 16 ]}