Задача Монжа-Канторовича с линейными ограничениями Заев Данила Андреевич

Содержание к диссертации

Введение

Глава 1. Задача Канторовича с ограничениями общего вида 12

1.1 Формулировка задачи с дополнительными ограничениями 16

1.2 Двойственность Канторовича

1.2.1 Двойственность для задачи Канторовича с ограничениями 21

1.2.2 Двойственность в классической задаче Канторовича

1.3 Носитель оптимального транспортного плана в задаче с ограничениями 28

1.4 Мартингальная задача 32

Глава 2. Инвариантная задача Монжа—Канторовича 35

2.1 Инвариантная задача Канторовича 35

2.2 Случай компактной группы симметрии 41

2.3 Инвариантная задача Монжа 46

2.4 Инвариантное расстояние Канторовича 49

Глава 3. Эргодические разложения и задача Канторовича 53

3.1 Симплексы распределений и дезинтегрирование 58

3.2 Геометрические свойства дополнительных линейных ограничений 65

3.3 О некоторых вопросах измеримости 73

3.4 Эргодическое разложение задачи Канторовича 77

3.5 Эргодическое разложение инвариантных метрик Канторовича 81

Глава 4. Инвариантная задача Монжа—Канторовича на бесконечномерных пространствах 83

4.1 Типы симметрии на пространствах последовательностей 86

4.1.1 Перестановочные вероятностные распределения 86

4.1.2 Сферически-инвариантные вероятностные распределения

4.2 Транспортировка мер на гильбертовых пространствах 88

4.3 Транспортировка перестановочных вероятностных распределений з

4.4 Характеризация равномерно логарифмически вогнутых

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

Заключение 98

Список литературы

• Двойственность Канторовича
• Случай компактной группы симметрии
• Геометрические свойства дополнительных линейных ограничений
• Сферически-инвариантные вероятностные распределения

Введение к работе

Актуальность темы и степень ее разработанности. Задача Мон-жа- Канторовича, или задача об оптимальной транспортировке вероятностных мер, в последние два десятилетия пользуется большим вниманием специалистов из различных областей математики: теории вероятностей, анализа, геометрии, теории динамических систем. Помимо чисто теоретических задач, возникающих на стыке различных областей математики, развитие теории Монжа-Канторовича стимулируется многочисленными приложениями, включающими модели статистической физики, финансовых рынков, динамики жидкостей. Кроме того, задача представляет заметный интерес для экономических и технических приложений.

Базовые результаты транспортной теории были получены Л.В. Канторовичем в 1940-е годы. Задача оптимальной транспортировки интенсивно развивалась во второй половине XX - начале XXI века в работах В.Н. Судакова, С. Виллани, Л. Амброзио, A.M. Вершика и других крупных ученых. Современная формулировка (которую уместно называть «задачей Канторовича») была предложена Канторовичем¹. Он рассмотрел задачу нахождения вероятностного распределения на прямом произведении двух пространств с фиксированными проекциями (маргиналами), минимизирующего некоторый линейный функционал. Используя линейность задачи и свои результаты в теории линейного программирования, Канторович нашел достаточные условия существования решения и сформулировал фундаментальный принцип двойственности.

Важно отметить, что рассматриваемая Канторовичем задача тесно связана с классической (нелинейной) задачей о перемещении масс, предложенной Г. Монжем² в 1781 году (задача Монжа): имеются куча песка и яма одинаковых объемов. Как засыпать песком яму, потратив наименьшие усилия на транспортировку массы? В формулировке Канторовича фиксированные маргиналы — распределение куч песка и ям на плоскости, а оптимальное вероятностное распределение — обобщение понятия транспортировки, называемое транспортным планом. Известно, что на К^га в довольно общей ситуации решение задачи Канторовича является решением в смысле Монжа: оно сосредоточено на графике некоторого отображения.

В современных работах задача Монжа-Канторовича обычно рассматривается в весьма общей постановке: пространства, на которых определены маргинальные распределения, предполагаются польскими (полными сепарабельными метрическими), а функция стоимости, задающая критерий оптимальности — полунепрерывной снизу или даже боре-

¹Канторович Л. В. О перемещении масс // Зап. научи, сем. ПОМИ. 2004. Т. 312, № XI. С. 11—14. ² Моще G. Memoire sur la theorie des deblais et de remblais // Memoires de Mathematique et de Physique. 1781.

левской (см., например, работу В.Л. Левина и А.А. Милютина³, а также обзор В.И. Бога-чева и А.В. Колесникова⁴).

Задача Канторовича формулируется следующим образом. Найти минимум функционала

7г —> / c{x,y)dn, (1)

JxxY

на множестве П(/і,и) вероятностных распределений на X х Y с фиксированными маргиналами:

(РГ_Х)_#7Г = /1, (Ргу)_#7Г = V.

Здесь с : XxY — функция, называемая функцией стоимости. Элементы множества П(/і,и) называют транспортными планами. Измеримые отображения Т : X —> Y со свойством T#(j, = v называют транспортными отображениями или транспортировками. Задача Канторовича заключается в поиске оптимального транспортного плана, а задача Монжа — в поиске оптимального транспортного отображения. Классический принцип двойственности утверждает, что минимум в задаче (1) совпадает с супремумом функционала

J(<*pd(j, + / ipdv,
Jx Jy

который ищется на парах функций ((p(x),if)(y)), удовлетворяющих ограничению <р(х) = Ф(у) < ^с(^х,у)- Носитель распределения 7г характеризуется, как правило, важным геометрическим свойством циклической монотонности, из которого в ряде случаев можно вывести, что решение задачи Канторовича однозначно определяет решение задачи Монжа.

В такой постановке задача оказывается связанной со многими приложениями, например с геометрией метрических пространств (Л. Амброзио⁵, С. Виллани⁶), гидродинамикой (Я. Бренье⁷), динамическими системами (A.M. Вершик⁸), статистический физикой (Р. Л. Добрушин⁹), теорией марковских цепей (Я. Оливье¹⁰). Обширные вероятностные приложения представлены в книгах СТ. Рачева и Л. Рюшендорфа¹¹, а также Д. Бакри,

³Левин В. Л., Милютин А. А. Задача о перемещении масс с разрывной функцией стоимости и массовая постановка проблемы двойственности выпуклых экстремальных задач // УМЫ. 1979. Т. 34, 3(207). С. 3— 68.

⁴Богачев В. И., Колесников А. В. Задача Монжа-Канторовича: достижения, связи и перспективы // УМН. 2012. Т. 67, № 5. С. 3-110.

⁵Ambrosio L., Gigli N. A user's guide to optimal transport // Modelling and Optimisation of Flows on Networks. Lecture Notes in Math. 2013. Vol. 2062, no. 5. Pp. 1-155.

^e Villani C. Optimal transport, old and new. Berlin : Springer-Verlag, 2009. (Grundlehren der Mathematis-chen Wissenschaften).

⁷ В renter Y. Connections between optimal transport, combinatorial optimization and hydrodynamics // ESAIM: Mathematical Modelling and Numerical Analysis. 2015. Vol. 49, no. 6. Pp. 1593-1605.

⁸Вершик A. M. Метрика Канторовича: начальная история и малоизвестные применения // Зап. научн. сем. ПОМИ. 2004. Т. 312. С. 69-85.

⁹Добрушин Р. Л. Задание системы случайных величин при помощи условных распределений // ТВП. 1970. Т. 15, № 3. С. 469-497. ¹⁰ Olivier Y. jl Ricci curvature of Markov chains on metric spaces. 2009. Vol. 256, no. 3. Pp. 810-864. ¹¹Rachev S. Т., Ruschendorf L. Mass transportation problems, Vol.1: Theory, Vol. II: Applications. Springer-Verlag, 1998. (Probability and its applications).

И. Жантиля и М. Леду . В последней книге продемонстрирована тесная взаимосвязь вероятностных и аналитических задач, где техника транспортной задачи выступает одним из главных инструментов изучения неравенств концентрации, неравенств Соболева, энтропийных оценок.

Имеются важные ситуации, когда вместо стандартной транспортной задачи имеет смысл рассматривать ее некоторые модификации. Одной из такой модификаций является ее инвариантный аналог. В этом случае мы рассматриваем некую группу преобразований пространств, действующую на них непрерывно (или, более общим образом, измеримо). Фиксированные маргинальные распределения предполагаются инвариантными относительно действия этой группы, а поиск оптимального решения производится только среди инвариантных транспортных планов. Для задачи в такой постановке известны лишь частичные результаты: например, подробно исследован случай, когда функция стоимости также инвариантна (А. Моамени¹³). Однако такие вопросы, как формулировка двойственной задачи Канторовича, связь между задачей Монжа и Канторовича (когда решение задачи Канторовича будет решением задачи Монжа?), свойство циклической монотонности, взаимосвязь между эргодичностью решения и его оптимальностью представляют большой интерес для исследования. Достаточные условия существования решения инвариантной задачи Монжа не столь очевидны, как для инвариантной задачи Канторовича и тесно связаны с теорией эргодических разложений и изучением структуры крайних точек бистохастических распределений (A.M. Вершик¹⁴, В.Н. Судаков¹⁵, Р. МакКэн¹⁶). Среди потенциальных приложений отметим теорию случайных процессов (в частности, стационарных, Л. Рюшендорф¹⁷), теорию мер на графах (A.M. Вершик¹⁸).

Отметим, что исследования по бесконечномерной задаче Монжа-Канторовича мотивированы, в частности, задачами анализа на пространстве Винера (В.И. Богачев и

¹²Bakry D., Gentil I., Ledoux М. Analysis and geometry of Markov diffusion operators. Vol. 348. Springer International Publishing, 2014. (Grundlehren der mathematischen Wissenschaften).

¹³Moameni A. Invariance properties of the Monge-Kantorovich mass transport problem // Dis. Cont. Dyn. Sys. 2016. Vol. 36, no. 5. Pp. 2653-2671.

¹⁴Вершик A. M. Задача о центральных мерах на пространствах путей градуированных графов // Функц. анализ и его прил. 2014. Т. 48, № 4. С. 26—46.

¹⁵ Судаков В. Н. Геометрические проблемы теории бесконечномерных вероятностных распределений //
Тр. МИАН СССР. 1976. Т. 141. С. 3-191.

¹⁶ Chiappori P., McCann R., Nesheim L. P. Invariance properties of the Monge-Kantorovich mass transport
problem // Econ Theory. 2010. Vol. 42, issue 2. Pp. 317-354.

¹⁷Riischendorf L., Sei T. On optimal stationary couplings between stationary processes // Electron. .1. Probab. 2012. Vol. 17, no. 17.

¹⁸Вершик A. M. Оснащенные градуированные графы, проективные пределы симплексов и их границы // Зап. научн. сем. ПОМИ. 2015. № 5. С. 83-104. (432-я сер.)

А.В. Колесников¹⁹, Д. Фейель и А.С. Устюнель²⁰) и теорией диффузионных процессов (Д.Б. Букин²¹). В цитированных работах обычно рассматривались вероятностные распределения, абсолютно непрерывные относительно фиксированного гауссовского распределения и, как правило, в этой ситуации решение задачи Монжа существует и совпадает с решением задачи Канторовича. В этом смысле транспортная задача на пространстве Винера похожа на конечномерную. В настоящей работе развивается подход для принципиально иной, но также естественной для приложений ситуации. В инвариантной задаче Канторовича на бесконечномерных пространствах маргинальные вероятностные распределения, как правило, взаимно сингулярны, а вопрос о существовании решения Монжа очень сложен.

Другая важная модификация задачи связана с моделированием финансовых активов. Фиксированные маргинальные распределения в этом случае можно интерпретировать как распределения стоимости актива в определенные моменты времени, а оптимальный транспортный план — как совместное распределение модельного процесса. В таком случае естественно рассматривать транспортную задачу с конечным (не обязательно равным двум) числом маргиналов. Кроме этого, большинство вероятностных распределений в финансовых моделях являются мартингальными мерами. Поэтому на транспортные планы естественно наложить условие мартингальности, которое также является линейным. Мар-тингальная задача Канторовича изучалась в работах М. Байглбека, В. Шахермайера и соавторов²². Эта задача тесно связана с потраекторными неравенствами для мартингалов, которые естественно интерпретируются как ограничения в задаче, двойственной к мартингальной задаче Канторовича (см., например, Б. Буршар, М. Нутц и др.²³).

Имея в виду два описанных выше примера модификации стандартной задачи Монжа-Канторовича, можно заметить, что в обоих случаях речь идет о наложении дополнительных условий на множество возможных решений, причем математически эти условия

¹⁹Feyel D., Ustunel A. S. Monge-Kantorovich measure transportation and Monge-Ampere equation on Wiener space //Prob. Theory and Related Fields. 2004. Vol.128. Pp. 347-385; Кolesnikov A. V. Convexity inequalities and optimal transport of infinite-dimensional measures // J. Math. Pures Appl. 2004. T. 83, № 11. C. 1373— 1404; Bogachev V. I., Kolesnikov A. V. On the Monge-Ampere equation in infinite dimensions // Infin. Dimen. Anal. Quantum Probab. Related Topics. 2005. Vol. 8, no. 4. Pp. 547-572; Bogachev V. I., Kolesnikov A. V. Sobolev regularity for the Monge-Ampere equation in the Wiener space // Kyoto J. Math. 2013. Vol. 53, no. 4. Pp. 713-738.

²⁰Feyel D., Ustunel A. S. Monge-Kantorovich measure transportation and Monge-Ampere equation on Wiener space // Prob. Theory and Related Fields. 2004. Vol. 128. Pp. 347-385.

²¹Bukin D. B. On the Monge and Kantorovich problems for distributions of diffusion processes // Mathematical Notes. 2014. Vol. 96, no. 5-6. Pp. 864-870.

²²Beiglboeck M., Goldstern M., Maresch G. Optimal and better transport plans // J. Funct. Anal. 2009. Vol. 256, no. 6. Pp. 1907-1927; Beiglboeck M., Leonard C, Schachermayer W. A general duality theorem for the Monge-Kantorovich transport problem // Stud. Math. 2012. Vol. 209, no. 2. Pp. 151-167; Beiglboeck M., Henry-Labordere P., Penkner F. Model-independent bounds for option prices - a mass transport approach // Finance and Stochastics. 2013. Vol. 17, no. 3. Pp. 477-5017; Bouchard В., Nutz M. Arbitrage and duality in nondominated discretetime models // Ann. Appl. Pronbability. 2015. Vol. 25, no. 2. Pp. 823-859; Beiglboeck M., Juillet N. On a problem of optimal transport under marginal martingale constraints // Annals of Probability. 2016. Vol. 44, no. 1. Pp. 42-106.

²³Beiglboeck M., Nutz M. Martingale inequalities and deterministic counterparts // Electron. J. Probab. 2014. Vol. 19, no. 95. Pp. 1-15; Bouchard В., Nutz M. Arbitrage and duality in nondominated discretetime models // Ann. Appl. Pronbability. 2015. Vol. 25, no. 2. Pp. 823-859.

можно описать как линейные бесконечномерные ограничения. Если говорить более точно, мы выделяем некоторое линейное подпространство функций и требуем, чтобы интересующие нас распределения принимали нулевые значения на этом пространстве. Свойства задачи с дополнительными ограничениями такого общего вида есть основной объект изучения в первой главе диссертации.

Прогресс в исследовании задачи с ограничениями общего вида позволяет использовать разработанную теорию для частного случая инвариантной задачи. Ключевая задача в этой области: исследование взаимосвязи эргодичности и оптимальности в смысле Мон-жа- Канторовича. Эта задача уже рассматривалась специалистами в эргодической теории (A.M. Вершик²⁴), однако в третьей главе диссертации предложен альтернативный подход к этому вопросу и описание ряда новых результатов. В доказательстве этих результатов мы опираемся на работы Е.Б. Дынкина²⁵. Основным техническим инструментом здесь является теория симплексов Дынкина (Дж. Керстан и др.²⁶), в рамках которой можно доказать существование эргодических разложений для весьма широкого класса выпуклых множеств в пространстве вероятностных мер.

Если X = Y — достаточно хорошие метрические пространства (например польские), а в качестве функции стоимости рассматривается функция расстояния, то минимум в задаче Канторовича определяет значение функции расстояния на пространстве V(X) вероятностных распределений на X. Такие расстояния называют расстояниями Канторовича. Их свойства хорошо изучены, а число приложений чрезвычайно велико (с ними можно ознакомиться, например, по работе Л. Амброзио с соавторами²⁷ или по книге С. Вил-лани²⁸). Однако на множестве инвариантных вероятностных распределений стандартное расстояние Канторовича не всегда естественно. Поэтому в диссертации вводится понятие инвариантного расстояния Канторовича, учитывающего симметрии, возникающие в модели.

Цели и задачи диссертации. Цель работы состоит в исследовании свойств вероятностных распределений, являющихся решениями задачи Монжа-Канторовича с дополнительными ограничениями линейного типа.

Задачи диссертационного исследования.

1. Сформулировать и доказать принцип двойственности для задачи Канторовича с линейными ограничениями на пространстве вероятностных распределений. Исследовать важные частные случаи, в том числе случай мартингальных распределений и распределений, инвариантных относительно заданной группы преобразований.

²⁴Вершик А. М. Оснащенные градуированные графы, проективные пределы симплексов и их границы // Зап. научн. сем. ПОМИ. 2015. № 5. С. 83-104. (432-я сер.)

²⁵Dynkin Е. В. Sufficient statistics and extreme points // Ann. Probab. 1978. Vol. 6, no. 5. Pp. 705-730.

^2eKerstan J., Wakolbinger A. Ergodic decomposition of probability laws // Zeitschrift fur Wahrscheinlichkeit-stheorie und Verwandte Gebiete. 1981. Vol. 56, no. 3. Pp. 339-414.

²⁷ Ambrosio L., Gigli N., Savari G. Gradient flows in metric spaces and in the Wasserstein spaces of probability
measures. Birkhauser, 2008.

²⁸ Villani C. Optimal transport, old and new. Berlin : Springer-Verlag, 2009. (Grundlehren der Mathematis-
chen Wissenschaften).

1. Исследовать геометрические свойства носителя вероятностного распределения, являющегося решением задачи Канторовича с линейными ограничениями. В частности, исследовать аналоги свойства циклической монотонности (равносильного оптимальности в классической задаче Канторовича без ограничений), их необходимость и достаточность.

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

3. Получить достаточные условия существования оптимальной транспортировки вероятностных распределений на бесконечномерных линейных пространствах в случае распределений, инвариантных относительно заданной группы преобразований. Исследовать классические случаи инвариантности (в частности перестановочные распределения).

Научная новизна. Все представленные на защиту положения являются новыми научными результатами. В частности, впервые исследуется задача Канторовича с линейными ограничениями общего вида, описываются свойства ее решения. Важным новым результатом работы является теорема об эргодическом разложении решения инвариантной задачи Канторовича. С ее помощью доказаны новые факты о задаче Монжа для перестановочных распределений на K^N, а также получена новая характеризация перестановочных равномерно логарифмически вогнутых распределений на K^N.

Положения, выносимые на защиту.

1. В задаче Канторовича с дополнительными линейными ограничениями описан явный вид двойственного функционала на соответствующем пространстве случайных величин. Доказано, что супремум двойственного функционала совпадает с минимумом функционала Канторовича (принцип двойственности). Описаны геометрические свойства носителя решения, в частности доказано, что решение обладает свойством, аналогичным свойству циклической монотонности. Построен контрпример, показывающий, что это свойство недостаточно для оптимальности.

2. Для инвариантной задачи Канторовича с компактной группой симметрии описана специальная форма результата о двойственности на соответствующем пространстве инвариантных случайных величин. На пространстве инвариантных вероятностных распределений введено понятие инвариантного расстояния Канторовича.

3. Исследована связь между эргодическими разложениями инвариантных транспортных планов и их оптимальностью. Доказано, что инвариантную задачу Канторовича можно свести к следующим задачам: инвариантной задаче Канторовича для маргиналов соответствующих эргодических компонент и задаче Канторовича для вероятностных распределений на пространстве эргодических мер.

4. Доказано существование оптимальной транспортировки для некоторых инвариантных вероятностных распределений на бесконечномерных пространствах. Описан явный вид оптимальной транспортировки в случае перестановочных распределений. Доказано, что перестановочная последовательность случайных величин, имеющая равномерно логарифмически вогнутое распределение, является последовательностью независимых одинаково распределенных случайных величин. Методология и методы диссертационного исследования. В диссертации используются методы теории вероятностей, общей теории меры и функционального анализа. Теоретическая и практическая значимость. Диссертация имеет теоретический характер. Полученные в диссертации результаты могут представлять интерес для специалистов в области теории вероятностей, случайных процессов, динамических систем, а также в различных разделах теоретической физики. В частности, задача Монжа для перестановочных распределений на K^N может найти применение в моделях статистической физики, результат об эргодичности перестановочных равномерно логарифмически вогнутых распределений может быть важен при изучении вопросов концентрации мер. Мартингальная задача Канторовича имеет приложения в сфере финансового моделирования, в связи с чем полученные автором результаты могут быть полезны при исследовании существующих финансовых моделей.

Степень достоверности результатов диссертации. Представленные на защиту результаты диссертации представляют собой математические утверждения и сопровождаются строгими доказательствами.

Личный вклад автора. Все представленные результаты получены автором самостоятельно.

Апробация результатов диссертационного исследования. Основные результаты диссертации были представлены автором лично на следующих семинарах и конференциях:

Семинар «Бесконечномерный анализ и стохастика» (МГУ, руководители Бо-гачев В.П., Толмачев Н.А., Шапошников СВ.), 2013. Доклад «Задача Монжа-Канторовича на бесконечномерных линейных пространствах».

Международная конференция "Stochastic processes and high dimensional probability distributions" (Санкт-Петербург), 2014. Доклад: "Monge-Kantorovich problem with additional constraints: infinite-dimensional applications".

Vienna Seminar in Mathematical Finance and Probability (Вена, Австрия), 2014. Доклад: "Monge - Kantorovich problem with additional constraints and its applications".

Международная конференция «Бесконечномерный анализ, стохастика, математическое моделирование» (Москва), 2014. Доклад: «Задача Монжа-Канторовича с линейными ограничениями».

— Семинар Добрушинской математической лаборатории, ИППИ РАН (Москва), 2016. Доклад: «Задача Монжа-Канторовича с линейными ограничениями». Также результаты диссертации многократно докладывались и обсуждались в рамках научно-исследовательского семинара «Теория вероятностей. Экономические и аналитические приложения» (Москва, НИУ ВШЭ, руководители Колесников А.В., Конаков В.Д.) в 2013-2016 годах.

Публикации. Основные результаты по теме диссертации изложены в 3 печатных работах, которые опубликованы в журналах, рекомендованных ВАК. Общий объём публикаций 6.5 п.л., личный вклад автора составляет 6 п.л. Список публикаций приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Главы разбиты на параграфы. Общий объем диссертации составляет 105 страниц. Список литературы включает 61 наименование.

Двойственность Канторовича

В этом параграфе мы сформулируем аналог с-монотонности для нашей задачи и докажем его необходимость для носителей оптимальных транспортных планов. Независимо от нас подобный результат был получен в работе [21]. Приведенное там доказательство отлично от нашего и основано на абстрактной теории меры в духе [45]. Определение 1.14. Для двух вероятностных распределений а, (3 на X = Х\ х х Хп определим отношение эквивалентности w; a w [3 если и только если 1. (Pr,)#(a) = (Pr,)#(/3),VA; = l,...,n; 2. fx uda = fx ud/3, Vu Є W. Обозначим через [(3]w класс эквивалентности (З по отношению w- Пусть Sm — набор из т точек в пространстве X, (3S — мера с носителем Sm.

Определение 1.15. Для борелевской функции стоимости с:1-»Ви линейного подмножества W С Сь(р), множество Г С X называется (c,W) — монотонным, если и только если для любого т Є N; любого Sm С Г; любого дискретного вероятностного распределения [3S со свойством supp(/3s) = Sm и любого вероятностного распределения a w [3S выполнено неравенство / cdfis / cda. Jx Jx Предложение 1.16. Если W = {0}, то определение (с }W)—монотонности эквивалентно определению обычной с-монотонности. Доказательство. (с,{0})—монотонность очевидно влечет с-монотонность. Об ратное следует из известного (см. книгу [59]) факта: из с-монотонности supp(/3) следует, что (3 оптимальна в классе вероятностных распределений на X с теми же маргиналами, что и (3. Действительно, если W = {0}, то этот класс сов падает с классом эквивалентности [(3]w- Получаем, что (3 оптимальна в [/3]и/, где (3 — любое распределение с носителем, состоящем из конечного числа точек и лежащем в с-монотонном множестве (здесь мы также используем известный факт, что подмножество с-монотонного множества также с-монотонно). Определение 1.17. Транспортный плани Є Tlw(X) называется (c,W)— монотонным, если и только если существует (c,W)—монотонное множество Г полной ТІ-меры: 7г(Г) = 1. Теорема 1.18. Пусть Xk (к = 1,...,п), X := Х\Х- -хХп —польские пространства, /І = (pk Є V(Xk)), с Є CL(P) —функция стоимости, W С Сь(р) —векторное подпространство, fJ-k\wncL( k) = 0, итг Є Uw(p) —это решение задачи зо Монжа—Канторовича с дополнительными линейными ограничениями: / СОІТІ — inf , 7Г Є Uw(p)-Jx Тогда 7Г —это (c}W)—монотонный транспортный план. Представленное ниже доказательство основывается на теореме о двойственности, которая была доказана в предыдущем параграфе. Доказательство. Из теоремы о двойственности (1.8) / С0І7Г = SUp 2 / fkdf h где супремум берется по множеству всех пар функций (fiUj) Є F х W удовлетворяющих условию / + ио с. Напомним обозначения: F = ф=1 С (/х ), / = Х Г=1 fi(xi)- Пусть (/(),a;fc)— максимизирующая последовательность для двойственной задачи, и пусть Ck = с — р — ujk- Так как / ско1тг = / соїтг 2 fi df1 и Ck 0, мы можем найти такую подпоследовательность с л и такое борелев-ское множество Г для которого 7Г (Г) = 1, что Ck[j) - 0 на Г. В дальнейшем условимся обозначать индексы {k(j)} просто как {j}. Если S = {я } С Г, (3S — это распределение с носителем S и а Є [/3s]n/, то мы получаем / cola 2_\ / Д da + / uj ola. Так как si (Ріі)ф(а) = (Ргг)#(/3) для каждого і Є l,...,m = / /ffc)da = / / гіД и / иода = / 6 j(i/3 для каждого ш Є If = / ujkda = I uJkd[5Sl то для любого к выполнено неравенство ТІ Jcda Y,J flk)d[5s + J ukd(3s =[{с- ck)d(3s. Устремляя к — оо, мы получаем (c,W)—монотонность Г.

Заметим, что в отличие от задачи без ограничений, условие (c,W)—монотонности не является достаточным для оптимальности в общем случае (см. пример 1.19). Однако в некоторых частных случаях достаточность все же имеет место. Это верно, например, в случае мартингальных ограничений, которым посвящен следующий параграф.

Пример 1.19. Пусть k = 2,X = Y = Sl — окружности единичного радиуса, G = Z действует поворотами (образующая группы соответствует положительному повороту на некоторое фиксированное число а, для которого а/тг иррационально), с(х,у) — непрерывная ограниченная функция на S1 х S1. На множестве X х Y группа G действует следующим образом: (х,у) — (g(x),g(y)), g Є G. Множество функций W совпадает с линейной оболочкой множества {hog — h : g Є Z} h Є Сь(Х х Y)}.

Заметим, что любая нетривиальная знакопеременная мера а с носителем, состоящим из конечного числа точек, не является G-инвариантной. Действительно, это следует из того, что для любого є 0 существует элемент g Є G, являющийся поворотом на угол, меньший, чем є. Очевидно, при достаточно малом є мера а = aog l не совпадает с а. Отсюда следует, что произвольное множество Г С S1 х S1 является (c,W)-монотонным. Действительно, класс эквивалентности любой меры а с конечным носителем Sm С Г имеет только один элемент, потому что для любой другой другой меры а с конечным носителем мера а — а не может быть G-инвариантной. Из этого, очевидно, следует, что (с,W)-монотонности носителя недостаточно для оптимальности.

Случай компактной группы симметрии

Напомним определение і/-расстояния Канторовича. Определение 2.15. Пусть (X,d) —метрический компакт, V(X) —множество всех борелевских (= радоновских) вероятностных распределений на нем. Тогда для всякого числа р Є [1,оо) соответствующая LP-метрика Канторовича Wp: V(X) х V(X) — М о есть функция расстояния, определяемая формулой WP(IJL,V) := inf {( f оІр(х,у)оІтг У : 7Г eV(XxX), РгДтг) =/І, РГ2(ТГ) = Л. (2.6)

Обозначим через VQ(X) множество борелевских вероятностных распределений, инвариантных относительно G, а через VQ(X Х X) — множество транспортных планов, инвариантных относительно диагонального действия G на X х X. В нашей ситуации естественно рассмотреть следующий аналог / -расстояний Канторовича на VQ(X): TG KM оІр(х,у)оІ7г) : 7Г ЄРС( ХХ),РГІ(7Г)=/І,РГ2(7Г) = v). (2.7)

Известно (однако это нетривиальный факт), что в случае, когда метрикаd инва риантна относительно действия Z, функция VK; совпадает с классическим рас р стоянием Канторовича Wp на VQ(X) (СМ. [51], теорема 1.7). Однако в дальнейшем мы не будем предполагать инвариантность метрики d, так что И-у Wp на их общей области определения. В этом параграфе мы проверим, что W удовлетворяет аксиомам функции расстояния на"Р5(Х). Пусть X, Y — локально-компактные польские пространства. Группа G действует на них непрерывно. Множество П := span({/ -fog: V/ Є Cb(X x X), Уд Є G}) определяет дополнительное линейное ограничение инвариантности. Определим транспортный план (Id, Ы)фЦ Є П(/І,/І) как единственный транспортный план, сосредоточенный на диагональном множестве {(ж,ж) : х Є X} С X х X и имеющий маргиналы /І. Транспонированный транспортный план 7Г Є П(г/,/і) для 7Г Є Il(/i,z/) определим как единственный транспортный план, удовлетворяющий соотношению: / d7rT = dn JAxB JBXA для каждой пары борелевских множеств А С X, ВСУ. Предложение 2.16. 1. ((/d,/d)#/x)M = 0 VfieVG(X). 2. (ріу)(ш) = 0 V/i,f/ePG(I). 5. 7т(и) = 0 == 7rT(w) = 0 Утт Є Il(/i,z/),V/i, z/ Є VG{X), где ттт определено соотношением f(x,y)d7TT = J f(y,x)d K V/ Є а(Х х Y). Доказательство. 1. Заметим, что м (Id,Id)#n(f(x,y) - f(g(x),g(y))) = fi(f(x,x) - f(g(x,x))) = м(/(ж,ж)) - g#(i(f(x,x)) = 0, если /І Є PG( ), / Є Сь( х X), # Є G, /І(/) := J fdfi. 2. Заметим, что (/І g v){f{x,y) - f{g{x),g{y)) = I f(xM) f(9(x),y)dii(x)\dv(y)+ + J I f(9(x),y) - f(g(x),g(y))dv(y)\dii(x) = 0, V/i,z/ є VG(X), f Є Сь(Х хХ)}9є G. 3. Так как из включения f(x,y) — f(g(x),g(y)) Є W следует, что f(y,x) — f{g{y)i g(x)) W для всех / Є Съ(Х х X), то последнее условие из определения метрического ограничения выполнено. Теперь докажем основное утверждение данного параграфа. Предложение 2.17. Функция W является [0,+оо]-значной функцией расстояния на VG(X).

Доказательство. Так как 7Г = (IdJd)#Li Є П З(/І,/І), f dPdn = 0 для этого 7Г, и W (fi,fi) = 0. По схожим причинам (dp = 0 только на диагонали {(ж,ж)}, причем только планы вида (Id,Id)#[i сосредоточены на ней) Wp(fi,u) ф 0, если [х Ф v. Функция Wp инвариантна, так как из включения 7Г Є ПС(/І,І/) следует, что 7ГТ Є Пс(г/,/і) и J dpdn = J dpdnT. Неравенство треугольника доказывается стандартным образом (см., например, [17], теорема 2.2) с использованием специальной версии леммы о склеивании, которую мы формулируем ниже.

Лемма 2.18 (Лемма об инвариантном склеивании). Для любых вероятностных распределений /ІІ,/І2,МЗ Є VG(X), тіуі Є VG(X Х X), 7Г2з Є VG(X Х X) существует вероятностное распределение 7 Є "Р(Х х X х X) такая, что (РГ12)#(7) = 12; (РГ23)#(7) = 23, (Ргіз)#(т) Є ПС(/ІЬ/І3). Доказательство. Модифицируем доказательство классической леммы о склеивании. Определим подпространство V С Съ{Х х X х X) следующим образом: := /і2(жі,Ж2) + І2з(ж2,жз) +олз(жі,ж3): /і2,/гз Є Cb{X х X), wi3 Є Qj. ПуСТЬ F(/i2 + /23 + ЬЛз) := 7Tl2(/l2) + Я"2з(/2з)- Проверим, ЧТО F КОррвКТНО определен на V. Рассмотрим два представления некоторого элемента из V: /12 + І23+ із = /і2 + /23 + із- Заметим, чтоа із(жі,Жз)-&із(жі,Жз) = иі(хі) + шз(хз) для некоторых бо і, бо з Є 7. Тогда /і2 — /і2 + і = /23 — /23 — з, и, следовательно, обе части равенства зависят только от х - Получаем: 7Tl2(/l2 - /і2 + l) = M2(/l2 - /l2) = М2(/23 /гз) = 7Г2з(/23 /23 з), что доказывает корректность определения F на У. Легко проверить, что F — по ложительный линейный ограниченный функционал. Соответствующая версия теоремы Хана-Банаха (теорема 1.25 в [16]) утверждает, что такой функционал можно продолжить до положительного ограниченного функционала на всем Сь(Х х X х X). В силу того, что на подпространствах Съ(Х} ) действие F сов падает с интегрированием по соответствующим мерам/І , мы можем применить теорему Рисса (теорема 7.10.6 в [26]) для продолжения F (предположения теоре мы выполняются, достаточно рассмотреть произведения компактов). Получен ная мера будет удовлетворять всем свойствам из формулировки доказываемой леммы.

Замечание 2.19. Естественно задаться вопросом: "на каком подмножестве VQ{X)XVQ{X) функция Wp будет принимать конечные значения и являться функцией расстояния в строгом смысле этого слова?". Легко понять, что это множество состоит из инвариантных вероятностных распределений 7Г, для которых . dp(x, ХО)О1ТТ +оо при некотором фиксированном Хо Є X. В силу неравенства треугольника от выбора Хо это множество не меняется.

Замечание 2.20. Имея заданное действие группы на пространстве X, мы можем по-разному определять ее действие на пространстве X х X: "диагональный" способ, рассматриваемый выше, далеко не единственен. Например, можно рассмотреть действие прямой суммы групп G 0 G на пространстве X х X, заданное соотношением: (gi,g2)(%ii%2) = (gi(%i)i#2( 2))- Однако, заметим, что именно идиагональность" действия группы обеспечивает выполнение аксиом расстояния для функции WQ.

Геометрические свойства дополнительных линейных ограничений

Заметим, что разложение тройки (А,А ,М) по определению является марковским переходным ядром из (Х}А) в (Х}А). Определим действие марковского ядра на V(X,A) следующим образом: Q#(/x)(A) := / Q(x,A)d/i Jx для всех А Є А. Вероятностное распределение /і Є V называется инвариантным относительно Q, если Q (fi) = ц. Аналогично для любого марковского переходного ядра можно определить отображение из В(Х,А) в B{Y)B) по формуле Q(f)(y) J f(x)dQ(y,-) и отображение из V(Y,B) в V(X,A) по формуле Q#(v)(A):=fYQ(y,A)dv,VAeA.

Определение 3.11. Подмножество М С V(X) называется сепарабелъным, если в А существует счетное семейство элементов, Т, такое, что для каждой пары различных вероятностных распределений /ІІ, /І2 Є М найдется элемент А Є Т со свойством /іі(А) = (А)- Далее, а-подалгебра A0 Q А называется достаточной для сепарабельного подмножества М С V{X), если существует марковское ядро Q на (Х,А), являющееся разложением тройки (А,А,М). Достаточная а-подалгебра называется Н-достаточной для М, если она достаточна и ц{{х: Qx Є М}) = 1, V/ІЄМ. Две (7-подалгебры A Q A, A Q А будем называть М-эквивалентными для некоторого М С V(X,A), если для каждой меры /І Є М и каждого множества А\ Є А1 найдется множество А і Є А2 такое, что А\ = А і почти всюду относительно /І.

Следующая важная теорема объединяет утверждения теоремы 3.1, теоремы 3.2 и теоремы 3.3 из [38] с леммой 3.6 из [46].

Теорема 3.12. Предположим, что А — счетно-порожденная а-алгебра. Тогда для сепарабельного подмножества М С V(X,A) следующие свойства эквивалентны. - Существует единственная, с точностью до М-эквивалентности, Н-достаточная а-алгебра Л Q А для М, которая состоит из всех множеств А Є А таких, что /і(А) = 0 или /і(А) = 1 для каждого вероятностного распределения /І Є де(М). - Существует марковское ядро Q на (Х,А) со свойством Q(gQ(f)) = Q(g)Q(f) v/,g є в(х,Л) или, что равносильно, со свойством Qx({yeX: Qx = Qy}) = 1,VxeX, такое, что М оказывается подмножеством всех Q-инвариантных вероятностных распределений из V(X,A). Для марковского ядра из этого утверждения соответствующая ему Н-достаточная подалгебра является алгеброй (с точностью до М-эквивалентности) всех Q-инвариантных измеримых множеств.

Определение 3.13. Сепарабельное подмножество М С V(X,A) вероятностных распределений на счетно-порожденной а-алгебре А называется эргодиче-ски разложимым симплексом, если оно удовлетворяет любому из двух эквивалентных свойств, сформулированных в теореме 3.12.

В [38] Дынкин приводит серию примеров эргодически разложимых симплексов. В частности, эргодически разложимыми являются симплексы из примеров 3.6, 3.7.

Следующий результат является прямым следствием теоремы 3.1 из [38] и Замечания 3.8 из [46]. Теорема 3.14. Эргодически разложимый симплекс М С V(X,A) является симплексом Дынкина. Более того, существует такое марковское ядро Q из определения эргодически разложимого симплекса, что граница симплекса по Дынкину определяется равенством: de(M) = {Qx: хєХ} и Ьаг(Д) = /І = jj(S) = fi({x: Qx Є S}) для любого измеримого 5СМ. Следующее предложение носит технический характер. Предложение 3.15. Пусть (X\А) — польское пространство с борелевской а-алгеброй. Тогда следующие три а-алгебры на V(X) совпадают: 1. стандартная а-алгебра 8, 2. а-алгебра, порожденная всеми множествами вида {/ІЄ?(І): a fi(A) &}, А є А, а, 6 Є Qn [0,1], 3. борелевская а-алгебра, порожденная топологией слабой сходимости наТ(Х).

Доказательство. Покажем сначала, что может быть порождена всеми функциями вида /і — ц(А), А Є А. Очевидно, что если все отображения /І — ц(А) измеримы, то отображение /і — /i(s) := f sdfi измеримо для любой простой функции s (под простой функцией мы имеем ввиду линейную комбинацию конечного числа измеримых индикаторных функций). По определению интеграла Лебега j fdfi := sup{/i(s): 0 s f+} — sup{/i(s): 0 s f } (где / = /+— /_, /+, /_ неотрицательны и измеримы, s — измеримая простая функция), и ее измеримость следует из классического факта об измеримости поточечного супремума измеримых отображений.

Так как семейство всех интервалов с рациональными концами в [0,1] порождает борелевскую а-алгебру на [0,1], то стандартная а-алгебра совпадает с сг-алгеброй, порожденной множествами вида {/і Є V(X): а /і(А) b}, АєА,а,Ьє Qn[0,1]. Эквивалентность такой а-алгебры и а-алгебры, борелевской относительно топологии слабой сходимости, доказана, например, в [40] (теорема 2.3). Рассмотрим пример эргодически разложимого симплекса, который уже рассматривался в предыдущей главе диссертации, и который будет служить основным мотивационным примером на протяжении этой главы.

Пример 3.16 (Основной пример). Пусть G —топологическая группа с заданным непрерывным действием на польском метрическом пространстве (X\d), принадлежащая к одному из следующих классов: 1. конечная или счетная группа с дискретной топологией; 2. локально-компактная группа с плотной счетной подгруппой; 3. группа конечных перестановок на счетном множестве (бесконечная симметрическая группа) с топологией поточечной сходимости.

Действие G на X х X определено „диагональным" способом: g(xi,X2) = (g(xi),g(x2)), где g — действие элемента g Є G на X. Вероятностное распределение /І на (X,d) называется инвариантным относительно G, если /І о g l = /І для каждого g Є G. Обозначим через Vc(X) С V(X) множество всех инвариантных борелевских вероятностных распределений na(X}d). Известно, что VQ(X) является замкнутым эргодически разложимым симплексом (доказательство см. в п. 6 и 7 в [38]). Соответствующая симплексу Н-достаточная а-алгебра может быть определена как алгебра Amv всех борелевских G-инвариантных измеримых подмножеств. Соответствующее марковское ядро Q на (Х,А) определяется формулой Q(x,A) := lim -—— / g#(Sx(A))du(g). Здесь (Fn) — последовательность Фелнера группы G, v — левая мера Хаара на G, 5Х —мера Дирака, сосредоточенная в точке х Є X. Напомним, что последовательностью Фелнера называется последовательность таких непустых компактных подмножеств G, что n oo /i(Fn) для всякого g Є G; где gFn := {gf: f Є Fn}, Л — симметрическая разность. Существование такой последовательности подмножеств гарантировано для рассматриваемых классов групп.

Сферически-инвариантные вероятностные распределения

Обозначим через S группу всех перестановок натуральных чисел, которые меняют местами только конечное число элементов. Рассмотрим естественное действие этой группы на К. , определенное по формуле (т(х) = (ха{і)), I = WG1N, (7ЄГ Рассмотрим вероятностные распределения /І и z/, которые инвариантны относительно каждого элемента а Є S: /і =/і ост-1, v = v о o l. Вероятностные распределения такого типа называются перестановочными ("exchangeable"). Простейший пример такой меры —счетная степеньт00 некоторой борелевской вероятностной меры т на Ш. Напомним, что счетной степенью называется распределение последовательности и.о.р.с.в. с распределением ш, которое является вероятностным распределением наК .

Вид оптимальной транспортировки в инвариантной задаче Монжа в случае /і = т очень легко описывается. Рассмотрим отображение Т\(х) = (Т(ж),еі) и зафиксируем первую координату Х\. Тогда отображение F: (ж2,Жз,...) ь- Т\(х) инвариантно относительно S (действующего на (ж2,Жз,...)). Следовательно, F — /І-ПОЧТИ наверное константа согласно закону 0 — 1 Хьюита-Сэвэджа (Hewitt-Sawage law), примененному к мере/І. Поэтому Т\ зависит только от координаты Х\ (с точностью до множества нулевой вероятности). Так как аналогичный аргумент может быть применен к каждой из координат, получаем, что Т диагональное отображение: (Ті(жі),Т2(ж2)5 Более того, ТІ(Х) = Т\{х), так как Т коммутирует со всеми перестановками координат.

Рассмотрим перестановочную задачу Монжа для функции стоимости с = (х\ —у\)2. Ответ на вопрос Q1) прост, так как эргодические вероятностные распределения представляют собой счетные степени одномерных мер, а структура оптимальных транспортировок между ними хорошо известна. Что касается вопроса Q2), то можно воспользоваться классической теоремой Де Финетти:

Теорема 4.2. Пусть V —пространство борелевских вероятностных распределений на Ж, снабженное топологией слабой сходимости. Тогда для каждой борелевского перестановочного распределения ц наШп существует борелевское вероятностное распределение И на V сое войством fI(B) = fm(B)U(dm) для каждого борелевского В С MN.

Из теоремы следует, что пространство эргодических вероятностных распределений изоморфно пространству "Р(К) всех вероятностных распределений на Ш. Поэтому для решения транспортной задачи в классе перестановочных мер нужно исследовать транспортную задачу для пары /ІО, Щ ИЗ "Р(М), возникающей в разложении теоремы де-Финетти. Ясно, что функция стоимости с на "Р(К) удовлетворяет равенству где W — стандартное квадратичное расстояние Канторовича на Ш.

Следующее очевидное следствие устанавливает возможные причины отсутствия оптимального транспортного отображения в инвариантной задаче Монжа.

Следствие 4.3. Перестановочная задача Монжа имеет решение тогда и только тогда, когда задача из пункта Q1) имеет решение, и, более того, задача из пункта Q2) имеет решение для а -почти всех цх и ау-почти всех Vу. Перестановочная задача Монжа не всегда имеет решение. Например, если /І — счетная степень одномерной меры (совместное распределение после 88 дователъности н.о.р.с.в.), a v — нет, то оптимальной транспортировки из її в v не существует.

Рассмотрим инвариантную транспортную задачу для мер, инвариантных относительно операторов вида U х Id, где U — унитарный оператор на IEP = Prn(MN), a Id — тождественный оператор на ортогональном дополнении к М.п. Как правило, с = (х\ — у\)2 Это один из примеров, когда задача Монжа допускает явное решение. Согласно известному результату (см. [44]) каждая сферически-инвариантная мера /і на К допускает представление fi = I 7t%W, где 7t — распределение гауссовских независимых одинаково распределенных случайных величин с нулевым средним и дисперсией t, а р — мера на Ш+. В этом случае задача Монжа сводится очевидно сводится к изучению одномерной оптимальной транспортировки между рм и pv.

В этом параграфе мы продолжим исследование перестановочной задачи Монжа и покажем, что она сводится к изучению транспортной задачи на подмножестве гильбертового пространства. Сформулируем строгое определение перестановочной задачи Монжа— Канторовича, объединяющей в себе перестановочные задачи Монжа и Канторовича, рассматриваемые ранее. Определение 4.4. Перестановочная задача Монжа—Канторовича Пусть заданы \i,v Є V(M ) —перестановочные вероятностные распределения. Перестановочной задачей Монжа—Канторовича будем называть задачу поиска отображения Т: Ш — Ш , такого, что вероятностное распределение 7Г = /І о [х)Т{х)) 1 является решением перестановочной задачи Канторовича с функцией стоимости Ci(x,y) = \х\ — yi\2. Отображение Т называется оптимальной перестановочной транспортировкой. Заметим, что в параграфе 4.1.1 мы уже свели рассмотрение перестановочной задачи Монжа—Канторовича к рассмотрению семейства транспортных задач на прямой. Более точно, решение перестановочной транспортной задачи сводится к поиску решения задачи Монжа—Канторовича на метрическом пространстве с функцией стоимости W2