Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков

Подождите немного. Документ загружается.

А. В. Колесников

Транспортная задача и концентрация

Первые результаты о концентрации были получены П. Леви в

его книге по функциональному анализу [10]. Само название «кон-

центрация мер» было предложено В. Мильманом. Благодаря ему

же явление концентрации приобрело большую популярность в ма-

тематическом сообществе и нашло многочисленные при ложения в

функциональном анализе, геометрии, вероятности, комбинаторике

и технических науках.

Среди сугубо математических приложений упомянем: 1) новое

доказательство теоремы Дворецкого о «почти круглых» сечениях

выпуклых тел, 2) изопериметрические теоремы сравнения М. Гро-

мова для многообразий положительной кривизны Риччи, 3) прило-

жения в теории гауссовских случайных процессов (например, оцен-

ки статистического супремума), 4) применения к другим функци-

ональным и вероятностным неравенствам (неравенства типа Собо-

лева, неравенства типа Брунна—Минковского для выпуклых тел и

т.п.). Подробнее об этом можно узнать в книгах [2; 7–9]. О вероят-

ностных приложениях см. статью [11]. Для ознакомления с недавни-

ми результатами о концентрации и функциональных неравенст вах

для логарифмически вогнутых распределений также рекомендуем

статью [13]. Теоремы о концентрации также позволяют оценить ско-

рость сходимости системы к равновесному состоянию (см. коммен-

тарий ниже и приложение Е. В. Гасниковой настоящего пособия).

Классический пример свойства концентрации дает стандартное

нормальное (гауссовское) d-мерное распределение γ. Как известно,

плотность такого распределения задается формулой

(x) =

(2π)

d/2

exp



−

|x|



Для произвольного множества A со свойством γ(A) >

рассмот-

рим его r-окрестность:

= {x : ∃y ∈ A : |x − y| ≤ r}.

288

Тогда выполнено следующее неравенство концентрации:

γ(A

) ≥ 1 −

−

. (1)

Как мы видим, P (A

) очень быстро (квадратично экспоненциально)

стремится к единице.

Равномерное распределение σ на единичной сфере S

d−1

⊂ R

также обладает аналогичным свойством:

σ(A

) ≥ 1 −





−d

. (2)

Одно из важных следствий неравенств такого типа — неравен-

ства для колебаний липши цевых функций. Пусть f — 1-липшицева

функция, т.е. удовлетворяющая соотношению |f(x) − f(y)| ≤ |x − y|.

Используя формулу коплощади

g(x) dγ =

∞

−∞

γ({g > t}) dt,

из (1) можно получить неравенство вида



{x : f(x) −

f dγ > t}



≤ 2e

−ct

для некоторой универсальной константы c. Полученное свойство

обычно формулируется в виде «липшицевы функции с большой до-

лей вероятности мало отличаются от своего среднего значения».

Несмотря на простой вид, доказательство (1) нетривиально. Клас-

сический способ основан на описании так называемых «изоперимет-

рических множеств» — множеств, имеющих наименьшую границу

среди множеств такой же меры (вероятности). В евклидовом про-

странстве таким, как известно, является шар. На сфере их роль вы-

полняют сферические «шары», а в пространстве, наделенном гаус-

совым распределением, — полупространства {x : hx, ai < c}, a ∈ R

c ∈ R. Это — хорошо известный в теории вероятностей результат,

доказанный В. Судаковым и Б. Цирельсоном (и независимо от них

K. Бореллем, см. [1]). Из того факта, что r-окрестности полупро-

странств являются полупространствами (т.е. опять изопериметри-

ческими множествами), несложно извлечь следствие, что функция

289

r 7→ F (A, r) = γ(A

) среди всех множеств фиксированной вероятно-

сти p растет медленнее всего для изопериметрического A. Для этого

множества функция F (A, r) явно вычисляется, и мы получаем (1).

Указанный способ плох тем, что явно найти изопериметрические

множества в более общем случае невозможно. Существует несколько

подходов к доказательству неравенства концентрации. В настоящем

пособии мы опишем связь явления концентрации с транспортной за-

дачей, возникшей и развившейся в совершенно другой области ма-

тематики. Связь эта была найдена в работе К. Мартон [12].

Транспортная задача ведет свою историю от классической рабо-

ты Г. Монжа [14], написанной в 1781 году. В этой работе задача была

сформулирована следующим образом: имеется куча песка и яма оди-

наковых объемов. Как засыпать песком яму, потратив наименьшие

усилия на перевозку? Конечно, это не единственная возможная «эко-

номическая» формулировка транспортной задачи. Речь, например,

может идти о перевозе грузов со складов по заданным адресам.

В дискретной постановке мы имеем набор точек {x

}, 1 ≤ i ≤ N.

Задано N других точек {y

} и фукция стоимости c(x, y) (напри-

мер, расстояние или квадрат расстояния). Как построить взаимно-

однозначное отображение T , сопоставляющее каждой точке из пер-

вого набора точку из второго набора, так, чтобы суммарная стои-

мость

i=1

c(x

, y

) была наименьшей?

В дальнейшем транспортная задача переживала как периоды за-

бвения, так и бурного развития. На языке современной математики

транспортная задача была переформулирована и решена Л. Канто-

ровичем в 40-х годах XX-го века (см. [3]) и получила в дальнейшем

название задачи Монжа—Канторовича. Важным шагом в работах

Канторовича было применение развитого им в теории линейного

программирования метода двойственности и формулировка транс-

портной задачи на языке теории меры и функционального анализа.

О приложениях двойственности и задач типа транспортной в техни-

ческих науках см., например, главу 2 и п риложени е Е. В. Гасниковой

настоящего пособия.

Пусть задана пара вероятностных распределений µ и ν на про-

странствах X = Y = R

. Решением задачи Монжа—Канторовича

называется распределение m на R

, удовлетворяющее следующим

условиям:

290

1. Проекции m на X и Y равны соответственно µ и ν:

m = µ, pr

m = ν. (3)

2. Распределение m реализует миним ум следующего функциона-

ла:

F(m) : m →

X×Y

c(x, y) dm,

где c : X ×Y → R — некоторая функция, называемая функцией

стоимости (cost function).

При весьма общих предположениях задача Монжа—Канторовича

имеет решение.

В дальнейшем мы будем интересоваться только случаем c(x, y) =

= |x − y|

Обратим теперь внимание на важное отличие задачи Монжа—

Канторовича от исходной задачи Монжа. В задаче Монжа речь идет

о перевозе груза, что на математическом языке соответствует задаче

существования отображения T : X → Y , преобразующего распре-

деление µ в распределение ν (последнее означает, что ν(A) = µ({x :

T (x) ∈ A}) и реализующего минимум функционала

(µ, ν) =

|x − T (x)|

dµ.

Оказывается, что при весьма общих условиях (например, распре-

деления µ и ν непрерывны) эти задачи эк вивалентны. Если m —

решение задачи Монжа—Канторовича, то m сосредоточено на гра-

фике некоторого отображения T : m{(x, y) : y = T (x)} = 1. Мы будем

называть T оптимальным отображением. Существование T было до-

казано Я. Бренье в [5]. Более того, имеет место следующий удиви-

тельный факт.

Теорема 1. T имеет вид

T (x) = ∇ϕ(x),

где ϕ — некоторая выпуклая функция.

Величина

(µ, ν) =

|x − T (x)|

dµ

291

называется расстоянием Канторовича (также можно встретить на-

звания «расстояние Канторовича—Рубинштейна» и «расстояние Ва-

серштейна»). Действительно, можно проверить, что W

(µ, ν) явля-

ется расстоянием на пространстве вероятностных распределений.

Пусть теперь распределения µ и ν заданы п лотностями µ = ρ

dx,

ν = ρ

dx. Свойство T отображать µ в ν аналитически записывается

с помощью формулы замены переменной:

(∇ϕ) det D

ϕ = ρ

Под D

ϕ = D(∇ϕ) подразумевается матрица вторых производных

(гессиан) функции ϕ.

Сделаем важное техническое замечание. Выполнено очевидное

тождество

|x − y|

dm =

|x|

dµ − 2

hx, yidm +

|y|

dν.

Поэтому поиск минимума функционала

|x −y|

dm эквивалентен

поиску максимума функционала

hx, yi dm.

Существование ϕ может быть доказано разными способами. Стан-

дартный подход состоит в применении метода двойственности Кан-

торовича и работе с так называемыми циклически монотонными

множествами. При этом выпуклость ϕ получается автоматически.

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

Φ(x) dµ +

Ψ(y) dν → max,

где функционал максимизируется среди функций, удовлетворяющих

условию Φ(x) + Ψ(y) ≤ |x − y|

. Отображение T связано с Φ следую-

щим образом: T (x) = x − ∇Φ(x) (см. подробнее гл. 1, [16]).

Формальное, но поучительное доказательство того факта, что

T является градиентом, можно получить путем вывода уравнения

Эйлера—Лагранжа (см. [6]). Пусть T — произвольное отображение

из µ в ν. Решение задачи Монжа—Канторовича можно искать, как

условный экстремум функционала

hT (x), xidµ

292

при условии ρ

(T ) det DT = ρ

. Составим функционал Лагранжа:



hT (x), xiρ

+ λ(x)(ρ

(T ) det DT − ρ

)



dx.

Функция λ играет роль множителя Лагранжа. Чтобы найти первую

вариацию функционала Лагранжа, рассмотрим инфинитезимальную

вариацию

(x) = T (x) + εω(x)

отображения T . Здесь ω — гладкое векторное поле с компактным

носителем. Очевидно,

) ≈ ρ

(T ) + εhω, ∇ρ

(T )i.

Можно проверить, что

det(DT + εDω) = det DT · det(I + ε(DT )

−1

Dω) ≈

≈ det DT



1 + εTr



−1

· Dω





Таким образом, первая вариация функционала Лагранжа равна



hω(x), xiρ

+ λ(x) · ρ

(T )Tr



−1

Dω



+ λ(x)h∇ρ

(T ), ωi

(T )



dx.

Заметим, что div(ω(T

−1

)) = TrD



ω(T

−1

)



= Tr



−1

Dω



−1

Интегрируя по частям и применяя замену переменных, несложно

убедиться в том, что

λ(x) · Tr



−1

· Dω



dx =

λ(T

−1

)div(ω(T

−1

))ρ

dx =

= −

h∇



λ(T

−1

)



, ω(T

−1

)iρ

dx −

λ(T

−1

)



ω(T

−1

)),

∇ρ



dx.

Следовательно, вариация равна



hω(x), xiρ

−

h∇



λ(T

−1

)



, ω(T

−1

)iρ

dx = 0.

293

Пусть λ = u(T ), где u — некоторая функция. Применяя опять

формулу замены переменных, получаем, что для любого гладког о

поля ω выполнено



hω(x), xi − h∇u(T ), ω(x) i



dx = 0.

Следовательно:

∇u(T ) = x =⇒ T

−1

= ∇u.

Таким образом, T

−1

= ∇u. В силу симметричности задачи относи-

тельно µ и ν то же утверждение можно сделать для самого отобра-

жения T .

Пусть ν — некоторое вероятностное распределение. Энтропией

вероятностного распределения g · ν относительно ν называется вели-

чина Ent

(g) =

g log g dν (мы считаем, что функция x log x равна

нулю в точке 0).

Следующий результат, доказанный М. Талаграном [15], связыва-

ет теорию оптимальной транспортировки с функцинальными нера-

венствами.

Теорема 2. Пусть µ = γ — стандартное гауссовское распределе-

ние. Предположим, что ν = g · γ — другое вероятностное распреде-

ление. Тогда квадрат расстояния Канторовича между этими рас-

пределениями оценивается относительной энтропией g:

(γ, g · γ) ≤

g · log g dγ := Ent

(g).

Доказательство. Для простоты изложения предположим, что g и

ϕ — гладкие функции (это бывает не всегда, но общий случай можно

свести к этому). Рассмотрим формулу замены переменной:

−

= g(∇ϕ)e

−

|∇ϕ|

det D

ϕ.

Прологарифмируем это соотношение:

−

= log g(∇ϕ) −

|∇ϕ|

+ log detD

ϕ.

Перепишем его в виде

|x − ∇ϕ|

= hx, x − ∇ϕi + log g(∇ϕ) + log detD

ϕ.

294

Проинтегрируем полученное неравенство по γ. Заметим, что

∇e

−

= −xe

−

. Из формулы интегрирования по частям следует:

hx, x − ∇ϕi dγ =



d − TrD



dγ

(напомним, что d — размерность). Следовательно,

|x−∇ϕ|

dγ +



TrD

ϕ−d−log det D



dγ ≤

log g(∇ϕ)dγ.

Заметим теперь, что

TrD

ϕ − d − log det D

ϕ ≥ 0.

Действительно, если λ

— собственные значения матрицы D

ϕ, то

TrD

ϕ − d − log det D

ϕ =

i=1

− 1 − log det λ

≥ 0

(в силу неотрицательности функции x − 1 − ln x). Таким образом,

получаем

|x − ∇ϕ|

dγ ≤

log g(∇ϕ)dγ =

g log g dγ.

Теорема 3 (К. Мартон). Если вероятностное распределение µ

удовлетворяет неравенству Талаграна:

(µ, g · µ) ≤ C

g · log g dµ,

то µ удовлетворяет неравенству гауссовской концентрации:

µ(A

) ≥ 1 − 2e

−

, µ(A) ≥

. (4)

В частности, неравенству гауссовской концентрации удовлетворя-

ет гауссовское распределение.

295

Доказательство. Положим (A

)

= R

. Рассмотрим оптималь-

ную транспортировку ∇ϕ вероятностного распределения µ

µ(A)

×I

· µ в вероятностное распределение µ

µ((A

)

· µ. В силу

того, что расстояние между носителями µ

, µ

превосходит r, имеем

(µ

, µ

) ≥ r. В силу неравенства треугольника (напомним, что W

— расстояние):

r ≤ W

(µ

, µ

) ≤ W

(µ

, µ) + W

(µ

, µ).

По неравенству Талаграна

r ≤

2CEnt

Так как Ent

= log

µ(A)

, Ent

= log

µ((A

)

, немедленно полу-

чаем

≤ log

µ(A)

+ log

µ((A

)

Следовательно,

µ((A

)

) ≤ 2e

−

Остается заметить, что µ((A

)

) = 1 − µ (A

). Теорема доказана.

Несложно проверить, что приведенн ые выше аргументы приме-

нимы к случаю распределения с плотностью e

−V

, где D

V ≥ K · Id,

K > 0 (неравенство понимается в матричном смысле , эквивалент-

ная формулировка: hD

V · v, vi ≥ K для любого вектора v ∈ R

единичной длины). В этом случае также получаем гауссовскую кон-

центрацию. Те же самые аргументы работают для сферы или, более

общим образом, для многообразия с ограниченным снизу тензором

Риччи.

Напоследок кратко обсудим еще одно приложени е транспортной

задачи — оценку скорости сходимости к равновесному состоянию.

Пусть V — равномерно выпуклый потенциал:

V ≥ K · Id, K > 0.

Рассмотрим решение уравнения Фоккера—Планка:

∂µ

∂t

= ∆µ

+ div(∇V · µ

296

= ρ

dx — вероятностное распределение. Оказывается, для двух

решений этого уравнения выполнено неравенство

(µ

, ν

) ≤ −2K · W

(µ

, ν

)

(см. [16], пример 9.10). Это можно проверить, непосредственно про-

дифференцировав расстояние Канторовича п о параметру t. Очевид-

но, эта оценка дает экспоненциальную скорость сходимости µ

к рав-

новесному распределению:

(µ

, ν

) ≤ W

(µ

, ν

−Kt

Приложения такого рода включают в себя широкий класс уравнений,

являющихся градиентными потоками относительно метрики Канто-

ровича. Подробнее об этом см. в [4].

297