ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2011, том 47, № 4, с. 143-165
К СТОЛЕТИЮ СО ДНЯ РОЖДЕНИЯ ЛЕОНИДА ВИТАЛЬЕВИЧА КАНТОРОВИЧА
ДВОЙСТВЕННОСТЬ МОНЖА-КАНТОРОВИЧА И ЕЕ ПРИМЕНЕНИЕ В ТЕОРИИ ПОЛЕЗНОСТИ*
© 2011 г. В.Л. Левин
(Москва)
Обзор посвящен развитию теории двойственности для общей задачи Монжа-Канторовича и ее применению в теории полезности.
Ключевые слова: теория двойственности, двойственность Монжа-Канторовича, теория полезности.
1. ВВЕДЕНИЕ
Задача Монжа-Канторовича (ЗМК), известная также как задача о перемещении масс, состоит в следующем. Заданы два распределения (исходное и желаемое) некоторого продукта и функция стоимости, показывающая стоимость перемещения единицы продукта из одного пункта в другой. Требуется перейти от первого распределения ко второму с наименьшими затратами, т.е. составить оптимальный план перемещения масс. Впервые эту задачу рассмотрел Гаспар Монж (1781) в связи с некоторыми прикладными вопросами фортификации ("задача о выемках и насыпях"). Функцией стоимости в задаче Монжа служило расстояние между пунктами, а под планом перемещения масс понималось отображение, сохраняющее объем, так что надо найти план, минимизирующий работу по перемещению масс, связанную с преодолением сил трения. В такой постановке задача была решена П.-Э. Аппелем (1887). В наше время получены решения задачи Монжа для более общих функций стоимости и более общих распределений массы.
В 1942 г. Л.В. Канторович (Канторович, 1942) (см. также (Канторович, 1948; Канторович, Рубинштейн, 1957, 1958; Канторович, Акилов, 1984)) рассмотрел задачу о перемещении масс, в которой под планом перемещения понималась положительная мера на произведении пространств, имеющая своими проекциями (маргинальными мерами) исходное и желаемое распределения, а функцией стоимости, как и у Монжа, служило расстояние между пунктами. Указанная постановка задачи, называемая иногда классической задачей Монжа-Канторовича, является расширением (релаксацией) первоначальной постановки Монжа; решениям Монжа при этом отвечают меры, сосредоточенные на графике соответствующего отображения. Такой вариант классической ЗМК исследуется в публикациях Канторовича 1942 и 1949 г. В более поздних работах (Канторович, Рубинштейн, 1957, 1958) рассматривается другой вариант задачи, когда заданы не сами маргинальные меры, а их разность, т.е. разрешены транзитные перевозки.
Приведем точную математическую формулировку классической ЗМК, рассматривавшейся Л.В. Канторовичем. На метрическом компакте (X, d) заданы две положительные борелев-ские меры v1 и v2 с равными общими массами: a1X = v2X. Требуется минимизировать интеграл fxxxc(x' y)dn, где c(x, y) = d(x, y), n пробегает множество положительных мер наXх Xс проекциями n(B х X) = v1B и n(X х B) = V2B для каждого борелевского множества B 3 X (ЗМК с фиксированными маргинальными мерами) или же n пробегает множество положительных мер на X х X с разностью проекций n(B х X) - n(X х B) = v1B - v2B (ЗМК с фиксированной разностью маргинальных мер). Обозначим через A(c, v1 - v2) оптимальное значение задачи с фиксированной разностью маргинальных мер и через C(c, v1, v2) оптимальное значение задачи с фиксированными маргинальными мерами. Один из важных результатов для классической ЗМК состоит в
* Работа выполнена при финансовой поддержке Российского гуманитарного научного фонда (проект 10-02-00073а).
эквивалентности обеих постановок, с фиксированными маргинальными мерами и с фиксированной разностью маргинальных мер: A(d, v1, v2) = C(d, v1 - v2) (Канторович, Рубинштейн, 1957, 1958). При этом указанная величина является метрикой на пространстве вероятностных мер на X, топологизирующей их слабую* сходимость (метрика Канторовича-Рубинштейна). Другим фундаментальным результатом является критерий оптимальности Канторовича: для оптимальности данной допустимой меры (плана перемещения масс) необходимо и достаточно существование функции u(x) на исходном пространстве, называемой потенциалом и обладающей тем свойством, что для любых двух пунктов x и y разность потенциалов u(x)-u(y) не превосходит значения функции стоимости в точке (x, y), а на носителе меры имеет место точное равенство.
Классическая ЗМК является бесконечномерной задачей линейного программирования (исторически, одной из первых, если не самой первой); при этом критерий оптимальности Канторовича может быть переформулирован как теорема двойственности, т.е. утверждение о равенстве оптимальных значений исходной и двойственной задач (см., например, (Вершик, 1970; Рубинштейн, 1970)). В случае конечного числа пунктов задача с фиксированными проекциями превращается в обычную транспортную задачу линейного программирования (с расстоянием в качестве функции стоимости), а задача с фиксированной разностью проекций - в транспортную задачу в сетевой постановке. Замечательно, что первая публикация Л.В. Канторовича (1942) появилась раньше соответствующих работ, относящихся к конечномерной транспортной задаче.
Задачи Монжа-Канторовича с более общими функциями стоимости (непрерывными и разрывными), определенными на всевозможных пространствах, рассматриваются в литературе начиная с середины 1970-х годов (Левин, 1974, 1975, 1977, 1978; Левин, Милютин, 1979). В это же время появился и сам термин "задача Монжа-Канторовича" (Левин, 1977, 1978), ставший теперь общепринятым. В общем случае две постановки ЗМК перестают быть эквивалентными, и существование потенциала не является необходимым условием оптимальности. (Заметим в этой связи, что в формулировке задачи в (Канторович, 1948) не предполагается, что функция стоимости является метрикой, однако это предположение неявно используется в доказательстве.) Приведем иллюстративный пример.
Пример 1. Пусть X = [0, 1], c(x, y) = (x - y)2, v1 = e0, v2 = e1, где ex - мера Дирака (S-функция) в точке x, т.е. ex(B) = 1 при x G B и ex(B) = 0 при x £ B. Поскольку e(01) - единственная мера с проекциями e0 и e1, то она является оптимальным решением ЗМК с фиксированными проекциями и C(c, v1, v2) = с(0, 1) = 1. В то же время для n = e(01/n) + e(1/n,2/n) +...+ e((n-1)/n1) (перемещение из
0 в 1 через n - 1 промежуточный пункт) разность проекций равна v1 - v2, и, так как интеграл от c(x, y) по этой мере равен 1/n, то A(c, v1 - v0) = 0. Далее, если u(x) - u(y) < (x - y)2 при всех x, y из [0, 1], то u(x) - константа, стало быть, u(0) - u(1) = 0 ^ с(0, 1) = 1, т.е. мера e(01) оптимальна (в задаче с фиксированными проекциями), но критерий Канторовича для нее не выполняется1.
Несложно показать, что для сохранения эквивалентности обоих вариантов ЗМК при любых v1, v2 (o1X = v2X) необходимо и достаточно, чтобы функция стоимости удовлетворяла неравенству треугольника c(x, y) + c(y, z) > c(x, z). С точки зрения теории двойственности ЗМК с фиксированной разностью маргинальных мер является более трудной. Полная теория двойственности в массовой постановке (т.е. описание всех функций стоимости, для которых верна теорема двойственности) для этой задачи была построена в совместной работе Милютина и автора (Левин, Милютин, 1979) в случае произвольного (не обязательно метризуемого) компактного пространства X. Обобщение этой теории на более широкий класс топологических пространств получено в (Левин, 1984, 1987; Levin, 1990). Дальнейшие (не топологические) обобщения см. в (Левин, 1996; Levin, 1997b; Левин, 1997).
В 1960-1980 гг. интенсивно развивались исследования по классической ЗМК с фиксированными проекциями (некоторые авторы рассматривают только этот вариант задачи) и ее применениям в теории информации и математической статистике (Вассерштейн, Вершик, Судаков, Келлерер, Рачев, Рюшендорф и др.). После появления важных работ (Brenier, Gangbo, McCann) в этой области начался настоящий бум, продолжающийся и сейчас (связь с уравнением
1 Для оптимальности допустимой меры в общей ЗМК с фиксированными проекциями необходимо и достаточно существование пары непрерывных функций u(x) и v(y) таких, что u(x) - v(y) < c(x, y) при любых x, y и u(x) - v(y) = c(x, y) на носителе меры.
Монжа-Ампера и другими дифференциальными уравнениями с частными производными, применения в различных разделах естествознания, от метеорологии и океанологии до космологии, гидро- и аэродинамики, и т.д.). В 1998-2003 гг. появилось несколько монографий (Rachev, Rüschendorf; Evans, Grandbo; Villani; Brenier; Ambrosio).
Экономические применения задачи Монжа-Канторовича, отличные от очевидного транспортного аспекта, оказались связаны с теорией двойственности для общей ЗМК с фиксированной разностью проекций. Нами был развит новый метод, позволяющий использовать единый подход при решении самых разных задач как математической экономики (теория полезности; рационализируемость спроса; модели динамики; коррупция, связанная с искажением экономической информации), так и чистой математики (задача наилучшего приближения, циклическая монотонность, абстрактный выпуклый анализ), список литературы в конце статьи2. В основе метода лежат теоремы двойственности для общей ЗМК с фиксированной разностью маргинальных мер и специальной (разрывной) функцией стоимости. Важную роль при этом играет множество ограничений двойственной задачи
Q(c) := {u d Cb(X) : u(x) - u(y) < c(x, y) V(x, y) d X x X}
(Cb(X) - пространство всех ограниченных непрерывных функций на X), аналогичное множество
Q0(c) := {u е RX(X) : u(x) - u(y) < c(x, y) V(x, y) d X x X},
являющееся множеством ограничений для абстрактной (нетопологической) версии двойственной ЗМК (если функция стоимости ограничена, непрерывна в некоторой окрестности диагонали D = {(x, x): x d X} и обращается в нуль на D, то Q0(c) = Q(c)), а также редуцированная функция стоимости ct(x, y), показывающая минимальную стоимость перемещения единицы продукта из x в y с учетом всевозможных транзитных перемещений через несколько промежуточных пунктов. Оказалось, что решение многих задач из самых разных разделов экономической теории сводится к условиям непустоты (и изучению свойств) множеств Q(c) и Q0(c) для специальных (как правило, знакопеременных) вспомогательных функций стоимости. Этот метод оказался полезен и
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.