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

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

Лемма Шепли-Фолкмана и связанные с ней результаты дают утвердительный ответ на вопрос: «Близка ли сумма многих множеств к выпуклости ?» ^[2] Множество определяется как выпуклое , если каждый отрезок, соединяющий две его точки, является подмножеством в множестве: например, сплошной диск  является выпуклым множеством, а окружность — нет, потому что отрезок, соединяющий две различные точки  не является подмножеством окружности. Лемма Шепли-Фолкмана предполагает, что если количество суммируемых множеств превышает размерность векторного пространства, то их сумма Минковского приблизительно выпукла. ^[1]${\ Displaystyle \ пуля}$ ${\ Displaystyle \ цирк}$${\ Displaystyle \ ослэш}$

Лемма Шепли-Фолкмана была введена как шаг в доказательстве теоремы Шепли-Фолкмана , которая устанавливает верхнюю границу расстояния между суммой Минковского и ее выпуклой оболочкой . Выпуклая оболочка множества  Q — это наименьшее выпуклое множество, содержащее  Q . Это расстояние равно нулю тогда и только тогда , когда сумма выпукла. Оценка теоремы на расстоянии зависит от размерности  D и формы наборов слагаемых, но не от количества наборов слагаемых  N , когда N > D. Формы поднабора только из  D наборов слагаемых определяют границу расстояния между  средним значением Минковского для  N  наборов

и его выпуклая оболочка. Когда  N увеличивается до бесконечности , граница уменьшается до нуля (для наборов слагаемых равномерно ограниченного размера). ^[3] Верхняя граница теоремы Шепли-Фолкмана была уменьшена следствием Старра (альтернативно, теоремой Шепли-Фолкмана-Старра ).

Лемма Ллойда Шепли и Джона Фолкмана была впервые опубликована экономистом Россом М. Старром , который исследовал существование экономического равновесия во время учебы у Кеннета Эрроу . ^[1] В своей статье Старр изучал выпуклуюэкономика, в которой невыпуклые множества заменены их выпуклыми оболочками; Старр доказал, что выпуклая экономика имеет равновесия, которые очень близки к «квазиравновесиям» исходной экономики; более того, он доказал, что каждое квазиравновесие обладает многими оптимальными свойствами истинного равновесия, существование которых доказано для выпуклой экономики. После статьи Старра 1969 года результаты Шепли-Фолкмана-Старра широко использовались, чтобы показать, что основные результаты (выпуклой) экономической теории являются хорошими приближениями к крупным экономикам с невыпуклостью; например, квазиравновесия очень близки к равновесиям выпуклой экономики. «Вывод этих результатов в общей форме был одним из главных достижений послевоенной экономической теории», — писал Роджер Геснери .Тему невыпуклых множеств в экономике изучали многие лауреаты Нобелевской премии , помимо Ллойда Шепли, получившего премию в 2012 году: Эрроу (1972), Роберт Ауманн (2005), Жерар Дебре (1983), Тьяллинг Купманс (1975), Пол Кругман (2008 г.) и Пол Самуэльсон (1970 г.); дополнительная тема выпуклых множеств в экономике была подчеркнута этими лауреатами, наряду с Леонидом Гурвичем , Леонидом Канторовичем (1975) и Робертом Солоу (1987).

Лемма Шепли-Фолкмана имеет приложения также в оптимизации и теории вероятностей . ^[3] В теории оптимизации лемма Шепли-Фолкмана использовалась для объяснения успешного решения задач минимизации, которые представляют собой суммы многих функций . ^{[5] [6]} Лемма Шепли-Фолкмана также использовалась в доказательствах « закона средних» для случайных множеств , теоремы, которая была доказана только для выпуклых множеств. ^[7]

Лемма Шепли-Фолкмана иллюстрируется сложением Минковского четырех множеств. Точка (+) в выпуклой оболочке суммы Минковского четырех невыпуклых множеств ( справа ) есть сумма четырех точек (+) из (левых) множеств — две точки в двух невыпуклых множествах плюс две точки в выпуклых оболочках двух множеств. Выпуклые оболочки окрашены в розовый цвет. Каждый исходный набор имеет ровно две точки (показаны красными точками). ^[1]

В невыпуклом множестве  Q точка на некотором отрезке, соединяющем две его точки, не является членом  Q .

Отрезки линий проверяют, будет ли подмножество выпуклым .

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

Сложение множеств Минковского. Сумма квадратов и есть квадрат .${\ Displaystyle Q_ {1} = [0,1] ^ {2}}$${\ Displaystyle Q_ {2} = [1,2] ^ {2}}$${\ Displaystyle Q_ {1} + Q_ {2} = [1,3] ^ {2} 2}$

Сложение Минковского и выпуклые оболочки. Шестнадцать темно-красных точек (справа) образуют сумму Минковского четырех невыпуклых множеств (слева), каждое из которых состоит из пары красных точек. Их выпуклые оболочки (заштрихованные розовым цветом) содержат знаки «плюс» (+): правый знак «плюс» представляет собой сумму левых знаков «плюс».

Лауреат Нобелевской премии по экономике 2012 года Ллойд Шепли доказал лемму Шепли-Фолкмана вместе с Джоном Фолкманом . ^[1]

Радиус описанной окружности (синий) и внутренний радиус (зеленый) набора точек (темно-красный, его выпуклая оболочка показана более светлыми красными пунктирными линиями). Внутренний радиус меньше радиуса описанной окружности, за исключением подмножеств одной окружности, для которых они равны.

Потребитель предпочитает каждую корзину товаров на кривой безразличия  I ₃ каждой корзине на   I ₂ . Корзина ( Q _x ,  Q _y ), в которой бюджетная линия ( показана синим цветом ) поддерживает  I ₂ , оптимальна и также осуществима, в отличие от любой корзины, лежащей на   I ₃ , которая предпочтительна, но невозможна.

Когда предпочтения потребителя имеют вогнутости, потребитель может прыгать между двумя отдельными оптимальными корзинами.

Кеннет Эрроу ( лауреат Нобелевской премии 1972 года ) помогал Россу М. Старру изучать невыпуклые экономики . ^[47]

Функция выпукла , если область над ее графиком является выпуклым множеством .

Функция синуса невыпукла . _