Teoría de Transporte Óptimo

Las notas

Un curso de un cuatrimestre sobre transporte óptimo, desde el problema de Monge y la relajación de Kantorovich hasta el teorema de Brenier, las distancias de Wasserstein, los baricentros y el transporte entrópico. Están pensadas para estudiantes avanzados de licenciatura y de doctorado en matemática; se asume análisis real y algo de teoría de la medida (repasada en el Apéndice A). Cada capítulo termina con una sección de ejercicios; seis de ellos incluyen además ejercicios computacionales que se resuelven con los cuadernos de más abajo.

Notas completas (PDF, 194 páginas) Todas las guías Sugerencias para los ejercicios Fuentes LaTeX

Capítulos

Capítulo 1

Introducción

El problema de Monge y su relajación de Kantorovich: mapas y planes de transporte, el caso discreto (asignación y matrices biestocásticas), el push-forward y la formulación en espacios de medida.

notas · guía

Capítulo 2

Existencia de planes óptimos

Convergencia débil de medidas, compacidad de los planes (Prokhorov) y existencia de planes óptimos para costos semicontinuos inferiormente.

notas · guía · cuaderno

Capítulo 3

Un breve repaso de dualidad en Programación Lineal

Lo esencial de la dualidad en programación lineal: dual, dualidad débil y fuerte, holgura complementaria.

notas · guía

Capítulo 4

Dualidad

El problema dual de Kantorovich, dualidad débil y la demostración de la dualidad fuerte vía Fenchel–Rockafellar.

notas · guía

Capítulo 5

Potenciales de Kantorovich en el caso discreto

Potenciales de Kantorovich en el caso discreto: existencia, relación con el soporte de los planes óptimos y ejemplos con potenciales no únicos.

notas · guía

Capítulo 6

Potenciales de Kantorovich

La c-transformada, existencia de potenciales de Kantorovich, caracterización del soporte de los planes óptimos y el costo cuadrático vía Legendre.

notas · guía · cuaderno

Capítulo 7

Algunas interpretaciones y extensiones

Acoplamientos y copulas, matching estable, transporte multimarginal y estabilidad de los planes bajo discretización.

notas · guía

Capítulo 8

Transporte óptimo en dimensión uno

Función de distribución y pseudoinversa, el mapa monótono, c-monotonicidad cíclica y optimalidad del plan monótono para costos convexos; fórmula del costo óptimo.

notas · guía · cuaderno

Capítulo 9

El teorema de factorización polar de Brenier

El teorema de Brenier: para el costo cuadrático el plan óptimo es el gradiente de una función convexa; factorización polar.

notas · guía

Capítulo 10

Distancias de Wasserstein

Las distancias Wₚ en Pₚ: desigualdad triangular vía pegado, metrización de la convergencia débil, Kantorovich–Rubinstein y geodésicas.

notas · guía · cuaderno

Capítulo 11

La desigualdad de Brunn–Minkowski

Una demostración de la desigualdad de Brunn–Minkowski con transporte óptimo.

notas · guía

Capítulo 12

Baricentros de Wasserstein

Baricentros de Wasserstein: existencia, convexidad y unicidad, criterio de optimalidad, formulación multimarginal y los casos explícitos (dimensión uno, gaussianas).

notas · guía · cuaderno

Capítulo 13

Transporte entrópico y el algoritmo de Sinkhorn

Regularización entrópica, dualidad entrópica, el algoritmo de Sinkhorn y su convergencia, límites en ε y baricentros entrópicos.

notas · guía · cuaderno

Apéndice A

Complementos de teoría de la medida

Repaso de teoría de la medida, desintegración de medidas y el lema de pegado.

notas · guía

Apéndice B

El teorema de Fenchel–Rockafellar

El teorema de Fenchel–Rockafellar.

notas · guía

Apéndice C

Factorización polar de matrices inversibles

Factorización polar de matrices inversibles.

notas · guía

Apéndice D

Subdiferencial de funciones convexas

Subdiferencial de funciones convexas y teorema de Rademacher.

notas · guía

Cuadernos de cómputo

Seis cuadernos de Python que acompañan las notas, con la biblioteca POT. No requieren instalar nada: el botón abre una copia en Google Colab (hace falta una cuenta de Google para ejecutarla). Cada cuaderno termina con los ejercicios computacionales del capítulo correspondiente.

Monge y Kantorovich

Capítulos 1–2

Planes discretos con POT, mapas y planes en dimensión uno, asignación y Birkhoff, costos cóncavos, convergencia débil de planes.

Abrir en Colab descargar .ipynb

Dualidad

Capítulos 3–6

Duales con linprog, potenciales de Kantorovich, holgura complementaria, mejora de potenciales, costo 0–1.

Abrir en Colab descargar .ipynb

OT en dimensión uno

Capítulo 8

Pseudoinversas, el mapa monótono, planes con átomos, fórmula del costo óptimo, plan antimonótono.

Abrir en Colab descargar .ipynb

Distancias de Wasserstein

Capítulo 10

Wₚ entre muestras, comparación con otras métricas, geodésicas e interpolación, Kantorovich–Rubinstein.

Abrir en Colab descargar .ipynb

Baricentros de Wasserstein

Capítulo 12

Baricentros en dimensión uno, de gaussianas y de medidas discretas; formulación multimarginal.

Abrir en Colab descargar .ipynb

Transporte entrópico y Sinkhorn

Capítulo 13

Planes entrópicos, Sinkhorn en versión escalada y en el dominio logarítmico, límites en ε, baricentros entrópicos de formas.

Abrir en Colab descargar .ipynb

Cómo usar el material

Para estudiar por cuenta propia, el orden natural es el de los capítulos: leer el capítulo, hacer la guía, y en los capítulos que lo tienen, trabajar el cuaderno. Las guías son exactamente las secciones de ejercicios de las notas, con la misma numeración, generadas desde el mismo archivo fuente; las referencias a teoremas y proposiciones remiten a las notas. El archivo de sugerencias reúne, para los ejercicios de todos los capítulos, una idea o el resultado que conviene usar, sin resolverlos.

Correcciones y sugerencias: abrir un issue o un pull request en el repositorio, o escribir a jfbonder@dm.uba.ar.