Лемма Шепли — ФолкманаВ литературе также используются варианты Фолкмена, Фолкманна. связывает две операции выпуклой геометрии — сложение по Минковскому и выпуклую оболочку. Лемма имеет приложения в ряде дисциплин, в том числе в математической экономике, оптимизации и теории вероятностей. Лемма и связанные с ней результаты позволяют дать утвердительный ответ на вопрос «Близка ли к состоянию выпуклости сумма нескольких множеств?».
Лемма названа в честь Ллойда Шепли и и была впервые опубликована в работе экономиста . В 2012 году Шепли наравне с Элвином Ротом стал лауреатом Нобелевской премии по экономикеПрисуждение Нобелевской премии в области экономических наук формально не является наследием Альфреда Нобеля. Премия присуждается Шведским государственным банком с 1969 года.. Работа Старра, в которой произошло первое упоминание леммы, увидела свет в 1969 году. Тогда экономист сотрудничал с известнейшим американским учёным Кеннетом Эрроу и занимался решением вопроса о существовании некоторых экономических равновесий. В работе Старра проводилось исследование экономики, в которой некоторые геометрически выраженные взаимосвязи, обладавшие свойством невыпуклости, заменялись ближайшими выпуклыми аналогами — выпуклыми оболочками. Старр доказал, что такая «овыпукленная» экономика обладает равновесными состояниями, весьма близкими к квазиравновесиям оригинальной экономики. Более того, учёный доказал, что каждое квазиравновесие обладает рядом оптимальных характеристик подлинного равновесия, которые были найдены в выпуклых экономиках. Работы Шепли, Фолкмана и Старра показали, что основные результаты выпуклой экономической теории являются хорошими приближениями экономики с невыпуклыми элементами. Лемма позволяет предположить, что если число слагаемых множеств превосходит размерность векторного пространства D, то тогда нахождение выпуклых оболочек («овыпукление») требуется только для D слагаемых. Французский экономист Роже Геснери писал: «Получение этих результатов в общем виде стало одним из главных достижений послевоенной экономической теории».
Тематика невыпуклых множеств в экономике становилась предметом исследования многих других нобелевских лауреатов. С этим вопросом работали Пол Самуэльсон (премия 1970 года), Кеннет Эрроу (1972), Тьяллинг Купманс (1975), Жерар Дебрё (1983), Роберт Ауман (2005), Пол Кругман (2008). Смежной тематикой выпуклых множеств занимались Леонид Канторович (1975), Роберт Солоу (1987), Леонид Гурвич (2007). В теории оптимизации лемма Шепли — Фолкмана использовалась для объяснения успешного решения задач минимизации сумм нескольких функций, а также для доказательства «закона средних» для случайных множеств (эта теорема была доказана только для выпуклых множеств).
Рассматриваемые категории Лемма опирается на некоторые математические категории и результаты выпуклой геометрии.
Вещественное векторное пространство
Векторным пространством называется алгебраическая структура, для элементов которой определены две операции — сложение и умножение на число (называемое «скаляром»). При этом операции подчинены восьми аксиомам: , для любых (коммутативность сложения); , для любых (ассоциативность сложения); существует такой элемент , что для любого (существование нейтрального элемента относительно сложения), в частности не пусто; для любого существует такой элемент , что (существование противоположного элемента относительно сложения). (ассоциативность умножения на скаляр); (унитарность: умножение на нейтральный по умножению скаляр сохраняет вектор). (дистрибутивность умножения на вектор относительно сложения скаляров); (дистрибутивность умножения на скаляр относительно сложения векторов), где — непустое множество элементов («векторов») данного пространства.
Важной характеристикой векторного пространства является размерность, которая характеризует максимальное число линейно независимых элементов пространства. Эти линейно независимые элементы образуют базис векторного пространства.
Выпуклое множество
Непустое множество в вещественном векторном пространстве считается выпуклым, если отрезок, соединяющий две любые точки , является подмножеством . Например, невыпуклое множество целых чисел {0, 1, 2} является подмножеством промежутка [0, 2], который обладает свойством выпуклости. Круг является выпуклым множеством, а окружность таковым считаться не может, так как не все точки отрезка будут одновременно являться точками множества: . Пустое множество считается выпуклым либо по определению, либо на основании принципа Пустой правдой называется бессодержательное утверждение обо всех элементах некоторого пустого класса. Так, импликация «если A…, то B…» станет пустой правдой, если A заведомо ложно..
Формально выпуклое множество можно определить следующим образом:
Множество является выпуклым, если для любых точек , и любого вещественного числа выполняется условие .
Выпуклой комбинацией множества называется некоторая взвешенная средняя, определённая по формуле
при условиях
Используя метод математической индукции, можно установить, что множество выпукло тогда и только тогда, когда каждая выпуклая комбинация принадлежит самому множеству: .
Определение выпуклого множества предполагает, что пересечение двух выпуклых множеств всегда выпукло. Отсюда же следует, что выпуклым является и пересечение семейства выпуклых множеств. В частности, пара непересекающихся множеств имеет пересечением пустое множество, которое, как было установлено выше, выпукло.
Выпуклая оболочка
Выпуклой оболочкой множества называется наименьшее выпуклое множество, содержащее в качестве подмножества. Наименьшее множество представляет собой наименьший элемент по отношению к вложению множеств, то есть такое выпуклое множество, содержащее данную фигуру, что оно содержится в любом другом выпуклом множестве, содержащем данную фигуру. Так, является пересечением всех выпуклых множеств, которые покрывают . К примеру, выпуклой оболочкой множества {0, 1} является отрезок числовой прямой [0, 1], содержащий целые числа 0 и 1.
Сложение Минковского
Суммой Минковского непустых множеств и в вещественном векторном пространстве является множество , состоящее из сумм всевозможных элементов слагаемых множеств:
Итак, в результате проведения операции формируется множество-сумма, включающее все возможные суммы элементов первого и второго множеств. Например, если множество, состоящее из нуля и единицы, сложить с собой же, то в результате будет получено множество, включающее ноль, единицу и двойку:
Согласно методу математической индукции, сумма Минковского конечного семейства непустых множеств при условиях
является множеством, сформированным поэлементным сложением множеств-слагаемых: .
Сумма множества и множества , содержащего только один нулевой элемент, равна : .
Выпуклая оболочка суммы Минковского Операция сложения Минковского обладает полезным свойством при «овыпуклении» множеств, то есть при нахождении их выпуклых оболочек. Для любых множеств и в вещественном векторном пространстве выпуклая оболочка их суммы Минковского равна сумме Минковского их выпуклых оболочек: . С применением математической индукции выводится аналогичное утверждение для конечного набора множеств: .
Лемма Тождество
позволяет установить, что если точка принадлежит выпуклой оболочке суммы Минковского множеств, то она принадлежит и сумме выпуклых оболочек слагаемых множеств:
Из этой импликации и определения суммы Минковского следует, что любую точку, принадлежащую множеству можно представить как сумму некоторых точек , принадлежащих выпуклым оболочкам слагаемых множеств:
В таком представлении набор суммируемых точек зависит от выбранной точки-суммы .
Лемма Шепли — Фолкмана
Примем указанное представление точки .
Если размерность векторного пространства строго меньше числа слагаемых множеств , то тогда, согласно лемме Шепли — Фолкмана, «овыпукление» требуется только для слагаемых множеств (их конкретный набор зависит от выбора точки ). Это позволяет выразить точку следующим образом:
при
Иными словами, сумма точек принадлежит выпуклой оболочке суммы множеств (или меньшего их числа), а сумма точек принадлежит сумме оставшихся множеств-слагаемых.
Содержание леммы проиллюстрируем простейшим примером: каждую точку выпуклого множества [0, 2] можно представить как сумму целого числа из невыпуклого множества {0, 1} и вещественного числа из выпуклого множества [0, 1].
Размерность Лемма позволяет делать и обратные выводы, касающиеся не множеств, но размерности векторного пространства. Если в некотором конечномерном вещественном векторном пространстве лемма выполняется для натурального числа и ни для какого числа меньше , то размерность векторного пространства равна . Разумеется, данное утверждение актуально только для конечномерных векторных пространств.
Теорема Шепли — Фолкмана и следствие Старра
Шепли и Фолкман использовали лемму для доказательства своей теоремы, в которой устанавливалась между суммой Минковского и её выпуклой оболочкой, «овыпукленной» суммой. Теорема Шепли — Фолкмана гласит, что квадрат евклидова расстояния между любой точкой «овыпукленной» суммы и соответствующей ей точкой исходной суммы не превосходит значение суммы квадратов наибольших радиусов окружностей, описанных около множеств (описанной сферой называется наименьшая сфера, включающая множество). Значение такой границы не зависит от числа слагаемых множеств, если . Следовательно, расстояние равно нулю тогда и только тогда, когда сумма сама является выпуклым множеством. При верхняя граница зависит от размерности , формы множеств-слагаемых и не зависит от количества слагаемых множеств.
Радиус описанной окружности превосходит внутренний радиус множества или, реже, равен ему. Внутренним радиусом называется наименьшее число , такое, что для любой точки существует окружность радиуса , содержащая те точки , которые охватывают центр окружности (то есть ). Внутренний радиус является характеристикой размеров невыпуклостей множества. Формально внутренний радиус множества можно определить таксм. статью «Точная верхняя и нижняя границы множеств»:
Следствие Старра к теореме установил новую (меньшую, чем у Шепли и Фолкмана) верхнюю границу между суммой и «овыпукленной» суммой:
согласно королларию Старра, квадрат евклидова расстояния между любой точкой и соответствующей ей точкой множества ограничен суммой квадратов наибольших внутренних радиусов множеств . Для меру расстояния, предложенную Старром, называют невыпуклостью ()Употребление слова «невыпуклость» в данном значении допускается только в этом разделе. В других разделах слово используется как антоним термина «выпуклость». множества. Граница, налагаемая королларием Старра на невыпуклость множества-суммы, зависит только от наибольших внутренних радиусов множеств-слагаемых и не зависит от числа слагаемых при .
Подмножество слагаемых (), точнее, их форма, определяет верхнюю границу расстояния между средним значением множеств по Минковскому
и выпуклой оболочкой этой средней. При N, стремящемся к бесконечности, максимальное расстояние стремится к нулю (для множеств-слагаемых равномерно ограниченного размера).
Доказательство Оригинальное доказательство леммы устанавливало лишь достоверность существования подобного представления точек, при этом алгоритм их нахождения в доказательстве представлен не был. Схожие доказательства были предложены Эрроу и Ханом, Касселсом, Шнейдером и другими учёными. Абстрактное и изящное доказательство представил — его работа была впоследствии дополнена Артстейном. Некоторые доказательства не были опубликованы. В 1981 году Старр опубликовал итеративный метод вычисления представления заданной точки-суммы. Тем не менее присутствовавшее в работе доказательство было менее сильным, чем оригинальное.
Приложения