Русская Википедия:Лемма Шепли — Фолкмана

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Shapley–Folkman lemma.svg
Сложение четырёх множеств по Минковскому. Тёмно-красные точки обозначают элементы множеств, в то время как выпуклые оболочки множеств выделены розовым цветом. Точка (+) на правой иллюстрации, принадлежащая выпуклой оболочке суммы Минковского четырёх невыпуклых множеств, является суммой четырёх точек (+), представленных на левой иллюстрацииШаблон:Sfn.

Лемма Шепли — Фолкмана[прим. 1]Шаблон:Переход связывает две операции выпуклой геометрии — сложение по МинковскомуШаблон:Переход и выпуклую оболочку. Лемма имеет приложения в ряде дисциплин, в том числе в математической экономикеШаблон:Переход, оптимизацииШаблон:Переход и теории вероятностейШаблон:ПереходШаблон:Sfn. Лемма и связанные с ней результаты позволяют дать утвердительный ответ на вопрос «Близка ли к состоянию выпуклостиШаблон:Переход сумма нескольких множеств?»Шаблон:Sfn.

Лемма названа в честь Ллойда Шепли и Шаблон:Нп3 и была впервые опубликована в работе экономиста Шаблон:Нп3. В 2012 году Шепли наравне с Элвином Ротом стал лауреатом Нобелевской премии по экономике[прим. 2]. Работа Старра, в которой произошло первое упоминание леммы, увидела свет в 1969 году. Тогда экономист сотрудничал с известнейшим американским учёным Кеннетом Эрроу и занимался решением вопроса о существовании некоторых экономических равновесийШаблон:Sfn. В работе Старра проводилось исследование экономики, в которой некоторые геометрически выраженные взаимосвязи, обладавшие свойством невыпуклости, заменялись ближайшими выпуклыми аналогами — выпуклыми оболочкамиШаблон:Переход. Старр доказал, что такая «овыпукленная» экономика обладает равновесными состояниями, весьма близкими к квазиравновесиям оригинальной экономики. Более того, учёный доказал, что каждое квазиравновесие обладает рядом оптимальных характеристик подлинного равновесия, которые были найдены в выпуклых экономиках. Работы Шепли, Фолкмана и Старра показали, что основные результаты выпуклой экономической теории являются хорошими приближениями экономики с невыпуклыми элементами. Лемма позволяет предположить, что если число слагаемых множеств превосходит размерность векторного пространстваШаблон:Переход D, то тогда нахождение выпуклых оболочек («овыпукление») требуется только для D слагаемыхШаблон:Sfn. Французский экономист Роже Геснери писал: «Получение этих результатов в общем виде стало одним из главных достижений послевоенной экономической теории»Шаблон:Sfn.

Тематика невыпуклых множеств в экономике становилась предметом исследования многих других нобелевских лауреатов[прим. 2]. С этим вопросом работали Пол Самуэльсон (премия 1970 года), Кеннет Эрроу (1972), Тьяллинг Купманс (1975), Жерар Дебрё (1983), Роберт Ауман (2005), Пол Кругман (2008). Смежной тематикой выпуклых множеств занимались Леонид Канторович (1975), Роберт Солоу (1987), Леонид Гурвич (2007). В теории оптимизации лемма Шепли — Фолкмана использовалась для объяснения успешного решения задач минимизации сумм нескольких функцийШаблон:SfnШаблон:Sfn, а также для доказательства «закона средних» для случайных множеств (эта теорема была доказана только для выпуклых множеств)Шаблон:Sfn.

Рассматриваемые категории

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

Вещественное векторное пространство

Шаблон:Main

Векторным пространством <math>V</math> называется алгебраическая структура, для элементов которой определены две операции — сложение и умножение на число (называемое «скаляром»). При этом операции подчинены восьми аксиомам:

  1. <math>\mathbf{x} + \mathbf{y} = \mathbf{y} + \mathbf{x}</math>, для любых <math>\mathbf{x}, \mathbf{y}\in V</math> (коммутативность сложения);
  2. <math>\mathbf{x} + (\mathbf{y} + \mathbf{z}) = (\mathbf{x} + \mathbf{y}) + \mathbf{z}</math>, для любых <math>\mathbf{x}, \mathbf{y}, \mathbf{z} \in V</math> (ассоциативность сложения);
  3. существует такой элемент <math>\theta \in V</math>, что <math>\mathbf{x} + \theta = \mathbf{x}</math> для любого <math>\mathbf{x} \in V</math> (существование нейтрального элемента относительно сложения), в частности <math>V</math> не пусто;
  4. для любого <math>\mathbf{x} \in V</math> существует такой элемент <math>-\mathbf{x} \in V</math>, что <math>\mathbf{x} + (-\mathbf{x}) = \theta</math> (существование противоположного элемента относительно сложения).
  5. <math>\lambda(\mu\mathbf{x}) = (\lambda\mu)\mathbf{x}</math> (ассоциативность умножения на скаляр);
  6. <math>1\cdot\mathbf{x} = \mathbf{x}</math> (унитарность: умножение на нейтральный по умножению скаляр сохраняет вектор).
  7. <math>(\lambda + \mu)\mathbf{x} = \lambda \mathbf{x} + \mu \mathbf{x}</math> (дистрибутивность умножения на вектор относительно сложения скаляров);
  8. <math>\lambda(\mathbf{x} + \mathbf{y}) = \lambda \mathbf{x} + \lambda \mathbf{y}</math> (дистрибутивность умножения на скаляр относительно сложения векторов),

где <math>V</math> — непустое множество элементов («векторов») данного пространстваШаблон:Sfn.

Важной характеристикой векторного пространства является размерность, которая характеризует максимальное число линейно независимых элементов пространства. Эти линейно независимые элементы образуют базис векторного пространстваШаблон:Sfn.

Выпуклое множество

Шаблон:Main Шаблон:Кратное изображение Непустое множество <math>Q</math> в вещественном векторном пространстве считается выпуклым, если отрезок, соединяющий две любые точки <math>Q</math>, является подмножеством <math>Q</math>Шаблон:Sfn. Например, невыпуклое множество целых чисел {0, 1, 2} является подмножеством промежутка [0, 2], который обладает свойством выпуклости. Круг <math>\bullet</math> является выпуклым множеством, а окружность <math>\circ</math> таковым считаться не может, так как не все точки отрезка будут одновременно являться точками множества: <math>\oslash</math>. Пустое множество считается выпуклым либо по определениюШаблон:Sfn, либо на основании принципа Шаблон:Нп3[прим. 3].

Формально выпуклое множество можно определить следующим образом:

Шаблон:Начало цитаты Множество <math>Q</math> является выпуклым, если для любых точек <math>v_0</math>, <math>v_1 \in Q</math> и любого вещественного числа <math>\lambda \in [0, 1]</math> выполняется условие

<math>(1 - \lambda)v_0 + \lambda v_1 \in Q</math>.Шаблон:Конец цитаты

Выпуклой комбинацией множества называется некоторая взвешенная средняя, определённая по формуле

<math>

\sum_{i=1}^n \lambda_i v_i </math> при условиях

<math>

\begin{cases} \lambda_i \geqslant 0, \\

\sum_{i=1}^n \lambda_i = 1. \end{cases} </math>

Используя метод математической индукции, можно установить, что множество <math>Q</math> выпукло тогда и только тогда, когда каждая выпуклая комбинация <math>Q</math> принадлежит самому множествуШаблон:SfnШаблон:SfnШаблон:Sfn:

<math>\sum_{i=1}^n \lambda_i v_i \in Q</math>.

Определение выпуклого множества предполагает, что пересечение двух выпуклых множеств всегда выпукло. Отсюда же следует, что выпуклым является и пересечение семейства выпуклых множеств. В частности, пара непересекающихся множеств имеет пересечением пустое множество, которое, как было установлено выше, выпуклоШаблон:Sfn.

Выпуклая оболочка

Шаблон:Main

Файл:Extreme points.svg
В выпуклой оболочке красного множества каждая синяя точка является выпуклой комбинацией некоторых красных точек.

Выпуклой оболочкой <math>Conv Q</math> множества <math>Q</math> называется наименьшее выпуклое множество, содержащее <math>Q</math> в качестве подмножества. Наименьшее множество представляет собой наименьший элемент по отношению к вложению множеств, то есть такое выпуклое множество, содержащее данную фигуру, что оно содержится в любом другом выпуклом множестве, содержащем данную фигуру. Так, <math>Conv Q</math> является пересечением всех выпуклых множеств, которые покрывают <math>Q</math>. К примеру, выпуклой оболочкой множества {0, 1} является отрезок числовой прямой [0, 1], содержащий целые числа 0 и 1Шаблон:Sfn.

Сложение Минковского

Шаблон:Main

Файл:Minkowski sum.png
Сложение множеств по Минковскому. Суммой квадратов Q1=[0,1]2 и Q2=[1,2]2 является квадрат Q1+Q2=[1,3]2.

Суммой Минковского непустых множеств <math>Q_1</math> и <math>Q_2</math> в вещественном векторном пространстве является множество <math>Q_3</math>, состоящее из сумм всевозможных элементов слагаемых множествШаблон:SfnШаблон:Sfn: Шаблон:Начало цитаты <math>Q_3 = \left\{\,q_3 \mid q_3=q_1+q_2, q_1\in Q_1, q_2\in Q_2\,\right\}.</math>Шаблон:Конец цитаты Итак, в результате проведения операции формируется множество-сумма, включающее все возможные суммы элементов первого и второго множеств. Например, если множество, состоящее из нуля и единицы, сложить с собой же, то в результате будет получено множество, включающее ноль, единицу и двойкуШаблон:Sfn:

<math>\{0, 1\} + \{0, 1\} = \{0 + 0, 0 + 1, 1 + 0, 1 + 1\} = \{0, 1, 2\}.</math>

Согласно методу математической индукции, сумма Минковского <math>Q_n</math> конечного семейства непустых множеств при условиях

<math>

\begin{cases} Q_n \neq \varnothing , \\

1 \leqslant n \leqslant N . \\ \end{cases} </math>

является множеством, сформированным поэлементным сложением множеств-слагаемыхШаблон:SfnШаблон:Sfn:

<math>\sum Q_n = \{\sum q_n: q_n \in Q_n \}</math>.

Сумма множества <math>Q</math> и множества <math>\{0 \}</math>, содержащего только один нулевой элемент, равна <math>Q</math>:

<math>Q + \{0 \} = Q</math>.

Выпуклая оболочка суммы Минковского

Операция сложения Минковского обладает полезным свойством при «овыпуклении» множеств, то есть при нахождении их выпуклых оболочек. Для любых множеств <math>Q_1</math> и <math>Q_2</math> в вещественном векторном пространстве выпуклая оболочка их суммы Минковского равна сумме Минковского их выпуклых оболочек:

<math>Conv(Q_1 + Q_2) = Conv Q_1 + Conv Q_2</math>.

С применением математической индукции выводится аналогичное утверждение для конечного набора множествШаблон:SfnШаблон:Sfn:

<math>Conv(\sum Q_n) = \sum Conv(Q_n)</math>.

Лемма

Тождество

<math>Conv(\sum Q_n) = \sum Conv(Q_n)</math>

позволяет установить, что если точка <math>v</math> принадлежит выпуклой оболочке суммы Минковского <math>N</math> множеств, то она принадлежит и сумме выпуклых оболочек слагаемых множеств:

<math>v \in Conv(\sum Q_n) \Rightarrow v \in \sum Conv(Q_n)</math>

Из этой импликации и определения суммы Минковского следует, что любую точку, принадлежащую множеству <math>Conv(\sum Q_n)</math> можно представить как сумму некоторых точек <math>q_n</math>, принадлежащих выпуклым оболочкам слагаемых множеств:

<math>

\begin{cases} v = \sum q_n , \\

v \in Conv(\sum Q_n) , \\

q_n \in Conv(Q_n) . \\ \end{cases} </math>

В таком представлении набор суммируемых точек <math>q_n</math> зависит от выбранной точки-суммы <math>v</math>.

Лемма Шепли — Фолкмана

Фотография Ллойда Шепли
Ллойд Шепли, лауреат Нобелевской премии по экономике (2012)[прим. 2], является соавтором доказательства леммы наряду с Джоном ФолкманомШаблон:Sfn.

Примем указанное представление точки <math>v = \sum q_n</math>.

Шаблон:Начало цитаты Если размерность векторного пространства строго меньше числа слагаемых множеств

<math>D < N</math>,

то тогда, согласно лемме Шепли — Фолкмана, «овыпукление» требуется только для <math>D</math> слагаемых множеств (их конкретный набор зависит от выбора точки <math>v</math>)Шаблон:Sfn. Это позволяет выразить точку <math>v</math> следующим образом:

<math>v = \sum_{1\leq{d}\leq{D}}{q_d} + \sum_{D+1\leq{n}\leq{N}}{q_n}</math>

при

<math> v \in{ \sum_{1\leq{d}\leq{D}}{\operatorname{Conv}{(Q_d)}} + \sum_{D+1\leq{n}\leq{N}}{Q_n} }. </math>

Шаблон:Конец цитаты

Иными словами, сумма точек <math>q_d</math> принадлежит выпуклой оболочке суммы <math>D</math> множеств (или меньшего их числа), а сумма точек <math>q_n</math> принадлежит сумме оставшихся множеств-слагаемых.

Содержание леммы проиллюстрируем простейшим примером: каждую точку выпуклого множества [0, 2] можно представить как сумму целого числа из невыпуклого множества {0, 1} и вещественного числа из выпуклого множества [0, 1]Шаблон:Sfn.

Размерность

Лемма позволяет делать и обратные выводы, касающиеся не множеств, но размерности векторного пространства. Если в некотором конечномерном вещественном векторном пространстве лемма выполняется для натурального числа <math>D</math> и ни для какого числа меньше <math>D</math>, то размерность векторного пространства равна <math>D</math>Шаблон:Sfn. Разумеется, данное утверждение актуально только для конечномерных векторных пространствШаблон:SfnШаблон:Sfn.

Теорема Шепли — Фолкмана и следствие Старра

A blue disk contains red points. A smaller green disk sits in the largest concavity in among these red points.
Радиус описанной окружности (синий вектор) и внутренний радиус (зелёный вектор) множества тёмно-красных точек (их выпуклая оболочка обозначена красным пунктиром). Внутренний радиус меньше радиуса описанной окружности в большинстве случаев.

Шепли и Фолкман использовали лемму для доказательства своей теоремы, в которой устанавливалась Шаблон:Нп3 Шаблон:Нп3 между суммой Минковского и её выпуклой оболочкой, «овыпукленной» суммой. Теорема Шепли — Фолкмана гласит, что квадрат евклидова расстояния между любой точкой «овыпукленной» суммы <math>Conv(\sum Q_n)</math> и соответствующей ей точкой исходной суммы <math>\sum Q_n</math> не превосходит значение суммы квадратов <math>D</math> наибольших радиусов окружностей, описанных около множеств <math>Q_n</math> (описанной сферой называется наименьшая сфера, включающая множество)Шаблон:Sfn. Значение такой границы не зависит от числа <math>N</math> слагаемых множеств, если <math>N > D</math>Шаблон:Sfn. Следовательно, расстояние равно нулю тогда и только тогда, когда сумма сама является выпуклым множеством. При <math>N > D</math> верхняя граница зависит от размерности <math>D</math>, формы множеств-слагаемых и не зависит от количества слагаемых множествШаблон:Sfn.

Радиус описанной окружности превосходит внутренний радиус множества или, реже, равен емуШаблон:Sfn. Внутренним радиусом называется наименьшее число <math>r</math>, такое, что для любой точки <math>q \in Conv(Q_n)</math> существует окружность радиуса <math>r</math>, содержащая те точки <math>Q_n</math>, которые охватывают центр окружности (то есть <math>q</math>)Шаблон:Sfn. Внутренний радиус является характеристикой размеров невыпуклостей множества. Формально внутренний радиус множества можно определить такШаблон:Sfn[прим. 4]:

<math>r(Q_n) = \sup\, \{ q \in Conv(Q_n) \} \inf\, \{ T \subset Q_n \} rad(T) .</math>

Следствие Старра к теореме установил новую (меньшую, чем у Шепли и Фолкмана) верхнюю границу между суммой и «овыпукленной» суммой: Шаблон:Начало цитаты согласно королларию Старра, квадрат евклидова расстояния между любой точкой <math>v \in Conv(\sum Q_n)</math> и соответствующей ей точкой множества <math>\sum Q_n</math> ограничен суммой квадратов <math>D</math> наибольших внутренних радиусов множеств <math>Q_n</math>Шаблон:SfnШаблон:Sfn.Шаблон:Конец цитаты Для Шаблон:Нп3 меру расстояния, предложенную Старром, называют невыпуклостью (Шаблон:Lang-en)[прим. 5] множества. Граница, налагаемая королларием Старра на невыпуклость множества-суммы, зависит только от <math>D</math> наибольших внутренних радиусов множеств-слагаемых и не зависит от числа слагаемых <math>N</math> при <math>N > D</math>.

Подмножество <math>D</math> слагаемых (<math>N > D</math>), точнее, их форма, определяет верхнюю границу расстояния между средним значением <math>N</math> множеств по Минковскому

<math>\frac1N (Q_1+ Q_2 + \ldots + Q_n)</math>

и выпуклой оболочкой этой средней. При N, стремящемся к бесконечности, максимальное расстояние стремится к нулю (для множеств-слагаемых равномерно ограниченного размера)Шаблон:Sfn.

Доказательство

Оригинальное доказательство леммы устанавливало лишь достоверность существования подобного представления точек, при этом алгоритм их нахождения в доказательстве представлен не был. Схожие доказательства были предложены Эрроу и ХаномШаблон:Sfn, КасселсомШаблон:Sfn, ШнейдеромШаблон:Sfn и другими учёными. Абстрактное и изящное доказательство представил Шаблон:Нп3 — его работа была впоследствии дополнена АртстейномШаблон:SfnШаблон:Sfn. Некоторые доказательства не были опубликованыШаблон:SfnШаблон:Sfn. В 1981 году Старр опубликовал итеративный метод вычисления представления заданной точки-суммы. Тем не менее присутствовавшее в работе доказательство было менее сильным, чем оригинальноеШаблон:Sfn. Шаблон:Hider

Приложения

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

Экономика

The nonnegative quadrant of the Cartesian plane appears. A blue straight-line slopes downward as a secant joining two points, one on each of the axes. This blue line is tangent to a red curve that touches it at a marked point, whose coordinates are labeled Qx and Qy.
Потребитель предпочитает любую корзину товаров на кривой безразличия I2 любой корзине на кривой I1. Корзина (Qx, Qy), находящаяся в точке касания синей бюджетной линии к I2, оптимальна и доступна, в то время как любая другая корзина на I2 желанна, но недоступна.

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

В микроэкономической теории принято допущение о том, что предпочтения потребителей определены на всём пространстве некоторых «корзин», то есть количественно определённых наборов различных товаров: потребители обладают точным знанием о своих предпочтениях и об их количественных характеристиках. Каждая корзина представлена неотрицательным вектором, координаты которого обозначают количество каждого рассматриваемого товара. На этом множестве корзин для каждого потребителя определяются кривые безразличия. Каждая кривая представляет собой геометрическое место точек, соответствующих тем корзинам, которые потребитель расценивает как эквивалентные по полезности. Другими словами, покупатель испытывает безразличие к тому, какая именно корзина (среди расположенных на одной кривой) ему достанется. В данной модели предполагается, что через некоторую корзину (точку) может проходить только одна кривая безразличия. Финансовые возможности покупателя при этом ограничены бюджетной линией (в двумерном пространстве). Таким образом, оптимальным для потребителя решением является выбор той корзины, которая расположена в точке касания бюджетной линии к некоторой кривой безразличия. Множеством предпочтений (Шаблон:Lang-en) потребителя называется объединение некоторой кривой безразличия и всех точек, расположенных выше её графика (то есть совокупность некоторых одинаково ценных для потребителя корзин и всех других более ценных корзин). Отношение предпочтения потребителя является выпуклым, если это множество предпочтений выпуклоШаблон:SfnШаблон:Sfn.

Итак, если найдено оптимальное для потребителя решение, то бюджетная линия является опорной прямой лучшей доступной кривой безразличия. Положение бюджетной линии определено вектором цены и вектором дохода покупателя (точнее, вектором дохода и Шаблон:Нп3). Следовательно, множество оптимальных корзин является функцией от цен, и эта функция называется спросом потребителя. Если множество предпочтений выпукло, то спрос потребителя также является выпуклым множеством при любой цене. Примером выпуклых функций спроса являются единственная оптимальная корзина и отрезок оптимальных корзинШаблон:Sfn.

Невыпуклое отношение предпочтения

Файл:NonConvex.gif
Если отношение предпочтения потребителя имеет вогнутости, потребитель может переходить между обособленными оптимальными корзинами, расположенными на кривой оптимальности. Кривая оптимальности (Optimal Pareto front) выделена чёрным цветом.

Впрочем, если множество предпочтений невыпукло, то при некоторых ценах формируется такая бюджетная линия, которая допускает выбор одной из двух обособленных оптимальных корзин. Например, владелец зоопарка, желающий приобрести льва или орла (оцениваемых одинаково), не может приобрести часть одного животного и часть другого — его множество предпочтений не является выпуклым. Так, потребитель отказывается от приобретения строго выпуклой комбинации товаров в пользу покупки лишь одного товара в произвольном количествеШаблон:Sfn.

Если множество предпочтений потребителя невыпукло, тогда при некоторых ценах функция спроса потребителя не является связным пространством. Гарольд Хотеллинг говорил о несвязном спросе: Шаблон:Начало цитаты Если при рассмотрении покупательских кривых безразличия мы примем предположение об их волнообразном характере, выпуклом в некоторых местах и вогнутом в других, мы неизменно придём к выводу о том, что только выпуклые участки можно воспринимать как сколько-нибудь значимые, поскольку другие по существу ненаблюдаемы. Их можно обнаружить только по разрывам, которые могут возникнуть в спросе с изменением ценовых соотношений; [разрывы] приводят к резким скачкам точки касания «через пропасть», возникающим при вращении [касательной] прямой. Но, хотя эти разрывы и могут указывать на существование «пропастей», характеризовать их глубину они не смогут в принципе. Вогнутые участки кривых безразличия и их многомерные обобщения, если таковые существуют, навсегда останутся в неизмеримой неясностиШаблон:Sfn. Шаблон:OqШаблон:Конец цитаты Сложность исследования невыпуклых предпочтений отмечали Херман ВолдШаблон:SfnШаблон:Sfn и Пол Самуэльсон. Последний, согласно ДивертуШаблон:Sfn, писал, что невыпуклости «окутаны вечной тьмой»[прим. 6]Шаблон:Sfn.

Тем не менее ряд публикаций 1959—1961 годов в журнале Шаблон:Нп3 пролил свет на проблемы невыпуклых предпочтений. Ведущими исследователями в этой области стали ФарреллШаблон:SfnШаблон:SfnШаблон:Sfn, БэйторШаблон:SfnШаблон:Sfn, КупмансШаблон:SfnШаблон:Sfn и РотенбергШаблон:SfnШаблон:Sfn. В частности, в работе Ротенберга рассматривался вопрос приблизительной выпуклости сумм невыпуклых множествШаблон:Sfn. Статьи в JPE подтолкнули Шепли и Шаблон:Нп3 к написанию работы, в которой описывались «овыпукленные» отношения предпочтения потребителей. Там же была впервые упомянута концепция «приблизительного равновесия» (Шаблон:Lang-en)Шаблон:Sfn. Статья Шепли и Шубика, а также предшествующие публикации вдохновили Роберта Аумана на создание термина «квазиравновесие»Шаблон:Sfn.

Доклад Старра 1969 года и современная экономика

Файл:Kenneth Arrow, Stanford University.jpg
Кеннет Эрроу, лауреат Нобелевской премии по экономике 1972 года[прим. 2], помогал Россу Старру в изучении невыпуклых экономикШаблон:Sfn.

В годы учёбы в Стэнфордском университете Росс Старр проходил особый экономико-математический курс повышенной сложности под руководством Кеннета Эрроу. Эрроу, составивший в прошлом аннотированную библиографию публикаций на тему невыпуклости в экономике, передал её молодому коллегеШаблон:Sfn. Свою семестровую работу Старр посвятил изучению общих равновесий некой вымышленной экономики, в которой невыпуклые отношения предпочтения заменялись их выпуклыми оболочками. Совокупный спрос в этой «овыпукленной» экономике представлял собой сумму выпуклых оболочек функций спроса потребителей при каждой цене. Идеи Старра заинтересовали Шепли и Фолкмана: в рамках частной переписки учёные доказали получившие их имя лемму и теорему, а затем эти результаты были опубликованы в работе Старра 1969 годаШаблон:Sfn.

Старру удалось обнаружить, что если число агентов на рынке превосходит товарную «размерность» (количество обмениваемых товаров), то общие равновесия «овыпукленной» экономики весьма близки к квазиравновесиям исходной экономики. Экономист получил строгое доказательство того, что в подобной ситуации имеет место по крайней мере одно квазиравновесие цен popt, обладающее следующими свойствами:

  • при каждой цене все потребители могут выбирать оптимальные корзины (предпочитаемые и доступные с точки зрения бюджета),
  • при ценах popt рынок каждого товара в «овыпукленной» экономике находится в равновесии (наблюдается равенство предложения и спроса),
  • для каждого квазиравновесия цены способствуют почти полному Шаблон:Нп3: значение верхней границы расстояния между множеством равновесий «овыпукленной» экономики и множеством квазиравновесий исходной определяется королларием СтарраШаблон:SfnШаблон:Sfn.

Старр установил, что Шаблон:Начало цитаты в целом расхождение между размещением в вымышленной экономике [порождённой нахождением выпуклых оболочек всех потребительских и производственных множеств] и некоторым размещением в настоящей экономике ограничено независимо от числа экономических агентовШаблон:Sfn. Шаблон:OqШаблон:Конец цитаты Результаты Шепли, Фолкмана и Старра получили применение и в других отраслях экономической науки: микроэкономикеШаблон:SfnШаблон:Sfn, теории общего равновесияШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn, экономике общественного сектораШаблон:Sfn (в том числе в теории провалов рынкаШаблон:Sfn), а также в теории игрШаблон:Sfn, математической экономикеШаблон:Sfn и прикладной математикеШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn. Достижения Шепли, Фолкмана и Старра дали толчок внедрению теории меры множества и теории интегрирования в экономическую методологиюШаблон:Sfn.

Математическая оптимизация

A graph of a convex function, which is drawn in black. Its epigraph, the area above its graph, is solid green.
Функция считается выпуклой, если её надграфик является выпуклым множеством.

Нелинейная оптимизация базируется на следующих основных понятиях:

  • графиком функции <math>f</math> называется множество пар аргумента функции <math>x</math> и значения функции <math>f(x)</math>:
<math>Graph(f) = \{ x, f(x) \} ,</math>
<math>Epi(f) = \{ x, u; f(x) < u \} ,</math>
  • вещественная функция является выпуклой, если её надграфик является выпуклым множествомШаблон:Sfn.

Например, функции <math>f(x) = x^2</math> и <math>g(x) = |x|</math> выпуклы, а функция <math>h(x) = sinx</math> (синусоида) подобным свойством не обладает (синусоида невыпукла на интервале <math>[0, \pi]</math>).

Задачи аддитивной оптимизации

Во многих задачах оптимизации целевая функция <math>f(x)</math> сепарабельна, то есть является суммой многих слагаемых функций, каждая из которых имеет свой аргумент:

<math>f(x) = f (x_1, \ldots, x_n) = \sum f_n(x_n)</math>

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

Оптимизационные задачи могут быть «овыпуклены» путём нахождения выпуклых оболочек слагаемых функций. Оптимальное решение такой задачи является пределом последовательности[прим. 7] точек с координатами <math>(x_j, f(x_j))</math>, принадлежащих множеству <math>\sum Conv(Graph(f_n))</math>Шаблон:Sfn. Оптимальная точка, согласно лемме, является суммой <math>D</math> точек графиков «овыпукленных» слагаемых функций и некоторого числа точек графиков оригинальных функций.

Данный анализ был впервые опубликован Шаблон:Нп3 в 1974 году. Математик тогда пытался объяснить, почему сепарабельные задачи с большим числом слагаемых выпуклы при невыпуклости исходных слагаемых. За несколько месяцев до того французский учёный Шаблон:Нп3 успешно применил итеративные методы выпуклой минимизации к решению невыпуклых задач. Решение двойственной задачи нелинейной минимизации не всегда несёт информацию, полезную для решения прямой задачи (однако для выпуклых прямых задач, удовлетворяющих условиям регулярности, это не так). Задача Лемарешаля была аддитивно сепарабельной, и каждая слагаемая функция была невыпуклой. Тем не менее решение двойственной задачи давало довольно точное приближение оптимального значения для прямой задачиШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn. Анализ Экеланда прояснил причины успеха методов выпуклой минимизации, применяемых к большим и сепарабельным задачам с невыпуклыми слагаемыми функциями. Экеланд и другие учёные утверждали, что аддитивная сепарабельность позволяла считать задачу приблизительно выпуклой при невыпуклости слагаемых. Поворотным событием в данной области исследований стало обращение математиков к лемме Шепли — ФолкманаШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn. Появление леммы стимулировало использование методов выпуклой минимизации для решения других классов задач с сепарабельными функциямиШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.

Теория вероятностей и теория меры

Выпуклые множества часто изучаются в рамках теории вероятностей. Каждая точка, принадлежащая выпуклой оболочке непустого множества <math>Q</math> в конечномерном пространстве, является математическим ожиданием простого случайного вектора, который принимает значения на множестве <math>Q</math> (это следует из леммы Каратеодори[прим. 8]. Таким образом, для непустого множества <math>Q</math> набор математических ожиданий величин простого случайного вектора эквивалентен выпуклой оболочке множества <math>Q</math> — следовательно, лемма может быть применена и в этой областиШаблон:Sfn. С другой стороны, инструментами для изучения выпуклых множеств в целом и леммы в частности обладает сама теория вероятностейШаблон:Sfn. Результаты Шепли, Фолкамана и Старра широко применялись в Шаблон:Нп3Шаблон:Sfn, например, для доказательства закона больших чиселШаблон:SfnШаблон:Sfn, центральной предельной теоремыШаблон:SfnШаблон:Sfn и Шаблон:Нп3Шаблон:Sfn. Чтобы избежать допущения о выпуклом характере всех случайных множеств, при доказательстве этих предельных теорем теории вероятностей применялись результаты Шепли, Фолкмана и Старра.

Лемма имеет приложения и в тех разделах теории меры, которые не связаны с вероятностью, например, в теориях объёма и Шаблон:Нп3. Лемма позволяет уточнить теорему Брунна — Минковского, которая устанавливает отношение объёма множества-суммы и сумму объёмов множеств-слагаемыхШаблон:Sfn. Объём множества характеризуется мерой Лебега, которая определена для множеств евклидова пространства. Лемма также использовалась при доказательстве теоремы Ляпунова, которая указывает на то, что образ[прим. 9] безатомной векторной меры является выпуклымШаблон:Sfn. Векторная мера, значениями которой являются векторы, является обобщением понятия меры. К примеру, если <math>p_1</math> и <math>p_2</math> являются вероятностными мерами, определёнными на одном измеримом пространстве, тогда их функция-произведение <math>p_1 p_2</math> является векторной мерой, где <math>p_1 p_2</math> определена для каждого случайного события <math>\omega</math>:

<math>(p_1 p_2)(\omega) = (p_1(\omega), p_2(\omega))</math>

Теорема Ляпунова используется в математической экономикеШаблон:Sfn, теории Шаблон:Нп3 и Шаблон:Нп3Шаблон:Sfn. Данная теорема считается непрерывным аналогом леммы Шепли — ФолкманаШаблон:Sfn, которую, в свою очередь, называют дискретным «двойником» теоремы ЛяпуноваШаблон:Sfn.

Примечания

Комментарии

Шаблон:Примечания

Использованная литература и источники

Шаблон:Примечания

Литература

A—D

E—O

P—Z

А—Я

Шаблон:Избранная статья

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное


Ошибка цитирования Для существующих тегов <ref> группы «прим.» не найдено соответствующего тега <references group="прим."/>

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Лемма_Шепли_—_Фолкмана&oldid=10259684