Оптимальный транспорт и задача Монжа-Канторовича

Оптимальный транспорт и задача Монжа-Канторовича

Задача о переноске земли

В 1781 году французский математик Гаспар Монж поставил вопрос: как переместить кучу земли (плотность μ) в яму (плотность ν) с минимальными затратами труда? Задача оказалась невероятно сложной и оставалась нерешённой 160 лет. В 1942 году советский математик Леонид Канторович решил расслабленную версию задачи и получил за это Нобелевскую премию по экономике (1975). Сегодня оптимальный транспорт — это центральная математическая теория, лежащая в основе генеративных нейросетей, обработки изображений, медицины и экономической теории. Это прямое дитя вариационного исчисления в бесконечномерных пространствах.

Задача Монжа: строгая формулировка

Даны две меры μ и ν на пространстве X (например, вероятностные распределения на ℝⁿ) и функция стоимости c(x, y) ≥ 0 (стоимость перемещения «единицы материала» из x в y).

Задача Монжа: найти отображение T: X → X («план переноски»), транспортирующее μ в ν (то есть T_#μ = ν — «образ» μ под T равен ν), минимизирующее суммарную стоимость:

min_T ∫_X c(x, T(x)) dμ(x)

Проблема формулировки Монжа: отображение T — это «детерминированный» план, но иногда оптимально «расщепить» единицу материала. Например, часть земли с места x₁ идёт в яму y₁, часть — в y₂. Монжевский план этого не допускает.

Формулировка Канторовича

Канторович расширил задачу, рассматривая «вероятностные планы» — совместные меры γ(x,y):

min_{γ ∈ Π(μ,ν)} ∫_{X×X} c(x, y) dγ(x, y)

где Π(μ,ν) = {γ : маргинали γ по x и y равны μ и ν соответственно}.

Ключевые свойства:

• Задача Канторовича — линейная по γ (бесконечномерное ЛП!)
• Всегда имеет решение (при разумных условиях на c и μ, ν)
• Задача Монжа — частный случай: γ сосредоточена на графике T

Двойственная задача Канторовича: по теореме двойственности ЛП:

max ∫u(x) dμ(x) + ∫v(y) dν(y) при условии u(x) + v(y) ≤ c(x,y) для всех x,y

Сильная двойственность выполнена: inf = sup.

Расстояние Вассерштейна

W_p-расстояние между вероятностными мерами μ, ν:

W_p(μ, ν) = (min_{γ ∈ Π(μ,ν)} ∫|x−y|^p dγ)^{1/p}

при c(x,y) = |x−y|^p.

Свойства: W_p — настоящая метрика на пространстве вероятностных мер. Сходимость по W_p эквивалентна слабой сходимости + сходимости p-момента.

Пространство Вассерштейна: P_p(ℝⁿ) с метрикой W_p — «пространство форм». Интерполяция между μ и ν по W₂ — это «оптимальный морфинг» между двумя распределениями.

Теорема Брейера-МакКана

Теорема (при c(x,y) = |x−y|²/2, μ абсолютно непрерывна): существует единственное оптимальное отображение T = ∇φ, где φ — выпуклая функция.

Смысл: оптимальный план транспортировки — это «сдвиг вдоль градиента выпуклой функции». Это поразительно: из задачи переноски земли возникает выпуклость!

Полярное разложение Брейера-МакКана: любое отображение T: ℝⁿ → ℝⁿ, сохраняющее меры (T_#μ = ν), разлагается в T = R ∘ ∇φ, где R — поворот (сохраняет расстояние), ∇φ — оптимальный транспорт.

Применения в машинном обучении

WGAN (Wasserstein GAN): обучение генеративных нейросетей. Обычный GAN использует KL-дивергенцию, которая нестабильна при непересекающихся распределениях. WGAN заменяет на W₁:

L(G, D) = W₁(μ_real, μ_G) ≈ max_‖D‖Lip≤1 E{xμ_real}[D(x)] − E_{xμ_G}[D(x)]

Более стабильное обучение, нет mode collapse.

Сопоставление точек (Point Cloud Matching): сопоставить два набора точек {xᵢ} ~ μ и {yⱼ} ~ ν с минимальными затратами. Алгоритм Sinkhorn — быстрый итерационный метод для приближённого решения задачи Канторовича с энтропийной регуляризацией.

Morph между изображениями: усреднение изображений в пространстве Вассерштейна. Барицентр Вассерштейна: min_{ν} Σᵢ wᵢ W₂²(μᵢ, ν). Результат — «средний» образ, сохраняющий геометрию.

Полный разбор: транспортный план в ℝ

Задача: μ = 0.5 δ₀ + 0.5 δ₂ (масса 0.5 в точках 0 и 2), ν = 0.5 δ₁ + 0.5 δ₃ (масса 0.5 в точках 1 и 3). Стоимость c(x,y) = |x−y|².

Допустимые планы: γ задаётся матрицей 2×2 с суммами строк (0.5, 0.5) и столбцов (0.5, 0.5):

γ = [[a, 0.5−a], [0.5−a, a]], a ∈ [0, 0.5].

Стоимость: C(γ) = a|0−1|² + (0.5−a)|0−3|² + (0.5−a)|2−1|² + a|2−3|² = a + 9(0.5−a) + (0.5−a) + a = 4.5 − 8a.

Минимум при a = 0.5: γ = [[0.5, 0], [0, 0.5]] — «монжевский план»: 0→1, 2→3. Стоимость = 0.5. Оптимум!

W₂: √C = √0.5 ≈ 0.707.