Лемма Шепли – Фолкмана. - Shapley–Folkman lemma

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

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

{0, 1} + {0, 1} = {0 + 0, 0 + 1, 1 + 0, 1 + 1} = {0, 1, 2}.

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

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

​¹⁄_N (Q₁ + Q₂ + ... + Q_N)

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

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

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

Вводный пример

Например, подмножество целых чисел {0, 1, 2} содержится в интервал из действительные числа [0, 2], которая является выпуклой. Из леммы Шепли – Фолкмана следует, что каждая точка в [0, 2] является суммой целого числа из {0, 1} и действительного числа из [0, 1].^[8]

Расстояние между выпуклым интервалом [0, 2] и невыпуклым множеством {0, 1, 2} равно половине

1/2 = |1 − 1/2| = |0 − 1/2| = |2 − 3/2| = |1 − 3/2|.

Однако расстояние между средний Сумма Минковского

1/2 ( {0, 1} + {0, 1} ) = {0, 1/2, 1}

а его выпуклая оболочка [0, 1] составляет только 1/4, что составляет половину расстояния (1/2) между его слагаемым {0, 1} и [0, 1]. По мере того, как все больше наборов складывается вместе, среднее от их суммы «заполняет» его выпуклую оболочку: максимальное расстояние между средним и его выпуклой оболочкой приближается к нулю, поскольку среднее включает больше слагаемые.^[8]

Предварительные мероприятия

Лемма Шепли – Фолкмана зависит от следующих определений и вытекает из выпуклая геометрия.

Реальные векторные пространства

А настоящий векторное пространство из двухразмеры можно дать Декартова система координат в котором каждая точка обозначена упорядоченная пара действительных чисел, называемых «координатами», которые условно обозначаютсяИкс иу. Две точки в декартовой плоскости могут быть добавлен по координатам

(Икс₁, у₁) + (Икс₂, у₂) = (Икс₁+Икс₂, у₁+у₂);

далее точка может быть умноженный по каждому действительному числуλ по координатам

λ (Икс, у) = (λx, λy).

В более общем смысле, любое реальное векторное пространство (конечной) размерностиD можно рассматривать как набор из всех D- пары изD действительные числа { (v₁, v₂, . . . , v_D) } на котором дваоперации определены: векторное сложение и умножение на действительное число. Для конечномерных векторных пространств каждая операция сложения векторов и умножения действительных чисел может быть определена покоординатно, следуя примеру декартовой плоскости.^[9]

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

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

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

Сегменты линии проверить, может ли подмножество быть выпуклый.

В реальном векторном пространстве непустой наборQ определяется как выпуклый если для каждой пары своих точек каждая точка на отрезок что присоединяется к ним подмножество изQ. Например, твердый диск  ${\displaystyle \bullet }$ выпуклый, но круг  ${\displaystyle \circ }$ нет, потому что он не содержит отрезка линии, соединяющего его точки${\displaystyle \oslash }$; невыпуклый набор из трех целых чисел {0, 1, 2} содержится в интервале [0, 2], который является выпуклым. Например, твердый куб выпуклый; однако все, что является полым или помятым, например, полумесяц форма, невыпуклая. В пустой набор выпукло, либо по определению^[10] или же бессмысленно, в зависимости от автора.

Более формально наборQ выпукло, если для всех точекv₀ иv₁ вQ и для каждого реального числаλ в единичный интервал [0,1], точка

(1 − λ) v₀ + λv₁

это член изQ.

К математическая индукция, множествоQ выпукло тогда и только тогда, когда каждое выпуклое сочетание членовQ также принадлежитQ. По определению выпуклое сочетание индексированного подмножества {v₀, v₁, . . . , v_D} векторного пространства - любое средневзвешенноеλ₀v₀ + λ₁v₁ + . . . + λ_Dv_D, для некоторого индексированного набора неотрицательных действительных чисел {λ_d} удовлетворяющий уравнениюλ₀ + λ₁ + . . .  + λ_D = 1.^[11]

Из определения выпуклого множества следует, что пересечение из двух выпуклых множеств является выпуклым множеством. В более общем смысле, пересечение семейства выпуклых множеств является выпуклым множеством. В частности, пересечение двух непересекающиеся множества - пустое множество, которое выпукло.^[10]

Выпуклый корпус

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

Для каждого подмножестваQ реального векторного пространства, его выпуклый корпус Конв (Q) это минимальный выпуклое множество, содержащееQ. Таким образом, Conv (Q) является пересечением всех выпуклых множеств, которые крышка  Q. Выпуклая оболочка множества может быть эквивалентно определена как множество всех выпуклых комбинаций точек вQ.^[12] Например, выпуклая оболочка множества целые числа {0,1} - закрытый интервал из действительные числа [0,1], который содержит целые конечные точки.^[8] Выпуклая оболочка единичный круг закрытый единичный диск, который содержит единичный круг.

Дополнение Минковского

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

В любом векторном пространстве (или алгебраической структуре с добавлением) ${\displaystyle X}$, то Сумма Минковского из двух непустых множеств ${\displaystyle A,B\subseteq X}$ определяется как поэлементная операция ${\displaystyle A+B:=\{x+y\mid x\in A,~y\in B\}.}$ (Смотрите также.^[13])Например

${\displaystyle \{0,1\}+\{0,1\}=\{0+0,0+1,1+0,1+1\}=\{0,1,2\}}$

Эта операция явно коммутативна и ассоциативна на совокупности непустых множеств. Все такие операции четко определенным образом распространяются на рекурсивные формы. ${\displaystyle \sum _{n=1}^{N}Q_{n}=Q_{1}+Q_{2}+\ldots +Q_{N}.}$ По принципу индукции легко видеть, что^[14]

${\displaystyle \sum _{n=1}^{N}Q_{n}=\{\sum _{n=1}^{N}q_{n}\mid q_{n}\in Q_{n},~1\leq n\leq N\}.}$

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

Сложение Минковского хорошо себя ведет по отношению к выпуклым оболочкам. В частности, для всех подмножеств ${\displaystyle A,B\subseteq X}$ реального векторного пространства, ${\displaystyle X}$, то выпуклый корпус их суммы Минковского - это сумма Минковского их выпуклых оболочек. То есть,

${\displaystyle \mathrm {Conv} (A+B)=\mathrm {Conv} (A)+\mathrm {Conv} (B).}$

И по индукции следует, что

${\displaystyle \mathrm {Conv} (\sum _{n=1}^{N}Q_{n})=\sum _{n=1}^{N}\mathrm {Conv} (Q_{n})}$

для любого ${\displaystyle N\in \mathbb {N} }$ и непустые подмножества ${\displaystyle Q_{n}\subseteq X}$, ${\displaystyle 1\leq n\leq N}$.^[15][16]

Заявления

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

По предыдущему тождеству для каждой точки ${\displaystyle x\in \mathrm {Conv} (\sum _{n=1}^{N}Q_{n})}$ в выпуклой оболочке есть элементы, ${\displaystyle q_{n}(x)\in \mathrm {Conv} (Q_{n})}$ за ${\displaystyle 1\leq n\leq N}$в зависимости от ${\displaystyle x}$, и такой, что ${\displaystyle \sum _{n=1}^{N}q_{n}(x)=x}$.

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

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

Работая с описанной выше настройкой, Лемма Шепли – Фолкмана. заявляет, что в приведенном выше представлении

${\displaystyle x=\sum _{n=1}^{N}q_{n}(x)}$

в большинстве ${\displaystyle D}$ слагаемых ${\displaystyle q_{n}(x)}$ нужно брать строго с выпуклых оболочек. То есть существует представление указанной выше формы такое, что ${\displaystyle |\{l\leq n\leq N\mid q_{n}(x)\in \mathrm {Conv} (Q_{n})\setminus Q_{n}\}|\leq D}$. При необходимости перетасовка индексов, это означает, что точка имеет представление

${\displaystyle x=\sum _{n=1}^{D}q_{n}(x)+\sum _{n=D+1}^{N}q_{n}(x)}$

куда ${\displaystyle q_{n}\in \mathrm {Conv} (Q_{n})}$ за ${\displaystyle 1\leq n\leq D}$и ${\displaystyle q_{n}\in Q_{n}}$ за ${\displaystyle D+1\leq n\leq N}$. Обратите внимание, что повторная индексация зависит от точки.^[17] Более лаконично, лемма Шепли – Фолкмана утверждает, что

${\displaystyle \mathrm {Conv} (\sum _{n=1}^{N}Q_{n})\subseteq \bigcup _{I\subseteq \{1,2,\ldots N\}:~|I|=D}\sum _{n\in I}\mathrm {Conv} (Q_{n})+\sum _{n\notin I}Q_{n}.}$

Например, каждая точка в ${\displaystyle [0,2]=[0,1]+[0,1]=\mathrm {Conv} (\{0,1\})+\mathrm {Conv} (\{0,1\})}$ согласно лемме является суммой элемента в ${\displaystyle \{0,1\}}$ и элемент в ${\displaystyle [0,1]}$.^[8]

Размерность реального векторного пространства

Наоборот, лемма Шепли – Фолкмана характеризует измерение конечномерных вещественных векторных пространств. То есть, если векторное пространство подчиняется лемме Шепли – Фолкмана для натуральное число  D, и не менее чемD, то его размерность в точности равнаD;^[18] лемма Шепли – Фолкмана верна только для конечномерный векторные пространства.^[19]

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

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

Шепли и Фолкман использовали свою лемму для доказательства своей теоремы, которая ограничивает расстояние между суммой Минковского и ее выпуклой оболочкой, т.е.выпуклый"сумма:

• В Теорема Шепли – Фолкмана заявляет, что квадрат Евклидово расстояние из любой точки выпуклой суммыКонв (∑Q_п ) к исходной (неквексированной) сумме∑ Q_п ограничен суммой квадратовD наибольшие описанные радиусы наборовQ_п (радиусы наименьшие сферы, охватывающие эти наборы ).^[20] Эта оценка не зависит от количества слагаемыхN (еслиN > D).^[21]

Теорема Шепли – Фолкмана устанавливает ограничение на расстояние между суммой Минковского и ее выпуклой оболочкой; это расстояние равно нулю если и только если сумма выпуклая. Их оценка по расстоянию зависит от размерностиD и формы слагаемых-множеств, но нет от количества слагаемыхN, когда N > D.^[3]

Окружной радиус часто превышает (и не может быть меньше) внутренний радиус:^[22]

• В внутренний радиус набораQ_п определяется как наименьшее числор так что для любой точкиq в выпуклой оболочкеQ_п, Существует сфера радиусар который содержит подмножествоQ_п выпуклая оболочка которого содержитq.

Старр использовал внутренний радиус для уменьшения верхней границы, сформулированной в теореме Шепли – Фолкмана:

• Следствие Старра из теоремы Шепли – Фолкмана. утверждает, что квадрат евклидова расстояния от любой точкиИкс в выпуклой суммеКонв (∑Q_п ) к исходной (неквексированной) сумме∑ Q_п ограничен суммой квадратовD наибольшие внутренние радиусы наборовQ_п.^[22][23]

Следствие Старра утверждает верхняя граница на евклидовом расстоянии между суммой МинковскогоN множества и выпуклая оболочка суммы Минковского; это расстояние между суммой и ее выпуклой оболочкой является мерой невыпуклости множества. За простота, это расстояние называется "невыпуклость"множества (относительно измерения Старра). Таким образом, оценка Старра на невыпуклость суммы зависит только отD наибольшие внутренние радиусы слагаемых; однако оценка Старра не зависит от количества слагаемых-множествN, когдаN > D. Например, расстояние между выпуклым интервалом [0, 2] и невыпуклым множеством {0, 1, 2} равно половине

1/2 = |1 − 1/2| = |0 − 1/2| = |2 − 3/2| = |1 − 3/2|.

Таким образом, оценка Старра невыпуклости средний

​¹⁄_N ∑ Q_п

уменьшается с увеличением количества слагаемыхN увеличивается. Например, расстояние между усредненный набор

1/2 ( {0, 1} + {0, 1} ) = {0, 1/2, 1}

а его выпуклая оболочка [0, 1] составляет только 1/4, что составляет половину расстояния (1/2) между его слагаемым {0, 1} и [0, 1]. Формы подколлекции толькоD наборы слагаемых определяют границу расстояния между средний набор и его выпуклая оболочка; таким образом, при увеличении числа слагаемых до бесконечность, граница уменьшается до нуля (для множеств слагаемых равномерно ограниченного размера).^[3] Фактически, оценка Старра невыпуклости этого среднего множества уменьшается до нуля как количество слагаемыхN увеличивается до бесконечность (когда внутренние радиусы всех слагаемых ограничены одним числом).^[3]

Доказательства и вычисления

Первоначальное доказательство леммы Шепли – Фолкмана установило только существование представительства, но не предоставил алгоритм для вычисления представления: аналогичные доказательства были даны Стрелка и Хан,^[24] Cassels,^[25] и Шнайдер,^[26] среди прочего. Абстрактное и элегантное доказательство Ekeland был расширен Artstein.^[27][28] Различные доказательства появлялись и в неопубликованных работах.^[2][29] В 1981 году Старр опубликовал итерационный метод для вычисления представления заданной точки суммы; однако его вычислительное доказательство дает более слабую оценку, чем исходный результат.^[30] Элементарное доказательство леммы Шепли – Фолкмана в конечномерном пространстве можно найти в книге Бертсекас^[31]вместе с приложениями для оценки разрыва двойственности в задачах разделимой оптимизации и играх с нулевой суммой.

Приложения

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

Экономика

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

Смотрите также: Выпуклость в экономике

В экономика, потребительский предпочтения определяются по всем «корзинам» товаров. Каждая корзина представлена ​​в виде неотрицательного вектора, координаты которого представляют количество товаров. На этом наборе корзин кривая безразличия определяется для каждого потребителя; кривая безразличия потребителя включает все корзины товаров, которые потребитель считает эквивалентными: то есть для каждой пары корзин на одной кривой безразличия потребитель не предпочитает одну корзину другой. Через каждую товарную корзину проходит одна кривая безразличия. Потребительский набор предпочтений (относительно кривой безразличия) союз кривой безразличия и всех товарных корзин, которые потребитель предпочитает кривой безразличия. Потребительский предпочтения находятся выпуклый если все такие множества предпочтений выпуклые.^[32]

Оптимальная корзина товаров возникает там, где бюджетная линия поддерживает набор предпочтений потребителя, как показано на схеме. Это означает, что оптимальная корзина находится на максимально возможной кривой безразличия с учетом линии бюджета, которая определяется в терминах вектора цен и дохода потребителя (вектора обеспеченности). Таким образом, набор оптимальных корзин представляет собой функция цен, и эта функция называется потребительской требовать. Если набор предпочтений выпуклый, то при каждой цене потребительский спрос представляет собой выпуклый набор, например, уникальную оптимальную корзину или линейный сегмент корзин.^[33]

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

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

Смотрите также: Невыпуклость (экономика)

Однако, если установлен предпочтительный невыпуклый, то некоторые цены определяют бюджетную линию, которая поддерживает два отдельный оптимальные корзины. Например, мы можем представить, что для зоопарков лев стоит столько же, сколько орел, и, кроме того, бюджета зоопарка хватит на одного орла или одного льва. Можно также предположить, что смотритель зоопарка считает любое животное равноценным. В этом случае зоопарк покупал либо одного льва, либо одного орла. Конечно, современный зоопарк не хочет покупать половину орла и половину льва (или грифон )! Таким образом, предпочтения хранителя зоопарка невыпуклые: хранитель зоопарка предпочитает иметь любое животное, а не любую строго выпуклую их комбинацию.^[34]

Когда набор предпочтений потребителя невыпуклый, то (для некоторых цен) потребительский спрос не является выпуклым. связаны; отключенный спрос подразумевает некоторое прерывистое поведение потребителя, как обсуждается Гарольд Хотеллинг:

Если рассматривать кривые безразличия для покупок как имеющие волнистый характер, выпуклые к исходной точке в одних регионах и вогнутые в других, мы вынуждены прийти к выводу, что только части, выпуклые к исходной точке, можно рассматривать как имеющие какое-либо значение. , поскольку остальные практически не наблюдаются. Их можно обнаружить только по скачкам спроса, которые могут возникать при изменении соотношений цен, что приводит к резкому скачку точки касания через пропасть при вращении прямой линии. Но, хотя такие разрывы могут указывать на существование пропастей, они никогда не могут измерить их глубину. Вогнутые части кривых безразличия и их многомерные обобщения, если они существуют, должны навсегда остаться в неизмеримой безвестности.^[35]

Трудности изучения невыпуклых предпочтений подчеркнули Герман Вольд^[36] и снова Пол Самуэльсон, писавший, что невыпуклости «окутаны вечным тьма ... ",^[37] согласно Диверту.^[38]

Тем не менее, невыпуклые предпочтения были освещены с 1959 по 1961 год благодаря серии статей в Журнал политической экономии  (JPE). Основными участниками были Фаррелл,^[39] Батор,^[40] Купманс,^[41] и Ротенберг.^[42] В частности, в статье Ротенберга обсуждалась приближенная выпуклость сумм невыпуклых множеств.^[43] Эти JPEбумаги стимулировали бумагу Ллойд Шепли и Мартин Шубик, который рассмотрел выпуклые потребительские предпочтения и ввел понятие «приблизительного равновесия».^[44] В JPEбумаги и статья Шепли-Шубика повлияли на другое понятие «квазиравновесия», поскольку Роберт Ауманн.^[45][46]

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

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

Предыдущие публикации на невыпуклость и экономика были собраны в аннотированной библиографии Кеннет Эрроу. Он дал библиографию Старр, который в то время был студентом, поступившим на курс продвинутого математико-экономического факультета Эрроу.^[47] В своей курсовой работе Старр изучал общие равновесия искусственной экономики, в которой невыпуклые предпочтения заменены их выпуклой оболочкой. В выпуклой экономике при каждой цене совокупный спрос представляла собой сумму выпуклых корпусов требований потребителей. Идеи Старра заинтересовали математиков Ллойд Шепли и Джон Фолкман, которые доказали свою одноименный лемма и теорема в «частной переписке», о которых сообщалось в опубликованной статье Старра 1969 года.^[1]

В своей публикации 1969 года Старр применил теорему Шепли – Фолкмана – Старра. Старр доказал, что «выпуклая» экономика имеет общие равновесия, которые можно точно аппроксимировать следующим образом:квазиравновесия«исходной экономики, когда количество агентов превышает размер товаров: Конкретно, Старр доказал, что существует по крайней мере одно квазиравновесие цен.п_{выбрать} со следующими свойствами:

• Для каждой цены квазиравновесияп_{выбрать}, все потребители могут выбрать оптимальные корзины (максимально предпочтительные и соответствующие их бюджетным ограничениям).
• По квазиравновесным ценамп_{выбрать} в выпуклой экономике рынок каждого товара находится в равновесии: его предложение равно его спросу.
• Для каждого квазиравновесия цены "почти очищают" рынки исходной экономики: верхняя граница на расстояние между множеством равновесий «выпуклой» экономики и множеством квазиравновесий исходной экономики следует из следствия Старра к теореме Шепли – Фолкмана.^[48]

Старр установил, что

"в совокупности несоответствие между распределением в фиктивной экономике, порожденным [взятием выпуклой оболочки всех наборов потребления и производства], и некоторым распределением в реальной экономике ограничено способом, который не зависит от количества экономических Таким образом, средний агент испытывает отклонение от намеченных действий, значение которого исчезает по мере того, как число агентов стремится к бесконечности ".^[49]

После статьи Старра 1969 года результаты Шепли – Фолкмана – Старра широко использовались в экономической теории. Роджер Гезнери резюмировали их экономические последствия: «Некоторые ключевые результаты, полученные в предположении выпуклости, остаются (приблизительно) актуальными в обстоятельствах, когда выпуклость не работает. Например, в странах с большой стороной потребления невыпуклость предпочтений не разрушает стандартные результаты».^[50] «Получение этих результатов в общей форме было одним из главных достижений послевоенной экономической теории», - писал Гезнери.^[4] Тема невыпуклые множества в экономике был изучен многими Нобелевские лауреаты: Стрела (1972), Роберт Ауманн (2005), Жерар Дебре (1983), Тьяллинг Купманс (1975), Пол Кругман (2008), и Пол Самуэльсон (1970); дополнительная тема выпуклые множества в экономике отмечен этими лауреатами, а также Леонид Гурвич, Леонид Канторович (1975), и Роберт Солоу (1987).^[51] Результаты Шепли – Фолкмана – Старра были представлены в экономической литературе: в микроэкономика,^[52] в теории общего равновесия,^[53][54] в общественная экономика^[55] (включая провалы рынка ),^[56] а также в теория игры,^[57] в математическая экономика,^[58] И в Прикладная математика (для экономистов).^[59][60] Результаты Шепли – Фолкмана – Старра также повлияли на экономические исследования с использованием мера и теория интеграции.^[61]

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

А функция является выпуклый если область выше ее график это выпуклый набор.

Лемма Шепли – Фолкмана использовалась, чтобы объяснить, почему большие минимизация проблемы с невыпуклость может быть почти решена (с итерационные методы доказательства сходимости которого приведены только для выпуклые задачи ). Лемма Шепли – Фолкмана поощряет использование методов выпуклой минимизации в других приложениях с суммами многих функций.^[62]

Предварительные сведения по теории оптимизации

Нелинейная оптимизация опирается на следующие определения для функции:

• В график функцииж - это множество пар аргументы  Икс и оценки функцийж(Икс)

График (ж) = { (Икс, ж(Икс) ) }

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

В функция синуса является невыпуклый.

Эпи (ж) = { (Икс, ты) : ж(Икс) ≤ ты }.

• Действительнозначная функция определяется как выпуклая функция если его надграфик - выпуклое множество.^[63]

Например, квадратичная функция  ж(Икс) = Икс² выпуклая, как и абсолютная величина функцияграмм(Икс) = |Икс|, Тем не менее функция синуса (на фото) невыпуклый на интервал (0, π).

Проблемы аддитивной оптимизации

Во многих задачах оптимизации целевая функция f это отделяемый: то есть, ж это сумма много слагаемые-функции, каждая из которых имеет свой аргумент:

ж(Икс) = ж( (Икс₁, ..., Икс_N) ) = ∑ ж_п(Икс_п).

Например, проблемы линейная оптимизация отделимы. Для отделимой задачи с оптимальным решением фиксируем оптимальное решение

Икс_мин = (Икс₁, ..., Икс_N)_мин

с минимальным значениемж(Икс_мин). Для этой сепарабельной задачи мы также рассматриваем оптимальное решение (Икс_мин, ж(Икс_мин) )к "выпуклая задача", где берутся выпуклые оболочки графиков слагаемых функций. Таким оптимальным решением является предел последовательности точек выпуклой задачи

(Икс_j, ж(Икс_j) ) ∈  ∑ Конв. (График ( ж_п ) ).^[5][64]

Конечно, данная оптимальная точка является суммой точек на графиках исходных слагаемых и небольшого числа выпуклых слагаемых согласно лемме Шепли – Фолкмана.

Этот анализ был опубликован Ивар Экеланд в 1974 г., чтобы объяснить кажущуюся выпуклость сепарабельных задач со многими слагаемыми, несмотря на невыпуклость проблем с слагаемыми. В 1973 году молодой математик Клод Лемарешаль был удивлен его успехом с выпуклая минимизация методы о задачах, которые заведомо невыпуклые; за минимизация нелинейных проблемы, решение двойная проблема не нужно предоставлять полезную информацию для решения основной задачи, если только основная задача не является выпуклой и удовлетворяет ограничение квалификации. Проблема Лемарешала была аддитивно отделимой, и каждая функция слагаемого была невыпуклой; тем не менее, решение двойной задачи обеспечило близкое приближение к оптимальному значению прямой задачи.^[65][5][66] Анализ Экланда объяснил успех методов выпуклой минимизации на большой и отделяемый проблемы, несмотря на невыпуклость слагаемых функций. Экеланд и более поздние авторы утверждали, что аддитивная отделимость порождает приблизительно выпуклую совокупную проблему, даже несмотря на то, что слагаемые функции невыпуклые. Решающим шагом в этих публикациях является использование леммы Шепли – Фолкмана.^[5][66][67] Лемма Шепли – Фолкмана поощряет использование методов выпуклой минимизации в других приложениях с суммами многих функций.^{[5][6][59][62]}

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

Выпуклые множества часто изучаются с помощью теория вероятности. Каждая точка выпуклой оболочки (непустой ) подмножествоQ конечномерного пространства - это ожидаемое значение из просто случайный вектор что принимает свои ценности вQ, как следствие Лемма Каратеодори. Таким образом, для непустого множестваQ, набор ожидаемых значений простого, Q-значные случайные векторы равныQс выпуклый корпус; это равенство означает, что результаты Шепли – Фолкмана – Старра полезны в теории вероятностей.^[68] С другой стороны, теория вероятностей предоставляет инструменты для изучения выпуклых множеств в целом и результатов Шепли – Фолкмана – Старра в частности.^[69] Результаты Шепли – Фолкмана – Старра широко использовались в вероятностная теория случайных множеств,^[70] например, чтобы доказать закон больших чисел,^[7][71] а Центральная предельная теорема,^[71][72] и большие отклонения  принцип.^[73] Эти доказательства вероятностные предельные теоремы использовали результаты Шепли – Фолкмана – Старра, чтобы избежать предположения, что все случайные множества выпуклые.

А вероятностная мера конечный мера, а лемма Шепли – Фолкмана находит применения в не вероятностной теории меры, например в теориях объем и из векторные меры. Лемма Шепли – Фолкмана позволяет уточнить Неравенство Брунна – Минковского., что ограничивает объем сумм через объем их слагаемых.^[74] Объем набора определяется исходя из Мера Лебега, который определен на подмножествах Евклидово пространство. В продвинутой теории меры лемма Шепли – Фолкмана использовалась для доказательства Теорема Ляпунова, в котором говорится, что классифицировать из векторная мера выпуклый.^[75] Здесь традиционный термин "классифицировать"(альтернативно" изображение ") - это набор значений, производимых функцией. A векторная мера является векторным обобщением меры; например, еслип₁ ип₂ находятся вероятностные меры определены на том же измеримое пространство, то функция продукта  п₁ п₂ - векторная мера, гдеп₁ п₂ определяется для каждого мероприятие  ω к

(п₁ п₂)(ω)=(п₁(ω), п₂(ω)).

Теорема Ляпунова использовалась в экономика,^[45][76] в ("ПИФ-паф" ) теория управления, И в статистическая теория.^[77] Теорема Ляпунова получила название непрерывный аналог леммы Шепли – Фолкмана,^[3] который сам был назван дискретный аналог теоремы Ляпунова.^[78]

Примечания

1. Старр (1969)
2. Хау (1979), п. 1) Ошибка harvtxt: несколько целей (2 ×): CITEREFHowe1979 (помощь): Хау, Роджер (3 ноября 1979 г.). О тенденции к выпуклости векторной суммы множеств (PDF) (Отчет). Документы для обсуждения Фонда Коулза. 538. Box 2125 Yale Station, New Haven, CT 06520: Фонд Коулза для исследований в области экономики, Йельский университет. Получено 1 января 2011.
3. Старр (2008)
4. Гезнери (1989, п. 138)
5. (Ekeland 1999, pp. 357–359): опубликованное в первом английском издании 1976 г., приложение Экланда доказывает лемму Шепли – Фолкмана, также признавая Lemaréchal Эксперименты на странице 373.
6. Бертсекас (1996 г., pp. 364–381) с признательностью Экеланд (1999) на странице 374 и Обен и Экланд (1976) на странице 381:

   Бертсекас, Дмитрий П. (1996). «5.6. Крупномасштабные разделяемые задачи целочисленного программирования и экспоненциальный метод множителей». Оптимизация с ограничениями и методы множителя Лагранжа (Перепечатка (1982) изд. Academic Press). Бельмонт, Массачусетс: Athena Scientific. С. xiii + 395. ISBN  1-886529-04-3. МИСТЕР  0690767.

   Бертсекас (1996 г., pp. 364–381) описывает применение Лагранжев двойственный методы для планирование из электростанции ("проблемы с обязательствами подразделения "), где невыпуклость возникает из-за целочисленные ограничения:

   Бертсекас, Дмитрий П.; Лауэр, Грегори С .; Sandell, Nils R., Jr .; Посберг, Томас А. (январь 1983 г.). «Оптимальное краткосрочное планирование крупномасштабных энергосистем» (PDF). IEEE Transactions по автоматическому контролю. 28 (1): 1–11. Дои:10.1109 / tac.1983.1103136. Получено 2 февраля 2011. Протоколы конференции IEEE 1981 г. по вопросам принятия решений и контроля, Сан-Диего, Калифорния, декабрь 1981 г., стр. 432–443.

7. Арштейн и Витале (1975), стр. 881–882): Арстейн, Цви; Витале, Ричард А. (1975). «Усиленный закон больших чисел для случайных компактов». Анналы вероятности. 3 (5): 879–882. Дои:10.1214 / aop / 1176996275. JSTOR  2959130. МИСТЕР  0385966. Zbl  0313.60012. PE  euclid.ss / 1176996275.
8. Картер (2001), п. 94)
9. Стрелка и Хан (1980), п. 375)
10. Рокафеллар (1997), п. 10)
11. Стрелка и Хан (1980), п. 376), Рокафеллар (1997), стр. 10–11), и Грин и Хеллер (1981, п. 37)
12. Стрелка и Хан (1980), п. 385) и Рокафеллар (1997), стр. 11–12).
13. Шнайдер (1993, п. xi) и Рокафеллар (1997), п. 16)
14. Рокафеллар (1997), п. 17) и Старр (1997, п. 78)
15. Шнайдер (1993, стр. 2–3)
16. Стрелка и Хан (1980), п. 387)
17. Старр (1969, стр. 35–36).
18. Шнайдер (1993, п. 131)
19. Шнайдер (1993, п. 140) приписывает этот результат Борвейн и О'Брайен (1978): Борвейн, Дж. М.; О'Брайен, Р. К. (1978). «Гашение характеризует выпуклость». Nanta Mathematica (Университет Наньян). 11: 100–102. ISSN  0077-2739. МИСТЕР  0510842.
20. Шнайдер (1993, п. 129)
21. Старр (1969, п. 36)
22. Старр (1969, п. 37)
23. Шнайдер (1993, стр. 129–130).
24. Стрелка и Хан (1980), стр. 392–395).
25. Кассель (1975), стр. 435–436).
26. Шнайдер (1993, п. 128)
27. Экланд (1999), стр. 357–359).
28. Арштейн (1980), п. 180)
29. Андерсон, Роберт М. (14 марта 2005 г.). "1 Теорема Шепли – Фолкмана" (PDF). Экономика 201B: невыпуклые предпочтения и приблизительные равновесия. Беркли, Калифорния: экономический факультет Калифорнийского университета в Беркли. стр. 1–5. Получено 1 января 2011.
30. Старр, Росс М. (1981). «Приближение точек выпуклой оболочки суммы множеств точками суммы: элементарный подход». Журнал экономической теории. 25 (2): 314–317. Дои:10.1016/0022-0531(81)90010-7. МИСТЕР  0640201.
31. Бертсекас, Дмитрий П. (2009). Теория выпуклой оптимизации. Бельмонт, Массачусетс: Athena Scientific. ISBN  978-1-886529-31-1.
32. Мас-Колелл (1985, pp. 58–61) и Стрелка и Хан (1980), стр. 76–79).
33. Стрелка и Хан (1980), стр. 79–81).
34. Старр (1969, п. 26): «В конце концов, можно безразлично выбирать между автомобилем и лодкой, но в большинстве случаев нельзя ни водить, ни плыть на комбинации полумара и полуавтомобиля».
35. Хотеллинг (1935, п. 74):Хотеллинг, Гарольд (Январь 1935 г.). «Спрос функционирует с ограниченным бюджетом». Econometrica. 3 (1): 66–78. Дои:10.2307/1907346. JSTOR  1907346.
36. Уолд (1943b, стр. 231 и 239–240): Уолд, Герман (1943b). "Синтез чистого анализа спросаII". Skandinavisk Aktuarietidskrift [Скандинавский актуарный журнал]. 26: 220–263. Дои:10.1080/03461238.1943.10404737. МИСТЕР  0011939.

    Уолд и Журин (1953), п. 146): Уолд, Герман; Юрин, Ларс (совместно с Уолдом) (1953). «8 Некоторые дальнейшие применения полей предпочтений (стр. 129–148)». Анализ спроса: исследование по эконометрике. Публикации Wiley по статистике. Нью-Йорк: John Wiley and Sons, Inc., стр. Xvi + 358. МИСТЕР  0064385.

37. Самуэльсон (1950, стр. 359–360):

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

    Самуэльсон, Пол А. (Ноябрь 1950 г.). «Проблема интегрируемости в теории полезности». Economica. Новая серия. 17 (68): 355–385. Дои:10.2307/2549499. JSTOR  2549499. МИСТЕР  0043436.

    «Вечная тьма» описывает Ад Джон Милтон с потерянный рай, чья вогнутость сравнивается с Безвыходное положение в Книга II, строки 592–594:

    Глубокая пропасть, как сербонское болото
    Betwixt Damiata и гора Casius старый,
    Где целые армии утонули.

    Описание Милтоном вогнутости служит литературный эпиграф перед седьмой главой Стрелка и Хан (1980), п. 169), «Рынки с невыпуклыми предпочтениями и производством», в котором представлены результаты Старр (1969).
38. Диверт (1982, стр. 552–553).
39. Фаррелл, М. Дж. (Август 1959 г.). «Предположение о выпуклости в теории конкурентных рынков». Журнал политической экономии. 67 (4): 371–391. Дои:10.1086/258197. JSTOR  1825163.Фаррелл, М. Дж. (Октябрь 1961 г.). «О выпуклости, эффективности и рынках: ответ». Журнал политической экономии. 69 (5): 484–489. Дои:10.1086/258541. JSTOR  1828538.Фаррелл, М. Дж. (Октябрь 1961b). «Предположение о выпуклости в теории конкурентных рынков: возражение». Журнал политической экономии. 69 (5): 493. Дои:10.1086/258544. JSTOR  1828541.
40. Батор, Фрэнсис М. (октябрь 1961a). «О выпуклости, эффективности и рынках». Журнал политической экономии. 69 (5): 480–483. Дои:10.1086/258540. JSTOR  1828537. Батор, Фрэнсис М. (октябрь 1961b). «О выпуклости, эффективности и рынках: ответ». Журнал политической экономии. 69 (5): 489. Дои:10.1086/258542. JSTOR  1828539.
41. Купманс, Тьяллинг К. (Октябрь 1961 г.). «Допущения выпуклости, эффективность распределения и конкурентное равновесие». Журнал политической экономии. 69 (5): 478–479. Дои:10.1086/258539. JSTOR  1828536.

    Купманс (1961, п. 478) и другие, например, Фаррелл (1959, pp. 390–391) и Фаррелл (1961a, п. 484), Батор (1961а), стр. 482–483), Ротенберг (1960 г., п. 438), и Старр (1969, п. 26) - прокомментировал Купманс (1957, стр. 1–126, особенно 9–16 [1.3 Суммирование множеств возможностей], 23–35 [1.6 Выпуклые множества и последствия оптимальности для цены] и 35–37 [1.7 Роль предположений о выпуклости в анализе]) :

    Купманс, Тьяллинг К. (1957). «Размещение ресурсов и система цен». В Купманс, Тьяллинг С (ред.). Три очерка о состоянии экономической науки. Нью-Йорк: Книжная компания Макгроу-Хилл. С. 1–126. ISBN  0-07-035337-9.

42. Ротенберг (1960 г., п. 447): Ротенберг, Джером (октябрь 1960). «Невыпуклость, агрегирование и оптимальность по Парето». Журнал политической экономии. 68 (5): 435–468. Дои:10.1086/258363. JSTOR  1830308. (Ротенберг, Джером (октябрь 1961 г.). «Комментарии о невыпуклости». Журнал политической экономии. 69 (5): 490–492. Дои:10.1086/258543. JSTOR  1828540.)
43. Стрелка и Хан (1980), п. 182)
44. Шепли и Шубик (1966), п. 806): Шепли, Л.С.; Шубик, М. (Октябрь 1966 г.). «Квазиядра в монетарной экономике с невыпуклыми предпочтениями». Econometrica. 34 (4): 805–827. Дои:10.2307/1910101. JSTOR  1910101. Zbl  0154.45303.
45. Ауманн (1966, стр. 1–2): Ауманн, Роберт Дж. (Январь 1966 г.). «Существование конкурентного равновесия на рынках с континуумом трейдеров». Econometrica. 34 (1): 1–17. Дои:10.2307/1909854. JSTOR  1909854. МИСТЕР  0191623. Ауманн (1966) использует результаты Aumann (1964, 1965 ):

    Ауманн, Роберт Дж. (Январь – апрель 1964 г.). «Рынки с континуумом трейдеров». Econometrica. 32 (1–2): 39–50. Дои:10.2307/1913732. JSTOR  1913732. МИСТЕР  0172689.

    Ауманн, Роберт Дж. (Август 1965 г.). «Интегралы от многозначных функций». Журнал математического анализа и приложений. 12 (1): 1–12. Дои:10.1016 / 0022-247X (65) 90049-1. МИСТЕР  0185073.

46. Использование выпуклой оболочки невыпуклых предпочтений обсуждалось ранее. Уолд (1943b, п. 243) и Уолд и Журин (1953), п. 146), согласно Диверт (1982, п. 552).

47. Старр и Стинчкомб (1999), стр. 217–218): Старр, Р. М.; Стинчкомб, М. Б. (1999). «Обмен в сети торговых постов». В Чичильнский, Грасиела (ред.). Рынки, информация и неопределенность: Очерки экономической теории в честь Кеннета Дж. Эрроу. Кембридж: Издательство Кембриджского университета. С. 217–234. Дои:10.2277/0521553555. ISBN  978-0-521-08288-4.
48. Стрелка и Хан (1980) С. 169–182). Старр (1969, стр. 27–33).
49. Грин и Хеллер (1981, п. 44)
50. Гезнери (1989, стр.99)
51. Мас-Колелл (1987)
52. Вариан (1992, стр. 393–394): Вариан, Хэл Р. (1992). «21.2 Выпуклость и размер». Микроэкономический анализ (3-е изд.). W. W. Norton & Company. ISBN  978-0-393-95735-8. МИСТЕР  1036734.

    Мас-Колелл, Whinston & Green (1995), стр. 627–630): Мас-Колелл, Андреу; Whinston, Michael D .; Грин, Джерри Р. (1995). «17.1 Большие экономики и невыпуклости». Микроэкономическая теория. Издательство Оксфордского университета. ISBN  978-0-19-507340-9.

53. Стрелка и Хан (1980), стр. 169–182).

    Мас-Колелл (1985, стр. 52–55, 145–146, 152–153 и 274–275): Мас-Колелл, Андреу (1985). «1.L Средние наборы». Теория общего экономического равновесия: A дифференцируемый подход. Монографии Эконометрического общества. 9. Издательство Кембриджского университета. ISBN  0-521-26514-2. МИСТЕР  1113262.

    Хильденбранд (1974 г., стр. 37, 115–116, 122 и 168): Хильденбранд, Вернер (1974). Ядро и равновесие большой экономики. Принстонские исследования в области математической экономики. 5. Принстон, Нью-Джерси: Издательство Принстонского университета. С. viii + 251. ISBN  978-0-691-04189-6. МИСТЕР  0389160.

54. Старр (1997, п. 169): Старр, Росс М. (1997). "8 Выпуклые множества, теоремы отделимости и невыпуклые множества вр^N (новые главы 22 и 25–26 во втором издании (2011)) ». Теория общего равновесия: введение (Первое изд.). Кембридж: Издательство Кембриджского университета. С. xxiii + 250. ISBN  0-521-56473-5. МИСТЕР  1462618.

    Элликсон (1994, pp. xviii, 306–310, 312, 328–329, 347 и 352): Элликсон, Брайан (1994). Конкурентное равновесие: теория и приложения. Издательство Кембриджского университета. Дои:10.2277/0521319889. ISBN  978-0-521-31988-1.

55. Лаффон, Жан-Жак (1988). «3. Невыпуклости». Основы государственной экономики. Массачусетский технологический институт Нажмите. С. 63–65. ISBN  0-262-12127-1.
56. Салани (2000 г., pp. 112–113 и 107–115): Салани, Бернар (2000). «7 невыпуклостей». Микроэкономика сбоев рынка (Английский перевод (1998) французского Микроэкономика: Les défaillances du marché (Экономика, Париж) изд.). Кембридж, Массачусетс: MIT Press. С. 107–125. ISBN  0-262-19443-0.
57. Итииси (1983), стр. 24–25): Итииси, Тацуро (1983). Теория игр для экономического анализа. Экономическая теория, эконометрика и математическая экономика. Нью-Йорк: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. с. х + 164. ISBN  0-12-370180-5. МИСТЕР  0700688.
58. Кассель (1981), стр. 127 и 33–34): Касселс, Дж. У. С. (1981). «Приложение А Выпуклые множества». Экономика для математиков. Серия лекций Лондонского математического общества. 62. Кембридж, Нью-Йорк: Издательство Кембриджского университета. С. xi + 145. ISBN  0-521-28614-X. МИСТЕР  0657578.
59. Обен (2007), стр. 458–476): Обен, Жан-Пьер (2007). «14.2 Двойственность в случае невыпуклого интегрального критерия и ограничений (особенно 14.2.3 Теорема Шепли – Фолкмана, страницы 463–465)». Математические методы игры и экономическая теория (Перепечатка с новым предисловием от редакции Северной Голландии 1982 г. на английском языке). Минеола, Нью-Йорк: Dover Publications, Inc., стр. Xxxii + 616. ISBN  978-0-486-46265-3. МИСТЕР  2449499.
60. Картер (2001), стр. 93–94, 143, 318–319, 375–377 и 416)
61. Трокель (1984, п. 30): Трокель, Вальтер (1984). Рыночный спрос: анализ крупных экономик с невыпуклыми предпочтениями. Конспект лекций по экономике и математическим системам. 223. Берлин: Springer-Verlag. С. viii + 205. ISBN  3-540-12881-6. МИСТЕР  0737006.
62. Бертсекас (1999 г., п. 496): Бертсекас, Дмитрий П. (1999). «5.1.6 Разделимые задачи и их геометрия». Нелинейное программирование (Второе изд.). Кембридж, Массачусетс: Athena Scientific. С. 494–498. ISBN  1-886529-00-0.
63. Рокафеллар (1997), п. 23)
64. В предел последовательности является членом закрытие оригинального набора, который является самым маленьким закрытый набор который содержит исходный набор. Сумма двух Минковского закрытые наборы не нужно закрывать, поэтому следующие включение может быть строгим

    Clos (P) + Clos (Q) ⊆ Clos (Clos (P) + Clos (Q));

    включение может быть строгим даже для двух выпуклый замкнутые слагаемые, согласно Рокафеллар (1997), с. 49 и 75). Чтобы гарантировать, что сумма множеств Минковского замкнута, требуется операция замыкания, которая добавляет пределы сходящихся последовательностей.
65. Лемарешаль (1973, п. 38): Лемарешаль, Клод (Апрель 1973 г.). Использование двойственности для невыпуклых проблем [Использование двойственности для невыпуклых проблем] (Отчет) (на французском языке). Domaine de Voluceau, Rocquencourt, 78150 Le Chesnay, Франция: IRIA (теперь INRIA), Laboratoire de recherche en informatique et automatique. п. 41.. Эксперименты Лемарешала обсуждались в более поздних публикациях:

    Аардал (1995), стр. 2–3): Аардал, Карен (Март 1995 г.). "Оптима интервью Клода Лемарешала " (PDF). Optima: Информационный бюллетень Общества математического программирования. 45: 2–4. Получено 2 февраля 2011.

    Хириарт-Уррути и Лемарешаль (1993, стр. 143–145, 151, 153, 156): Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). «XII Абстрактная двойственность для практиков». Алгоритмы выпуклого анализа и минимизации, ОбъемII: Продвинутая теория и методы связки. Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 306. Берлин: Springer-Verlag. С. 136–193 (и библиографические комментарии к стр. 334–335). ISBN  3-540-56852-2. МИСТЕР  1295240.

66. Экеланд, Ивар (1974). "Единая оценка априори en программирование невыпуклое ". Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Séries A et B (на французском языке). 279: 149–151. ISSN  0151-0509. МИСТЕР  0395844.
67. Обен и Экланд (1976), стр. 226, 233, 235, 238 и 241): Aubin, J.P .; Экланд, И. (1976). «Оценки разрыва двойственности в невыпуклой оптимизации». Математика исследования операций. 1 (3): 225–245. Дои:10.1287 / moor.1.3.225. JSTOR  3689565. МИСТЕР  0449695.

    Обен и Экланд (1976) и Экланд (1999), pp. 362–364) также рассматривали выпуклый  закрытие задачи невыпуклой минимизации, т. е. задачи, определяемой как закрыто  выпуклый корпус из эпиграф исходной проблемы. Их исследование разрывов дуальности было расширено Ди Гульельмо на квазивыпуклый закрытие невыпуклого минимизация проблема - то есть проблема, определяемая как закрыто  выпуклый корпус из ниже наборы уровней:

    Ди Гульельмо (1977), стр. 287–288): Ди Гульельмо, Ф. (1977). «Невыпуклая двойственность в многокритериальной оптимизации». Математика исследования операций. 2 (3): 285–291. Дои:10.1287 / moor.2.3.285. JSTOR  3689518. МИСТЕР  0484418.

68. Шнайдер и Вайль (2008 г., п. 45): Шнайдер, Рольф; Вайль, Вольфганг (2008). Стохастическая и интегральная геометрия. Вероятность и ее приложения. Springer. Дои:10.1007/978-3-540-78859-1. ISBN  978-3-540-78858-4. МИСТЕР  2455326.
69. Кассель (1975), стр. 433–434): Касселс, Дж. У. С. (1975). «Меры невыпуклости множеств и теорема Шепли – Фолкмана – Старра». Математические труды Кембриджского философского общества. 78 (3): 433–436. Дои:10.1017 / S0305004100051884. МИСТЕР  0385711.
70. Молчанов (2005 г., pp. 195–198, 218, 232, 237–238 и 407): Молчанов, Илья (2005). «3 сложения Минковского». Теория случайных множеств. Вероятность и ее приложения. Лондон: Springer-Verlag London Ltd., стр.194 –240. Дои:10.1007/1-84628-150-4. ISBN  978-1-84996-949-9. МИСТЕР  2132405.
71. Пури и Ралеску (1985), стр. 154–155): Puri, Madan L .; Ралеску, Дэн А. (1985). «Предельные теоремы для случайных компактов в банаховом пространстве». Математические труды Кембриджского философского общества. 97 (1): 151–158. Bibcode:1985MPCPS..97..151P. Дои:10.1017 / S0305004100062691. МИСТЕР  0764504.
72. Вейль (1982, pp. 203 и 205–206): Вайль, Вольфганг (1982). «Применение центральной предельной теоремы для случайных величин со значениями в банаховом пространстве к теории случайных множеств». Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete [Теория вероятностей и смежные области]. 60 (2): 203–208. Дои:10.1007 / BF00531823. МИСТЕР  0663901.
73. Серф (1999), стр. 243–244): Серф, Рафаэль (1999). «Большие уклонения для сумм i.i.d. случайных компактов». Труды Американского математического общества. 127 (8): 2431–2436. Дои:10.1090 / S0002-9939-99-04788-7. МИСТЕР  1487361. Серф использует приложения леммы Шепли – Фолкмана из Пури и Ралеску (1985) С. 154–155).
74. Ружа (1997 г., п. 345): Ружа, Имре З. (1997). «Неравенство Брунна – Минковского и невыпуклые множества». Geometriae Dedicata. 67 (3): 337–348. Дои:10.1023 / А: 1004958110076. МИСТЕР  1475877.
75. Тарделла (1990, стр. 478–479): Тарделла, Фабио (1990). «Новое доказательство теоремы Ляпунова о выпуклости». SIAM Journal по управлению и оптимизации. 28 (2): 478–481. Дои:10.1137/0328026. МИСТЕР  1040471.
76. Винд (1964, с. 168 и 175): Винд, Карл (май 1964). «Распределение Эджворта в экономике обмена с большим количеством трейдеров». Международное экономическое обозрение. 5 (2): 165–77. Дои:10.2307/2525560. JSTOR  2525560. Статью Винда отметила победитель конкурса 1983 г. Нобелевская премия по экономике, Жерар Дебре. Дебре (1991), п. 4) написал:

    Концепция выпуклого множества (т. Е. Множества, содержащего отрезок, соединяющий любые две его точки) неоднократно ставилась в центр экономической теории до 1964 года. Она появилась в новом свете с введением теории интеграции в исследование экономическая конкуренция: если связать с каждым агентом экономики произвольный набор в товарном пространстве и если усреднить эти индивидуальные наборы над набором незначительных агентов, то полученное множество обязательно выпукло. [Дебре добавляет эту сноску: «Об этом прямом следствии теоремы А.А. Ляпунова см. Винд (1964). "] Но объяснения ... функций цен ... можно сделать так, чтобы выпуклость множеств, полученных в результате этого процесса усреднения. Выпуклость в товарном пространстве полученные путем агрегирования над набором незначительных агентов - это понимание, которое экономическая теория обязана ... теории интеграции. [Курсив добавлен]

    Дебре, Жерар (Март 1991 г.). «Математизация экономической теории». Американский экономический обзор. 81 (Обращение президента к 103-му заседанию Американской экономической ассоциации, 29 декабря 1990 г., Вашингтон, округ Колумбия): 1–7. JSTOR  2006785.

77. Арштейн (1980), стр. 172–183). Артштейн (1980) был переиздан в фестивальный сбор за Роберт Дж. Ауманн, победитель 2008 г. Нобелевская премия по экономике: Арстейн, Цви (1995). «22 дискретных и непрерывных взрыва и пробелов на лице или: ищите крайние точки». В Харте, Серджиу; Нейман, Авраам (ред.). Игра и экономическая теория: избранные статьи в честь Роберта Дж. Ауманна. Анн-Арбор, Мичиган: Издательство Мичиганского университета. С. 449–462. ISBN  0-472-10673-2. Архивировано из оригинал 24 мая 2011 г.
78. Мас-Колелл (1978, п. 210): Мас-Колелл, Андреу (1978). «Примечание к основной теореме эквивалентности: сколько всего блокирующих коалиций?». Журнал математической экономики. 5 (3): 207–215. Дои:10.1016/0304-4068(78)90010-1. МИСТЕР  0514468.

Рекомендации

• Эрроу, Кеннет Дж.; Хан, Фрэнк Х. (1980) [1971]. Общий конкурентный анализ. Учебники по экономике. 12 (перепечатка Сан-Франциско, Калифорния: Holden-Day, Inc. Mathematical Economics Texts6 ред.). Амстердам: Северная Голландия. ISBN  0-444-85497-5. МИСТЕР  0439057.
• Арштейн, Цви (1980). «Дискретные и непрерывные трещины и лицевые пространства, или: ищите крайние точки». SIAM Обзор. 22 (2): 172–185. Дои:10.1137/1022026. JSTOR  2029960. МИСТЕР  0564562.
• Картер, Майкл (2001). Основы математической экономики. Кембридж, Массачусетс: MIT Press. С. xx + 649. ISBN  0-262-53192-5. МИСТЕР  1865841. (Сайт автора с ответы на упражнения ). Архивировано из оригинал 15 сентября 2006 г.
• Диверт, У. Э. (1982). «12 двойственных подходов к микроэкономической теории». В Стрелка, Кеннет Джозеф; Intriligator, Майкл Д. (ред.). Справочник по математической экономике, ТомII. Справочники по экономике. 1. Амстердам: North-Holland Publishing Co., стр. 535–599. Дои:10.1016 / S1573-4382 (82) 02007-4. ISBN  978-0-444-86127-6. МИСТЕР  0648778.
• Экеланд, Ивар (1999) [1976]. "Приложение I: априори оценка в выпуклом программировании ». В Экланде, Ивар; Темам, Роджер (ред.). Выпуклый анализ и вариационные задачи. Классика прикладной математики. 28 (Исправленное переиздание изд. Северной Голландии). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM). С. 357–373. ISBN  0-89871-450-8. МИСТЕР  1727362.
• Грин, Джерри; Хеллер, Уолтер П. (1981). «1 Математический анализ и выпуклость с приложениями к экономике». В Стрелка, Кеннет Джозеф; Intriligator, Майкл Д. (ред.). Справочник по математической экономике, Томя. Справочники по экономике. 1. Амстердам: издательство North-Holland Publishing Co., стр. 15–52. Дои:10.1016 / S1573-4382 (81) 01005-9. ISBN  0-444-86126-2. МИСТЕР  0634800.
• Геснери, Роджер (1989). «Первое наилучшее распределение ресурсов с невыпуклостями в производстве». В Корнете, Бернар; Тюлькенс, Генри (ред.). Вклад в исследования операций и экономику: двадцатая годовщина CORE (доклады симпозиума, состоявшегося в Лувен-ла-Нев, январь 1987 г.). Кембридж, Массачусетс: MIT Press. С. 99–143. ISBN  0-262-03149-3. МИСТЕР  1104662.
• Мас-Колелл, А. (1987). «Невыпуклость». В Eatwell, Джон; Милгейт, Мюррей; Ньюман, Питер (ред.). Новый Пэлгрейв: экономический словарь (первое изд.). Пэлгрейв Макмиллан. С. 653–661. Дои:10.1057/9780230226203.3173. ISBN  9780333786765. (PDF-файл на домашней странице Mas-Colell ).
• Рокафеллар, Р. Тиррелл (1997). Выпуклый анализ. Достопримечательности Принстона в математике. Принстон, Нью-Джерси: Издательство Принстонского университета. С. xviii + 451. ISBN  0-691-01586-4. МИСТЕР  1451876.. Перепечатка 1970 г. (МИСТЕР274683 ) Принстонская математическая серия28
• Шнайдер, Рольф (1993). Выпуклые тела: теория Брунна – Минковского.. Энциклопедия математики и ее приложений. 44. Кембридж: Издательство Кембриджского университета. С. xiv + 490. ISBN  0-521-35220-7. МИСТЕР  1216521.
• Старр, Росс М. (1969). «Квазиравновесия на рынках с невыпуклыми предпочтениями (Приложение 2: Теорема Шепли – Фолкмана, стр. 35–37)». Econometrica. 37 (1): 25–38. Дои:10.2307/1909201. JSTOR  1909201.
• Старр, Росс М. (2008). "Теорема Шепли – Фолкмана". В Дурлауф, Стивен Н.; Блюм, Лоуренс Э (ред.). Новый экономический словарь Palgrave (Второе изд.). Пэлгрейв Макмиллан. С. 317–318 (1-е изд.). Дои:10.1057/9780230226203.1518. ISBN  978-0-333-78676-5.

внешняя ссылка

• Андерсон, Роберт М. (март 2005 г.). "1 Теорема Шепли – Фолкмана" (PDF). Экономика 201B: невыпуклые предпочтения и приблизительные равновесия. Беркли, Калифорния: экономический факультет Калифорнийского университета в Беркли. стр. 1–5. Получено 15 января 2011.
• Хау, Роджер (Ноябрь 1979 г.). О тенденции к выпуклости векторной суммы множеств (PDF) (Отчет). Документы для обсуждения Фонда Коулза. 538. Box 2125 Yales Station, Нью-Хейвен, CT 06520: Фонд Коулза для исследований в области экономики, Йельский университет. Получено 15 января 2011.
• Старр, Росс М. (Сентябрь 2009 г.). "8 Выпуклые множества, теоремы отделимости и невыпуклые множества вр^N (Раздел 8.2.3 Измерение невыпуклости, теорема Шепли – Фолкмана) " (PDF). Теория общего равновесия: введение. С. 3–6. Дои:10.1017 / CBO9781139174749. ISBN  9781139174749. МИСТЕР  1462618. (Черновик второго издания, из курса Старра на экономическом факультете Калифорнийского университета в Сан-Диего).
• Старр, Росс М. (Май 2007 г.). "Теорема Шепли – Фолкмана" (PDF). С. 1–3. (Проект статьи второго издания Новый экономический словарь Пэлгрейва). Получено 15 января 2011.