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

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

Шепли -Фолкмана Лемма — результат выпуклой геометрии , который описывает в Минковского сложение множеств векторном пространстве . Он назван в честь математиков Ллойда Шепли и Джона Фолкмана , но впервые был опубликован экономистом Россом М. Старром .

Лемму можно интуитивно понять так: если число суммируемых множеств превышает размерность векторного пространства, то их сумма Минковского приблизительно выпукла.

Связанные результаты дают более точные заявления о том, насколько близко приближение. Например, Шепли-Фолкмана теорема дает верхнюю границу расстояния между любой точкой суммы Минковского и ее выпуклой оболочкой . Эта верхняя оценка уточняется теоремой Шепли-Фолкмана-Старра (альтернативно, Старра следствием ).

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

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

Множество является выпуклым , если каждый отрезок, соединяющий две его точки, является подмножеством этого множества: например, сплошной диск  $\bullet$ это выпуклое множество, но круг  $\circ$ нет, потому что отрезок, соединяющий две разные точки $\oslash$ не является подмножеством круга.

Выпуклая оболочка множества Q — это наименьшее выпуклое множество, Q. содержащее Это расстояние равно нулю тогда и только тогда, когда сумма выпукла.

Сложение Минковского – это сложение членов множества . Например, добавление набора, состоящего из целых чисел ноль и единица, к самому себе дает набор, состоящий из нуля, единицы и двойки: $$\{0,1\}+\{0,1\}=\{0+0,0+1,1+0,1+1\}=\{0,1,2\}.$$

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

Расстояние между выпуклым интервалом [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]. По мере того, как все больше наборов суммируются, среднее их суммы «заполняет» свою выпуклую оболочку: максимальное расстояние между средним значением и его выпуклой оболочкой приближается к нулю, поскольку среднее включает в себя больше слагаемых .

Предварительные сведения

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

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

Действительному , векторному пространству двух измерений можно задать декартову систему координат в которой каждая точка идентифицируется упорядоченной парой действительных чисел, называемых «координатами», которые обычно обозначаются x и y . Две точки в декартовой плоскости можно добавить по координатам.

( Икс ₁ , у ₁ ) + ( Икс ₂ , у ₂ ) знак равно ( Икс ₁ + Икс ₂ , у ₁ + у ₂ );

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

λ ( Икс , y ) знак равно ( λx , λy ).

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

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

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

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

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

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

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

(1 − λ ) v ₀ + λv ₁

является членом Q. ​ ​

По математической индукции множество Q является выпуклым тогда и только тогда, когда каждая комбинация членов Q также принадлежит Q. выпуклая По определению, выпуклая комбинация индексированного подмножества { v ₀ , v ₁ , . . . , v _D } векторного пространства — это любое средневзвешенное значение λ ₀ v ₀ + λ ₁ v ₁ + . . . + λ _D v _D , для некоторого индексированного набора неотрицательных действительных чисел { λ _d }, удовлетворяющего уравнению λ ₀ + λ ₁ + . . . + λ _Д = 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Формулировки трех основных результатов

Обозначения

$D,N\in \{1,2,3,...\}$ являются положительными целыми числами.

$D$ это размерность окружающего пространства $\mathbb {R} ^{D}$.

$Q_{1},...,Q_{N}$ являются непустыми ограниченными подмножествами $\mathbb {R} ^{D}$. Их еще называют «слагаемыми». $N$ это количество слагаемых.

$Q=\sum _{n=1}^{N}Q_{n}$ есть сумма Минковского слагаемых.

$x$ — произвольный вектор в $\mathrm {Conv} (Q)$.

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

С $\mathrm {Conv} (Q)=\sum _{n=1}^{N}\mathrm {Conv} (Q_{n})$, для любого $x\in \mathrm {Conv} (Q)$, существуют элементы $q_{n}\in \mathrm {Conv} (Q_{n})$ такой, что $\sum _{n=1}^{N}q_{n}=x$. Лемма Шепли –Фолкмана уточняет это утверждение.

Лемма Шепли – Фолкмана . Для любого $x\in \mathrm {Conv} (Q)$, существуют элементы $q_{n}$ такой, что $\sum _{n=1}^{N}q_{n}=x$, и самое большее $D$ слагаемых $q_{n}\in \mathrm {Conv} (Q_{n})\setminus Q_{n}$, в то время как другие $q_{n}\in Q_{n}$.

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

Перетасовка индексов при необходимости, это означает, что каждая точка в $\mathrm {Conv} (Q)$ можно разложить как

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

где $q_{n}\in \mathrm {Conv} (Q_{n})$ для $1\leq n\leq D$ и $q_{n}\in Q_{n}$ для $D+1\leq n\leq N$. Обратите внимание, что переиндексация зависит от точки $x$.

Лемму можно кратко сформулировать так:

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

Обратная лемма Шепли – Фолкмана.

обращение леммы Шепли – Фолкмана - Если векторное пространство подчиняется лемме Шепли – Фолкмана для натурального числа $D$, и ни для какого числа меньше $D$, то его размерность конечна и в точности $D$.

В частности, лемма Шепли – Фолкмана требует, чтобы векторное пространство было конечномерным.

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

Шепли и Фолкман использовали свою лемму, чтобы доказать следующую теорему, которая количественно определяет разницу между $Q$ и $\mathrm {Conv} (Q)$ используя квадрат евклидова расстояния .

Для любого непустого подмножества $S\subseteq \mathbb {R} ^{D}$ и любая точка $x\in \mathbb {R} ^{D},$ определить их квадрат евклидова расстояния как нижнюю границу $$d^{2}(x,S)=\inf _{y\in S}\|x-y\|^{2}.$$ И вообще, для любых двух непустых подмножеств $S,S'\subseteq \mathbb {R} ^{D},$ определять $$d^{2}(S,S')=\inf _{x\in S,y\in S'}\|x-y\|^{2}.$$

Обратите внимание, что $d^{2}(x,S)=(\inf _{y\in S}\|x-y\|)^{2},$ поэтому мы можем просто написать $d^{2}(x,S)=d(x,S)^{2},$ где $d(x,S)=\inf _{y\in S}\|x-y\|.$ Сходным образом, $d^{2}(S,S')=d(S,S')^{2}.$

Например, $d^{2}([0,2],\{0,1,2\})=1/4=d([0,2],\{0,1,2\})^{2}.$

Квадрат евклидова расстояния является мерой того, насколько «близки» два множества. В частности, если два множества компактны, то их квадрат евклидова расстояния равен нулю тогда и только тогда, когда они равны. Таким образом, мы можем количественно оценить, насколько близко к выпуклости $Q$ по верхней границе $d^{2}(\mathrm {Conv} (Q),Q).$

Для любого ограниченного подмножества $S\subset \mathbb {R} ^{D},$ определить его радиус окружности $rad(S)$ быть нижней границей радиуса всех содержащих его шаров (как показано на диаграмме). Более формально, $$rad(S)\equiv \inf _{x\in R^{N}}\sup _{y\in S}\|x-y\|$$ Теперь мы можем констатировать

Теорема Шепли – Фолкмана  —  $d^{2}(Q,\mathrm {Conv} (Q))~\leq ~\sum _{\max D}rad(Q_{n})^{2}.$

где мы используем обозначение $\sum _{\max D}$ означать «сумму $D$ наибольшие условия».

Обратите внимание, что эта верхняя граница зависит от размерности окружающего пространства и формы слагаемых, но не от количества слагаемых.

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

Определить внутренний радиус $r(S)$ ограниченного подмножества $S\subset \mathbb {R} ^{D}$ быть нижней границей $r$ такой, что для любого $x\in \mathrm {Conv} (S)$, существует шар $B$ радиуса $r$ такой, что $x\in \mathrm {Conv} (S\cap B)$.

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

Например, пусть $B'\subset B\subset \mathbb {R} ^{D}$ — два вложенных друг в друга шара, тогда радиус описанной окружности $B\setminus B'$ это радиус $B$, но его внутренний радиус равен радиусу $B'$.

С $r(S)\leq rad(S)$ для любого ограниченного подмножества $S\subset \mathbb {R} ^{D}$, следующая теорема является уточнением:

Теорема Шепли – Фолкмана – Старра  —  $d^{2}(Q,\mathrm {Conv} (Q))\leq \sum _{\max D}r(Q_{n})^{2}$.

В частности, если у нас есть бесконечная последовательность $(Q_{n})_{n=1,2,...}$ непустых ограниченных подмножеств $\mathbb {R} ^{D}$, и если существует какой-либо $r_{0}\geq 0$ так, что внутренний радиус каждого $Q_{n}$ ограничен сверху $r_{0}$, затем $$d^{2}\left(\mathrm {Conv} \left({\frac {1}{N}}\sum _{n=1}^{N}Q_{n}\right),{\frac {1}{N}}\sum _{n=1}^{N}Q_{n}\right)\leq {\frac {Dr_{0}^{2}}{N}}.$$Это можно интерпретировать как утверждение, что, пока у нас есть верхняя граница внутренних радиусов, выполнение «усреднения Минковского» будет приближать нас все ближе и ближе к выпуклому множеству.

Другие доказательства результатов

Было много доказательств этих результатов, начиная с оригинала, до более поздних Стрелы и Хана , Кассельс , Шнайдер, и т. д. Абстрактное и изящное доказательство Экланда. был расширен Artstein. Различные доказательства появились и в неопубликованных работах. Элементарное доказательство леммы Шепли–Фолкмана можно найти в книге Берцекаса : вместе с приложениями для оценки разрыва двойственности в сепарабельных задачах оптимизации и играх с нулевой суммой.

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

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

Следующее доказательство леммы Шепли–Фолкмана взято из. Идея доказательства состоит в том, чтобы поднять представление $x$ от $\mathbb {R} ^{D}$к $\mathbb {R} ^{D+N}$, используйте теорему Каратеодори для конических оболочек , а затем вернитесь к $\mathbb {R} ^{D}$.

Доказательство леммы Шепли – Фолкмана.

Для каждого $n$, представлять $q_{n}\in \mathrm {Conv} (Q_{n})$ как $q_{n}=\sum _{k=1}^{K}w_{n,k}q_{n,k}$, где $K$ большое конечное число, $w_{n,k}\geq 0$, и $\sum _{k}w_{n,k}=1$.

Теперь «поднимите» представление $x=\sum _{n}\sum _{k}w_{n,k}q_{n,k}$ от $\mathbb {R} ^{D}$ к $\mathbb {R} ^{D+N}$. Определять $${\bar {x}}=(x,1,...,1);\quad {\bar {q}}_{n,k}=(q_{n,k},e_{n})$$ где $e_{n}$ вектор в $\mathbb {R} ^{N}$ у которого есть 1 в координате $n$, и 0 во всех остальных координатах.

Таким образом, мы имеем поднятое представление

$${\bar {x}}=\sum _{n}\sum _{k}w_{n,k}{\bar {q}}_{n,k}.$$ То есть, ${\bar {x}}$ находится в конической оболочке $\{{\bar {q}}_{n,k}\}_{n\in 1:N,k\in 1:K}$.

По теореме Каратеодори для конических оболочек у нас есть альтернативное представление

$${\bar {x}}=\sum _{n}\sum _{k}w'_{n,k}{\bar {q}}_{n,k}$$ такой, что $w'_{n,k}\geq 0$, и самое большее $N+D$ из них ненулевые. Поскольку мы определили

$${\bar {x}}=(x,1,...,1);\quad {\bar {q}}_{n,k}=(q_{n,k},e_{n})$$ это альтернативное представление также является представлением для $x$.

Мы утверждаем, что для любого $n_{0}\in 1:N$, должно быть хотя бы одно значение $k$ для чего $w'_{n_{0},k}$ ненулевое значение. Помните, что мы определили $({\bar {x}})_{D+n_{0}}$, $(D+n_{0})$ запись ${\bar {x}}$, быть $1$. В то же время, из поднятого представления ${\bar {x}}$, $$({\bar {x}})_{D+n_{0}}=\left(\sum _{n}\sum _{k}w'_{n,k}{\bar {q}}_{n,k}\right)_{D+n_{0}}$$ $$=\sum _{n}\sum _{k}w'_{n,k}({\bar {q}}_{n,k})_{D+n_{0}}.$$ Отбросим все слагаемые на правой стороне, для которых $n\neq n_{0}$ поскольку они равны нулю. Остальные члены принимают вид $w'_{n_{0},k}({\bar {q}}_{n_{0},k})_{D+n_{0}}=w'_{n_{0},k}$, поэтому мы находим уравнение $$1=\sum _{k}w'_{n_{0},k}.$$ Отсюда следует, что хотя бы один элемент суммы в правой части не равен нулю.

Учитывая тот факт, что для каждого значения $n$ есть ненулевое значение $w_{n,k}'$, а также то, что существует не более $N+D$ из $w_{n,k}'$ которые ненулевые, мы заключаем, что может быть только не более $D$ элементы $n\in 1:N$ для которого существует как минимум два из $w_{n,k}'$ которые ненулевые.

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

$${\bar {x}}=\sum _{n}\left(\sum _{k}w'_{n,k}{\bar {q}}_{n,k}\right)$$ где максимум $D$ из $n$, термин $\sum _{k}w'_{n,k}{\bar {q}}_{n,k}$ не в $Q_{n}$.

Следующее «вероятностное» доказательство теоремы Шепли – Фолкмана – Старра взято из.

Мы можем интерпретировать $\mathrm {Conv} (S)$ в вероятностном выражении: $\forall x\in \mathrm {Conv} (S)$, с $x=\sum w_{n}q_{n}$ для некоторых $q_{n}\in S$, мы можем определить случайный вектор $X$, конечно поддерживаемый в $S$, такой, что $Pr(X=q_{n})=w_{n}$, и $x=\mathbb {E} [X]$.

Тогда естественно рассмотреть «дисперсию» множества $S$ как $$Var(S):=\sup _{x\in \mathrm {Conv} (S)}\inf _{\mathbb {E} [X]=x,X{\text{ is finitely supported in }}S}Var[X]$$При этом, $d(S,\mathrm {Conv} (S))^{2}\leq Var(S)\leq r(S)\leq rad(S)$.

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

$d(S,\mathrm {Conv} (S))^{2}\leq Var(S)$: Раскройте их определения.

$Var(S)\leq rad(S)$: если $x\in \mathrm {Conv} (S)$ тогда пусть $X$ иметь конечную поддержку в $S$ такой, что $E[X]=x$. Теперь, поскольку $S$ ограничен в шаре радиуса $rad(S)+\epsilon$ сосредоточено на каком-то $o$, у нас есть $Var[X]=Var[X-o]\leq E[\|X-o\|^{2}]\leq rad(S)+\epsilon$.

$Var(S)\leq r(S)$: использовать предыдущий результат.

Доказательство теоремы Шепли–Фолкмана–Старра.

Достаточно показать $Var\left(Q\right)\leq \sum _{\max D}Var(Q_{n})$.

$\forall x\in \mathrm {Conv} (Q)$, по лемме Шепли–Фолкмана существует представление $x=\sum _{n\in I}x_{n}+\sum _{n\in J}q_{n}$, такой, что $I,J$ перегородки $\{1,2,...,N\},|I|\leq D,x_{n}\in \mathrm {Conv} (Q_{n}),q_{n}\in Q_{n}$.

Теперь для каждого $n\in I$, построить случайные векторы $X_{n}$ такой, что $X_{n}$ конечно поддерживается на $Q_{n}$, с $\mathbb {E} [X_{n}]=x_{n}$ и $Var[X_{n}]<Var[Q_{n}]+\epsilon$, где $\epsilon >0$ — произвольное малое число.

Пусть все такие $X_{n}$ быть независимым. Тогда пусть $X=\sum _{n\in I}X_{n}+\sum _{n\in J}q_{n}$. Поскольку каждый $q_{n}$ — детерминированный вектор, мы имеем

$$Var[X]=Var\left[\sum _{n\in I}X_{n}\right]=\sum _{n\in I}Var\left[X_{n}\right]\leq \sum _{n\in I}\left(Var(Q_{n})+\epsilon \right)\leq \sum _{\max D}Var(Q_{n})+D\epsilon .$$

Поскольку это верно для произвольного $\epsilon >0$, у нас есть $Var[X]\leq \sum _{\max D}Var(Q_{n})$, и мы закончили.

История

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

Лемма Ллойда Шепли и Джона Фолкмана была впервые опубликована экономистом Россом М. Старром , который исследовал существование экономического равновесия во время учебы у Кеннета Эрроу . В своей статье Старр исследовал выпуклую экономику, в которой невыпуклые множества были заменены их выпуклыми оболочками; Старр доказал, что овыпуклая экономика имеет состояния равновесия, близко приближенные к «квазиравновесиям» исходной экономики; более того, он доказал, что каждое квазиравновесие обладает многими оптимальными свойствами истинного равновесия, существование которых доказано для выпуклых экономик.

После статьи Старра 1969 года результаты Шепли-Фолкмана-Старра широко использовались, чтобы показать, что центральные результаты (выпуклой) экономической теории являются хорошим приближением к крупным экономикам с невыпуклостью; например, квазиравновесия близко аппроксимируют равновесие овыпуклой экономики. «Вывод этих результатов в общей форме был одним из крупнейших достижений послевоенной экономической теории», — писал Роже Геснери .

Тему невыпуклых множеств в экономике изучали многие нобелевские лауреаты : сам Шепли (2012), Эрроу (1972), Роберт Ауманн (2005), Жерар Дебре (1983), Тьяллинг Купманс (1975), Пол Кругман (2008). ) и Пол Самуэльсон (1970); дополнительная тема выпуклых множеств в экономике была подчеркнута этими лауреатами вместе с Леонидом Гурвичем , Леонидом Канторовичем (1975) и Робертом Солоу (1987).

Приложения

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

Экономика

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

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

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

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

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

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

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

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

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

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

Трудности изучения невыпуклых предпочтений подчеркнул Герман Вольд. и снова Пола Самуэльсона , написавшего, что невыпуклости «окутаны вечной тьмой…», по словам Диверта.

Тем не менее, невыпуклые предпочтения были освещены с 1959 по 1961 год в ряде статей в «Журнале политической экономии» ( JPE ). Основными участниками были Фаррелл, Батор, Купманс , и Ротенберг. В частности, в статье Ротенберга обсуждалась приближенная выпуклость сумм невыпуклых множеств. Эти статьи JPE стимулировали появление статьи Ллойда Шепли и Мартина Шубика , в которых рассматривались овыпуклые потребительские предпочтения и вводилась концепция «приблизительного равновесия». Статьи JPE и статья Шепли-Шубика повлияли на другое понятие «квазиравновесия», предложенное Робертом Ауманном .

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

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

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

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

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

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

«В совокупности несоответствие между распределением в фиктивной экономике, порожденным [взятием выпуклых оболочек всех наборов потребления и производства] и некоторым распределением в реальной экономике, ограничено способом, который не зависит от количества экономических Следовательно, средний агент испытывает отклонение от намеченных действий, значение которого исчезает по мере того, как число агентов стремится к бесконечности».

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

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

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

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

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

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

• График представляет собой функции f набор пар аргументов   x и оценок функции f ( x )

График( ж ) знак равно { ( Икс , ж ( Икс ) ) }

• Надграфиком функции действительной .   f называется множество точек над графиком

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

Эпи( ж ) знак равно { ( Икс , ты ) : ж ( Икс ) ≤ ты   } .

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

Например, квадратичная функция   f ( x ) = x ² является выпуклой, как и абсолютного значения функция g ( x ) = | х |. Однако синусоидальная функция (на фото) невыпуклая на интервале (0, π).

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

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

ж ( Икс ) знак равно ж ( ( Икс ₁ , ..., Икс _$N$) ) знак равно Σ   ж _п ( Икс _п ).

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

х _мин = ( х ₁ , ..., х _$N$) _мин

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

( Икс _j , ж ( Икс _j ) ) ∈ Σ Conv ( График ( ж _п ) ) .

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

Этот анализ был опубликован Иваром Экеландом в 1974 году, чтобы объяснить кажущуюся выпуклость разделимых задач со многими слагаемыми, несмотря на невыпуклость проблем с слагаемыми. В 1973 году молодой математик Клод Лемарешаль был удивлен своим успехом в использовании выпуклой минимизации методов в задачах, которые, как было известно, были невыпуклыми; для минимизации нелинейных задач решение двойственной проблемы не обязательно должно предоставлять полезную информацию для решения основной проблемы, если только основная проблема не является выпуклой и не удовлетворяет ограничению . Проблема Лемарешаля была аддитивно разделимой, и каждая слагаемая функция была невыпуклой; тем не менее, решение двойственной проблемы обеспечило близкое приближение к оптимальному значению основной задачи. Анализ Экланда объяснил успех методов выпуклой минимизации в больших и разделимых задачах, несмотря на невыпуклость функций слагаемых. Экланд и более поздние авторы утверждали, что аддитивная разделимость создает приблизительно выпуклую совокупную проблему, даже несмотря на то, что слагаемые функции были невыпуклыми. Важным шагом в этих публикациях является использование леммы Шепли–Фолкмана. Лемма Шепли – Фолкмана побудила использовать методы выпуклой минимизации в других приложениях с суммами многих функций.

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

Выпуклые множества часто изучаются с помощью теории вероятностей . Каждая точка выпуклой оболочки ( непустого ) подмножества Q конечномерного пространства является значением простого ожидаемым случайного вектора , который принимает свои значения в Q , как следствие леммы Каратеодори . Таким образом, для непустого множества Q совокупность ожидаемых значений простых случайных векторов со значениями Q равна ; Q выпуклой оболочке из этого равенства следует, что результаты Шепли – Фолкмана – Старра полезны в теории вероятностей. С другой стороны, теория вероятностей предоставляет инструменты для изучения выпуклых множеств в целом и результатов Шепли-Фолкмана-Старра в частности. Результаты Шепли-Фолкмана-Старра широко используются в вероятностной теории случайных множеств . например, доказать закон больших чисел , центральная предельная теорема , и больших отклонений   принцип . В этих доказательствах вероятностных предельных теорем использовались результаты Шепли – Фолкмана – Старра, чтобы избежать предположения, что все случайные множества выпуклы.

Вероятностная мера является конечной мерой , и лемма Шепли-Фолкмана имеет приложения в невероятностной теории меры, такой как теории объема и векторных мер . Лемма Шепли-Фолкмана позволяет уточнить неравенство Брунна-Минковского , которое ограничивает объем сумм через объемы их наборов слагаемых. Объем множества определяется через меру Лебега , которая определена на подмножествах евклидова пространства . В продвинутой теории меры лемма Шепли-Фолкмана использовалась для доказательства теоремы Ляпунова , которая утверждает, что область значений векторной меры выпукла. Здесь традиционный термин « диапазон » (альтернативно «изображение») — это набор значений, создаваемых функцией. Векторная мера — это векторное обобщение меры; например, если p1 _{измеримом} и p2 _же — вероятностные меры, определенные в одном и том пространстве , тогда функция произведения   p ₁   p ₂ является векторной мерой, где р ₁   р ₂ определяется для каждого события   ω к

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

Теорема Ляпунова использовалась в экономике , в ( «взрывной» ) теории управления и в статистической теории . Теорему Ляпунова назвали непрерывным аналогом леммы Шепли – Фолкмана: которая сама была названа дискретным аналогом теоремы Ляпунова.

Ссылки

• Аардал, Карен (март 1995 г.). « Интервью Optima - Клод Лемарешаль» (PDF) . Optima: Информационный бюллетень Общества математического программирования . 45 : 2–4 . Проверено 2 февраля 2011 г.
• Эрроу, Кеннет Дж .; Хан, Фрэнк Х. (1980) [1971]. Общий конкурентный анализ . Учебники углубленного уровня по экономике. Том. 12 (переиздание Сан-Франциско, Калифорния: Holden-Day, Inc. Тексты по математической экономике, 6 изд.). Амстердам: Северная Голландия. ISBN  0-444-85497-5 . МР   0439057 .
• Арштейн, Цви (1980). «Дискретные и непрерывные челноки и лицевые пространства, или: Ищите крайние точки». Обзор СИАМ . 22 (2): 172–185. дои : 10.1137/1022026 . JSTOR   2029960 . МР   0564562 . Переиздано в праздничном сборнике Роберта Дж. Ауманна , лауреата Нобелевской премии по экономике 2008 года :
  • Арштейн, Цви (1995). «22 Дискретные и непрерывные челноки и лицевые пространства или: Ищите крайние точки» . В Харте, Серджиу; Нейман, Авраам (ред.). Игры и экономическая теория: Избранные статьи в честь Роберта Дж. Ауманна . Анн-Арбор, Мичиган: Издательство Мичиганского университета. стр. 449–462. ISBN  0-472-10673-2 . Архивировано из оригинала 24 мая 2011 года.
• Арштейн, Цви; Витале, Ричард А. (1975). «Усиленный закон больших чисел для случайных компактов» . Анналы вероятности . 3 (5): 879–882. дои : 10.1214/aop/1176996275 . JSTOR   2959130 . МР   0385966 . Збл   0313.60012 . PE   euclid.ss/1176996275 .
• Обен, Жан-Пьер (2007). «14.2 Двойственность в случае невыпуклого интегрального критерия и ограничений (особенно 14.2.3 Теорема Шепли – Фолкмана, страницы 463–465)». Математические методы игр и экономическая теория (Переиздание с новым предисловием, переработанное английское издание Северной Голландии, 1982 г.). Минеола, Нью-Йорк: Dover Publications. ISBN  978-0-486-46265-3 . МР   2449499 .
• Обен, JP; Экеланд, И. (1976). «Оценки разрыва двойственности в невыпуклой оптимизации». Математика исследования операций . 1 (3): 225–245. дои : 10.1287/moor.1.3.225 . JSTOR   3689565 . МР   0449695 .
• Ауманн, Роберт Дж. (январь – апрель 1964 г.). «Рынки с континуумом трейдеров». Эконометрика . 32 (1–2): 39–50. дои : 10.2307/1913732 . JSTOR   1913732 . МР   0172689 .
• Ауманн, Роберт Дж. (август 1965 г.). «Интегралы от многозначных функций» . Журнал математического анализа и приложений . 12 (1): 1–12. дои : 10.1016/0022-247X(65)90049-1 . МР   0185073 .
• Ауманн, Роберт Дж. (январь 1966 г.). «Существование конкурентного равновесия на рынках с континуумом торговцев». Эконометрика . 34 (1): 1–17. дои : 10.2307/1909854 . JSTOR   1909854 . МР   0191623 .
• Батор, Фрэнсис М. (октябрь 1961a). «О выпуклости, эффективности и рынках». Журнал политической экономии . 69 (5): 480–483. дои : 10.1086/258540 . JSTOR   1828537 .
• Батор, Фрэнсис М. (октябрь 1961b). «О выпуклости, эффективности и рынках: ответ». Журнал политической экономии . 69 (5): 489. дои : 10.1086/258542 . JSTOR   1828539 .
• Берцекас, Дмитрий П. (1999). «5.1.6 Сепарабельные задачи и их геометрия». Нелинейное программирование (Второе изд.). Кембридж, Массачусетс: Athena Scientific. стр. 494–498. ISBN  1-886529-00-0 .
• Берцекас, Дмитрий П. (1996). «5.6 Крупномасштабные задачи сепарабельного целочисленного программирования и экспоненциальный метод множителей». Оптимизация с ограничениями и методы множителей Лагранжа . Бельмонт, Массачусетс: Athena Scientific. ISBN  1-886529-04-3 . МР   0690767 . Перепечатка (1982) Academic Press.
• Берцекас, Дмитрий П .; Лауэр, Грегори С.; Сэнделл, Нильс Р. младший; Посберг, Томас А. (январь 1983 г.). «Оптимальное краткосрочное планирование крупных энергосистем» (PDF) . Транзакции IEEE при автоматическом управлении . 28 (1): 1–11. дои : 10.1109/tac.1983.1103136 . Проверено 2 февраля 2011 г. Материалы конференции IEEE по принятию решений и управлению 1981 г., Сан-Диего, Калифорния, декабрь 1981 г., стр. 432–443.
• Борвейн, Дж. М. ; О'Брайен, RC (1978). «Отмена характеризует выпуклость». Nanta Mathematica (Университет Наньян) . 11 : 100–102. ISSN   0077-2739 . МР   0510842 .
• Картер, Майкл (2001). Основы математической экономики . Кембридж, Массачусетс: MIT Press. ISBN  0-262-53192-5 . МР   1865841 . ( Авторский сайт с ответами на упражнения ). Архивировано из оригинала 15 сентября 2006 года.
• Кассельс, JWS (1975). «Меры невыпуклости множеств и теорема Шепли – Фолкмана – Старра». Математические труды Кембриджского философского общества . 78 (3): 433–436. дои : 10.1017/S0305004100051884 . МР   0385711 .
• Кассельс, JWS (1981). «Приложение А. Выпуклые множества». Экономика для математиков . Серия конспектов лекций Лондонского математического общества. Том. 62. Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-28614-Х . МР   0657578 .
• Серф, Рафаэль (1999). «Большие уклонения сумм случайных компактов iid» . Труды Американского математического общества . 127 (8): 2431–2436. дои : 10.1090/S0002-9939-99-04788-7 . МР   1487361 .
• Дебре, Жерар (март 1991 г.). «Математизация экономической теории». Американский экономический обзор . 81 (Обращение президента на 103-м заседании Американской экономической ассоциации, 29 декабря 1990 г., Вашингтон, округ Колумбия): 1–7. JSTOR   2006785 .
• Ди Гульельмо, Ф. (1977). «Невыпуклая двойственность в многокритериальной оптимизации». Математика исследования операций . 2 (3): 285–291. дои : 10.1287/moor.2.3.285 . JSTOR   3689518 . МР   0484418 .
• Диверт, WE (1982). «12 двойственных подходов к микроэкономической теории» . В «Стреле», Кеннет Джозеф ; Интрилигатор, Майкл Д. (ред.). Справочник по математической экономике . Справочники по экономике. Том. 2. Амстердам: Издательство Северной Голландии. стр. 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 .
• Элликсон, Брайан (1994). Конкурентное равновесие: Теория и приложения . Издательство Кембриджского университета. дои : 10.1017/CBO9780511609411 . ISBN  978-0-521-31988-1 .
• Фаррелл, MJ (август 1959 г.). «Предположение выпуклости в теории конкурентных рынков». Журнал политической экономии . 67 (4): 371–391. дои : 10.1086/258197 . JSTOR   1825163 .
• Фаррелл, MJ (октябрь 1961a). «О выпуклости, эффективности и рынках: ответ». Журнал политической экономии . 69 (5): 484–489. дои : 10.1086/258541 . JSTOR   1828538 .
• Фаррелл, MJ (октябрь 1961b). «Предположение выпуклости в теории конкурентных рынков: ответ». Журнал политической экономии . 69 (5): 493. дои : 10.1086/258544 . JSTOR   1828541 .
• Грин, Джерри; Хеллер, Уолтер П. (1981). «1 Математический анализ и выпуклость с приложениями к экономике». В «Стреле», Кеннет Джозеф ; Интрилигатор, Майкл Д. (ред.). Справочник по математической экономике . Справочники по экономике. Том. 1. Амстердам: Издательство Северной Голландии. стр. 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 .
• Хильденбранд, Вернер (1974). Ядро и равновесие большой экономики . Принстон изучает математическую экономику. Том. 5. Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN  978-0-691-04189-6 . МР   0389160 .
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). «XII Абстрактная двойственность для практиков». Алгоритмы выпуклого анализа и минимизации, Том II : Расширенная теория и методы расслоения . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. Том. 306. Берлин: Springer-Verlag. стр. 136–193 (и библиографические комментарии на стр. 334–335). ISBN  3-540-56852-2 . МР   1295240 .
• Хотеллинг, Гарольд (январь 1935 г.). «Функции спроса при ограниченных бюджетах». Эконометрика . 3 (1): 66–78. дои : 10.2307/1907346 . JSTOR   1907346 .
• Хоу, Роджер (ноябрь 1979 г.). О склонности к выпуклости векторной суммы множеств (PDF) (Отчет). Дискуссионные документы Фонда Коулза. Том. 538. Нью-Хейвен, Коннектикут: Фонд экономических исследований Коулза , Йельский университет . Проверено 15 января 2011 г.
• Итииси, Тацуро (1983). Теория игр для экономического анализа . Экономическая теория, эконометрика и математическая экономика. Нью-Йорк: Academic Press [Харкорт Брейс Йованович, Издательство]. ISBN  0-12-370180-5 . МР   0700688 .
• Купманс, Тьяллинг К. (1957). «Распределение ресурсов и система цен». В Купманс, Тьяллинг С. (ред.). Три очерка о состоянии экономической науки . Нью-Йорк: Книжная компания McGraw – Hill. стр. 1–126. ISBN  0-07-035337-9 .
• Купманс, Тьяллинг К. (октябрь 1961 г.). «Предположения о выпуклости, эффективность распределения и конкурентное равновесие». Журнал политической экономии . 69 (5): 478–479. дои : 10.1086/258539 . JSTOR   1828536 .
• Лемарешаль, Клод (апрель 1973 г.). Использование двойственности для невыпуклых задач (Отчет) (на французском языке). Domaine de Voluceau, Рокенкур , Ле Шене , Франция: IRIA (ныне INRIA) , Исследовательская лаборатория компьютерных наук и автоматизации.
• Мас-Колелл, Андреу (1978). «Примечание к основной теореме эквивалентности: сколько существует блокирующих коалиций?». Журнал математической экономики . 5 (3): 207–215. дои : 10.1016/0304-4068(78)90010-1 . МР   0514468 .
• Мас-Колелл, Андреу (1985). «1.L Средние значения наборов». Теория общего экономического равновесия: дифференцируемый подход . Монографии Эконометрического общества. Том. 9. Издательство Кембриджского университета. ISBN  0-521-26514-2 . МР   1113262 .
• Мас-Колелл, А. (1987). «Невыпуклость» . В Итуэлле, Джон ; Милгейт, Мюррей ; Ньюман, Питер (ред.). Новый Пэлгрейв: Экономический словарь (первое изд.). Пэлгрейв Макмиллан. стр. 653–661. дои : 10.1057/9780230226203.3173 . ISBN  9780333786765 . ( PDF-файл на домашней странице Мас-Колелла ).
• Мас-Колелл, Андреу ; Уинстон, Майкл Д.; Грин, Джерри Р. (1995). «17.1 Крупные экономики и невыпуклости». Микроэкономическая теория . Издательство Оксфордского университета. ISBN  978-0-19-507340-9 .
• Молчанов, Илья (2005). «3 сложения Минковского». Теория случайных множеств . Вероятность и ее приложения. Лондон: Спрингер-Верлаг Лондон. стр. 194–240 . дои : 10.1007/1-84628-150-4 . ISBN  978-1-84996-949-9 . МР   2132405 .
• Пури, Мадан Л.; Ралеску, Дэн А. (1985). «Предельные теоремы для случайных компактов в банаховом пространстве». Математические труды Кембриджского философского общества . 97 (1): 151–158. Бибкод : 1985MPCPS..97..151P . дои : 10.1017/S0305004100062691 . МР   0764504 .
• Рокафеллар, Р. Тиррелл (1997). Выпуклый анализ . Принстонские ориентиры в математике. Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN  0-691-01586-4 . МР   1451876 . . Перепечатка 1970 года ( МР 274683 ) Принстонская математическая серия 28
• Ротенберг, Джером (октябрь 1960 г.). «Невыпуклость, агрегация и оптимальность по Парето». Журнал политической экономии . 68 (5): 435–468. дои : 10.1086/258363 . JSTOR   1830308 .
• Ротенберг, Джером (октябрь 1961 г.). «Комментарии по поводу невыпуклости». Журнал политической экономии . 69 (5): 490–492. дои : 10.1086/258543 . JSTOR   1828540 .
• Ружа, Имре З. (1997). «Неравенство Брунна – Минковского и невыпуклые множества» . Геометрии посвященные . 67 (3): 337–348. дои : 10.1023/А:1004958110076 . МР   1475877 .
• Саланье, Бернар (2000). «7 невыпуклостей». Микроэкономика провалов рынка . Кембридж, Массачусетс: MIT Press. стр. 107–125. ISBN  0-262-19443-0 . Английский перевод книги «Французская микроэкономика: провалы рынка » (1998 г.) (Economica, Париж)
• Самуэльсон, Пол А. (ноябрь 1950 г.). «Проблема интегрируемости в теории полезности». Экономика . Новая серия. 17 (68): 355–385. дои : 10.2307/2549499 . JSTOR   2549499 . МР   0043436 .
• Шнайдер, Рольф (1993). Выпуклые тела: теория Брунна–Минковского . Энциклопедия математики и ее приложений. Том. 44. Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-35220-7 . МР   1216521 .
• Шнайдер, Рольф; Вайль, Вольфганг (2008). Стохастическая и интегральная геометрия . Вероятность и ее приложения. Спрингер. дои : 10.1007/978-3-540-78859-1 . ISBN  978-3-540-78858-4 . МР   2455326 .
• Шепли, Л.С .; Шубик, М. (октябрь 1966 г.). «Квазиядра в монетарной экономике с невыпуклыми предпочтениями» . Эконометрика . 34 (4): 805–827. дои : 10.2307/1910101 . JSTOR   1910101 . Збл   0154.45303 . Архивировано из оригинала 24 сентября 2017 года.
• Старр, Росс М. (1969). «Квазиравновесия на рынках с невыпуклыми предпочтениями (Приложение 2: Теорема Шепли – Фолкмана, стр. 35–37)». Эконометрика . 37 (1): 25–38. дои : 10.2307/1909201 . JSTOR   1909201 .
• Старр, Росс М. (2008). «Теорема Шепли – Фолкмана» . В Дюрлауфе, Стивен Н .; Блюм, Лоуренс Э. (ред.). Новый экономический словарь Пэлгрейва (второе изд.). Пэлгрейв Макмиллан. стр. 317–318 (1-е изд.). дои : 10.1057/9780230226203.1518 . ISBN  978-0-333-78676-5 .
• Старр, Росс М. (1997). «8 Выпуклые множества, теоремы разделения и невыпуклые множества в R ^$N$ (новые главы 22 и 25–26 во втором издании (2011 г.)). Теория общего равновесия: введение (1-е изд.). Кембридж, Великобритания: Cambridge University Press. ISBN  0-521-56473-5 . МР   1462618 .
• Старр, Р.М .; Стинчкомб, MB (1999). «Обмен в сети факторий». В Чичильниски, Грасиела (ред.). Рынки, информация и неопределенность: Очерки экономической теории в честь Кеннета Дж. Эрроу . Кембридж, Великобритания: Издательство Кембриджского университета. стр. 217–234. дои : 10.1017/CBO9780511896583 . ISBN  978-0-521-08288-4 .
• Тарделла, Фабио (1990). «Новое доказательство теоремы Ляпунова о выпуклости». SIAM Journal по контролю и оптимизации . 28 (2): 478–481. дои : 10.1137/0328026 . МР   1040471 .
• Трокель, Уолтер (1984). Рыночный спрос: анализ крупных экономик с невыпуклыми предпочтениями . Конспект лекций по экономике и математическим системам. Том. 223. Берлин: Springer-Verlag. ISBN  3-540-12881-6 . МР   0737006 .
• Вариан, Хэл Р. (1992). «21.2 Выпуклость и размер». Микроэкономический анализ (3-е изд.). WW Нортон и компания. ISBN  978-0-393-95735-8 . МР   1036734 .
• Винд, Карл (май 1964 г.). «Распределения Эджворта в экономике обмена со многими торговцами». Международное экономическое обозрение . 5 (2): 165–177. дои : 10.2307/2525560 . JSTOR   2525560 .
• Вейль, Вольфганг (1982). «Применение центральной предельной теоремы для случайных величин со значениями в банаховом пространстве к теории случайных множеств» . Журнал теории вероятностей и смежных областей . 60 (2): 203–208. дои : 10.1007/BF00531823 . МР   0663901 .
• Вольд, Герман (1943b). «Синтез анализа чистого спроса II ». Skandinavisk Aktuarietidskrift [ Скандинавский актуарный журнал ]. 26 : 220–263. дои : 10.1080/03461238.1943.10404737 . МР   0011939 .
• Вольд, Герман ; Журин, Ларс (совместно с Уолдом) (1953). «8 Некоторые дальнейшие применения полей предпочтений (стр. 129–148)». Анализ спроса: исследование по эконометрике . Публикации Wiley по статистике. Нью-Йорк: Джон Уайли и сыновья. МР   0064385 .

Внешние ссылки

• Андерсон, Роберт М. (март 2005 г.). «1 Теорема Шепли – Фолкмана» (PDF) . Экономика 201B: Невыпуклые предпочтения и приблизительное равновесие . Беркли, Калифорния: Экономический факультет Калифорнийского университета, Беркли. стр. 1–5 . Проверено 15 января 2011 г.
• Старр, Росс М. (сентябрь 2009 г.). «8 Выпуклые множества, теоремы разделения и невыпуклые множества в R ^$N$ (Раздел 8.2.3 Измерение невыпуклости, теорема Шепли – Фолкмана)» (PDF) . Теория общего равновесия: Введение . Стр. 3–6. doi : 10.1017/CBO9781139174749 . ISBN  9781139174749 . МР   1462618 . (Черновик второго издания из курса Старра на экономическом факультете Калифорнийского университета в Сан-Диего). Архивировано из оригинала (PDF) 1 июля 2010 года . Проверено 15 января 2011 г.
• Старр, Росс М. (май 2007 г.). «Теорема Шепли – Фолкмана» (PDF) . стр. 1–3. (Черновик статьи для второго издания New Palgrave Dictionary of Economics ) . Проверено 15 января 2011 г.