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

Суммы множеств векторов почти выпуклы

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

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

Интуитивно лемму можно понимать так: если число суммируемых множеств превышает размерность векторного пространства, то их сумма Минковского приблизительно выпукла. ^{[1] [2]}

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

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

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

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

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

Сложение Минковского — это сложение членов множества . Например, сложение множества, состоящего из целых чисел ноль и единица, с самим собой дает множество, состоящее из нуля, единицы и двойки: $${\displaystyle \{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]. ^[7]

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

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

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

Действительные векторные пространства

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

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

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

λ  ( х ,  у ) = ( λx , λy ).

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

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

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

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

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

(1 −  λ )  v ₀ + λv ₁

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

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

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

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

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

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

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

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

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

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

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

${\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})}$

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

Заявления о трех основных результатах

Обозначение

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

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

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

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

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

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

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

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

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

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

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

где для и для . Обратите внимание, что переиндексация зависит от точки . ^[16] ${\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}$ ${\displaystyle x}$

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

${\displaystyle \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).}$

Обращение леммы Шепли–Фолкмана

Обращение леммы Шепли–Фолкмана ^[17]  —  Если векторное пространство подчиняется лемме Шепли–Фолкмана для натурального числа  и для любого числа, меньшего  , то его размерность конечна, и в точности  . ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В частности, если у нас есть бесконечная последовательность непустых ограниченных подмножеств , и если существует такое , что внутренний радиус каждого из них ограничен сверху значением , то Это можно интерпретировать как утверждение, что до тех пор, пока у нас есть верхняя граница внутренних радиусов, выполнение «усреднения по Минковскому» будет приближать нас все ближе и ближе к выпуклому множеству. ${\displaystyle (Q_{n})_{n=1,2,...}}$ ${\displaystyle \mathbb {R} ^{D}}$ ${\displaystyle r_{0}\geq 0}$ ${\displaystyle Q_{n}}$ ${\displaystyle r_{0}}$ $${\displaystyle 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}}.}$$

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

Было много доказательств этих результатов, от оригинального ^[20] до более поздних Эрроу и Хана , ^[22] Касселса , ^[23] Шнайдера, ^[24] и т. д. Абстрактное и элегантное доказательство Экланда ^[25] было расширено Артштейном. ^[26] Различные доказательства также появлялись в неопубликованных работах. ^{[2] [27]} Элементарное доказательство леммы Шепли–Фолкмана можно найти в книге Берцекаса [ ^28] вместе с приложениями для оценки разрыва двойственности в разделимых задачах оптимизации и играх с нулевой суммой.

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

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

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

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

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

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

Благодаря этому у нас есть поднятое представление

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

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

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

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

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

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

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

$${\displaystyle {\bar {x}}=\sum _{n}\left(\sum _{k}w'_{n,k}{\bar {q}}_{n,k}\right)}$$где для большинства , термин не находится в . ${\displaystyle D}$ ${\displaystyle n}$ ${\displaystyle \sum _{k}w'_{n,k}{\bar {q}}_{n,k}}$ ${\displaystyle Q_{n}}$

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

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

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

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

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

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

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

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

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

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

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

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

$${\displaystyle 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 .}$$

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

История

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

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

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

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

Приложения

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

Экономика

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

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

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

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

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

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

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

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

Трудности изучения невыпуклых предпочтений подчеркивались Германом Уолдом ^[36] и Полом Самуэльсоном , который писал, что невыпуклости «окутаны вечной тьмой...» ^{[37] [a]} по мнению Дайверта. ^[38]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• График функции  f — это набор пар аргументов x и оценок функции  f ( x ) 

График( f ) = { ( x ,  f ( x ) ) }

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

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

Epi( f ) = {  ( x ,  u ) :  f ( x ) ≤  u  } .

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

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

Аддитивные задачи оптимизации

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

f ( x ) = f (  ( x ₁ , ..., x )  ) = Σ f _n ( x _n ). _{${\displaystyle N}$} 

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

х _мин  = ( х ₁ , ...,  х ) _{мин ${\displaystyle N}$}

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

( x _j ,  f ( x _j ) )  ∈  Σ Conv ( Graph( f _n ) ) . ^{[4] [б]}

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

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

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

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

Вероятностная мера — это конечная мера , и лемма Шепли–Фолкмана имеет приложения в теории не вероятностных мер, таких как теории объема и векторных мер . Лемма Шепли–Фолкмана позволяет уточнить неравенство Брунна–Минковского , которое ограничивает объем сумм в терминах объемов их множеств слагаемых. ^[73] Объем множества определяется в терминах меры Лебега , которая определена на подмножествах евклидова пространства . В продвинутой теории меры лемма Шепли–Фолкмана использовалась для доказательства теоремы Ляпунова , которая утверждает, что область значений векторной меры является выпуклой. ^[74] Здесь традиционный термин « область значений » (альтернативно, «изображение») — это множество значений, производимых функцией. Векторная мера — это векторнозначное обобщение меры; например, если  p ₁ и  p ₂ являются вероятностными мерами, определенными на одном и том же измеримом пространстве , то функция произведения  p ₁  p ₂ является векторной мерой, где  p ₁  p ₂ определяется для каждого события  ω как

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

Теорема Ляпунова использовалась в экономике , ^{[45] [75] в} теории управления ( «bang-bang» ) и в статистической теории . ^[76] Теорема Ляпунова была названа непрерывным аналогом леммы Шепли–Фолкмана, ^[3] которая сама была названа дискретным аналогом теоремы Ляпунова. ^[77]

Примечания

1. «Вечная тьма» описывает Ад в «Потерянном рае » Джона Мильтона , вогнутость которого сравнивается с Сербонским болотом в Книге II, строки 592–594:

   Пропасть глубокая, как Сербское болото
   между Дамиатой и горой Касий,
   где затонули целые армии.

   Описание вогнутости, данное Мильтоном, служит литературным эпиграфом , предваряющим седьмую главу Эрроу и Хана (1980, стр. 169) «Рынки с невыпуклыми предпочтениями и производством», в которой представлены результаты Старра (1969).
2. Предел последовательности является членом замыкания исходного множества , которое является наименьшим замкнутым множеством , содержащим исходное множество. Сумма Минковского двух замкнутых множеств не обязательно должна быть замкнутой, поэтому следующее включение может быть строгим

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

   включение может быть строгим даже для двух выпуклых замкнутых множеств слагаемых, согласно Рокафеллару (1997, стр. 49 и 75). Обеспечение замкнутости суммы множеств Минковского требует операции замыкания, которая добавляет пределы сходящихся последовательностей.
3. Aubin & Ekeland (1976) и Ekeland (1999, стр. 362–364) также рассмотрели выпуклое  замыкание проблемы невыпуклой минимизации — то есть проблему, определенную как замкнутая выпуклая оболочка надграфика исходной проблемы . Их исследование разрывов двойственности было расширено Ди Гульельмо до квазивыпуклого замыкания проблемы невыпуклой минимизации — то есть проблему, определенную как замкнутая выпуклая оболочка множеств нижнего уровня . ^[66]

1. Старр (1969)
2. Howe (1979, стр. 1)
3. Старр (2008)
4. Экеланд (1999, стр. 357–359): Опубликованное в первом английском издании 1976 года, приложение Экеланда доказывает лемму Шепли–Фолкмана, а также признает эксперименты Лемарешаля на стр. 373.
5. Берцекас (1996, стр. 364–381), признавая Экланда (1999) на странице 374 и Обина и Экланда (1976) на странице 381:

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

   Берцекас и др. (1983)

6. Artstein & Vitale (1975, стр. 881–882)
7. Картер (2001, стр. 94)
8. Эрроу и Хан (1980, стр. 375)
9. Rockafellar (1997, стр. 10)
10. Эрроу и Хан (1980, стр. 376), Рокафеллар (1997, стр. 10–11) и Грин и Хеллер (1981, стр. 37)
11. Эрроу и Хан (1980, стр. 385) и Рокафеллар (1997, стр. 11–12)
12. Шнайдер (1993, стр. xi) и Рокафеллар (1997, стр. 16)
13. Рокафеллар (1997, стр. 17) и Старр (1997, стр. 78)
14. Шнайдер (1993, стр. 2–3)
15. Эрроу и Хан (1980, стр. 387)
16. Старр (1969, стр. 35–36)
17. Шнайдер (1993, стр. 140) приписывает этот результат Борвейну и О'Брайену (1978)
18. Старр (1969, стр. 36)
19. Шнайдер (1993, стр. 129)
20. Starr (1969, стр. 37)
21. Шнайдер (1993, стр. 129–130)
22. Эрроу и Хан (1980, стр. 392–395)
23. Cassels (1975, стр. 435–436)
24. Шнайдер (1993, стр. 128)
25. Экеланд (1999, стр. 357–359)
26. Артштейн (1980, стр. 180)
27. Андерсон, Роберт М. (14 марта 2005 г.). "1 Теорема Шепли–Фолкмана" (PDF) . Экономика 201B: Невыпуклые предпочтения и приближенные равновесия . Беркли, Калифорния: Экономический факультет Калифорнийского университета в Беркли. стр. 1–5 . Получено 1 января 2011 г. .
28. Берцекас, Димитрий П. (2009). Теория выпуклой оптимизации . Белмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-31-1.
29. Старр, Росс М. (1981). «Аппроксимация точек выпуклой оболочки суммы множеств точками суммы: элементарный подход». Журнал экономической теории . 25 (2): 314–317. doi :10.1016/0022-0531(81)90010-7. MR  0640201.
30. Чжоу, Линь (июнь 1993 г.). «Простое доказательство теоремы Шепли-Фолкмана». Экономическая теория . 3 (2): 371–372. doi :10.1007/bf01212924. ISSN  0938-2259.
31. Guesnerie (1989, стр. 138)
32. Мас-Колелл (1985, стр. 58–61) и Эрроу и Хан (1980, стр. 76–79)
33. Эрроу и Хан (1980, стр. 79–81)
34. Старр (1969, стр. 26): «В конце концов, можно быть безразличным, автомобиль это или лодка, но в большинстве случаев невозможно ни управлять, ни управлять комбинацией наполовину лодка, наполовину автомобиль».
35. Хотеллинг (1935, стр. 74)
36. Wold (1943b, стр. 231 и 239–240) и Wold & Juréen (1953, стр. 146)
37. Самуэльсон (1950, стр. 359–360):

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

38. Диверт (1982, стр. 552–553)
39. Фаррелл (1959, 1961a, 1961b)
40. Батор (1961a, 1961b)
41. Купманс (1961, стр. 478) и другие — например, Фаррелл (1959, стр. 390–391) и Фаррелл (1961a, стр. 484), Батор (1961a, стр. 482–483), Ротенберг (1960, стр. 438) и Старр (1969, стр. 26) — прокомментировали Купманса (1957, стр. 1–126, особенно 9–16 [1.3 Суммирование множеств возможностей], 23–35 [1.6 Выпуклые множества и ценовые последствия оптимальности] и 35–37 [1.7 Роль предположений о выпуклости в анализе])
42. Ротенберг (1960, стр. 447, 1961)
43. Эрроу и Хан (1980, стр. 182)
44. Шепли и Шубик (1966, стр. 806)
45. Aumann (1966, стр. 1–2) использует результаты Aumann (1964, 1965).
46. Взятие выпуклой оболочки невыпуклых предпочтений обсуждалось ранее Уолдом (1943b, стр. 243) и Уолдом и Жюрином (1953, стр. 146), согласно Диверту (1982, стр. 552).
47. Старр и Стинчкомб (1999, стр. 217–218)
48. Эрроу и Хан (1980, стр. 169–182) и Старр (1969, стр. 27–33)
49. Грин и Хеллер (1981, стр. 44)
50. Guesnerie (1989, стр. 99)
51. Мас-Колелл (1987)
52. Вариан (1992, стр. 393–394)

    Мас-Колелл, Уинстон и Грин (1995, стр. 627–630)

53. Эрроу и Хан (1980, стр. 169–182)

    Мас-Колелл (1985, стр. 52–55, 145–146, 152–153 и 274–275)

    Хильденбранд (1974, стр. 37, 115–116, 122 и 168)

    Старр (1997, стр. 169)

    Элликсон (1994, стр. xviii, 306–310, 312, 328–329, 347 и 352)

54. Лаффон, Жан-Жак (1988). «3. Невыпуклости». Основы народной экономики. МТИ Пресс. стр. 63–65. ISBN 0-262-12127-1.
55. Саланье (2000, стр. 112–113 и 107–115)
56. Итииси (1983, стр. 24–25)
57. Касселс (1981, стр. 127 и 33–34)
58. Обин (2007, стр. 458–476)
59. Картер (2001, стр. 93–94, 143, 318–319, 375–377 и 416)
60. Трокель (1984, стр. 30)
61. Bertsekas (1999, стр. 496)
62. Рокафеллар (1997, стр. 23)
63. Лемарешаль (1973, стр. 38) Эксперименты Лемарешаля обсуждались в более поздних публикациях:

    Аардал (1995, стр. 2–3)

    Хириарт-Уррути и Лемарешаль (1993, стр. 143–145, 151, 153 и 156)

64. Экеланд, Ивар (1974). « Априорная оценка в невыпуклом программировании». Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences . Серии A и B (на французском языке). 279 : 149–151. ISSN  0151-0509. МР  0395844.
65. Обин и Экеланд (1976, стр. 226, 233, 235, 238 и 241)
66. Ди Гульельмо (1977, стр. 287–288)
67. Шнайдер и Вейль (2008, стр. 45)
68. Касселс (1975, стр. 433–434)
69. Молчанов (2005, стр. 195–198, 218, 232, 237–238 и 407).
70. Пури и Ралеску (1985, стр. 154–155)
71. Вайль (1982, стр. 203 и 205–206)
72. Серф (1999, стр. 243–244) использует приложения леммы Шепли–Фолкмана из Пури и Ралеску (1985, стр. 154–155).
73. Ружа (1997, стр. 345)
74. Тарделла (1990, стр. 478–479)
75. Vind (1964, стр. 168 и 175) был отмечен лауреатом Нобелевской премии по экономике 1983 года Жераром Дебре . Дебре (1991, стр. 4) писал:

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

76. Артштейн (1980, стр. 172–183)
77. Мас-Колелл (1978, стр. 210)

Ссылки

• Аардал, Карен (март 1995 г.). "Интервью об Optima - Клод Лемарешаль" (PDF) . Optima: Информационный бюллетень Общества математического программирования . 45 : 2–4 . Получено 2 февраля 2011 г. .
• Эрроу, Кеннет Дж .; Хан, Фрэнк Х. (1980) [1971]. Общий конкурентный анализ . Advanced Textbooks in Economics. Том 12 (переиздание Сан-Франциско, Калифорния: Holden-Day, Inc. Mathematical Economics Texts  6  -е изд.). Амстердам: Северная Голландия. ISBN 0-444-85497-5. МР  0439057.
• Артштейн, Цви (1980). «Дискретные и непрерывные пространства bang-bang и лицевые пространства, или: Ищите крайние точки». Обзор SIAM . 22 (2): 172–185. doi :10.1137/1022026. JSTOR  2029960. MR  0564562.Переиздано в праздничном сборнике Роберта Дж. Ауманна , лауреата Нобелевской премии по экономике 2008 года :
  • Artstein, Zvi (1995). "22 Дискретные и непрерывные пространства bang-bang и лицевые или: Ищите крайние точки". В Hart, Sergiu; Neyman, Abraham (ред.). Теория игр и экономики: избранные работы в честь Роберта Дж. Ауманна . Ann Arbor, Mich.: University of Michigan Press. стр. 449–462. ISBN 0-472-10673-2. Архивировано из оригинала 24 мая 2011 года.
• Артштейн, Цви; Витале, Ричард А. (1975). «Усиленный закон больших чисел для случайных компактных множеств». Анналы вероятности . 3 (5): 879–882. ​​doi : 10.1214/aop/1176996275 . JSTOR  2959130. MR  0385966. Zbl  0313.60012. PE  euclid.ss/1176996275.
• Обен, Жан-Пьер (2007). "14.2 Двойственность в случае невыпуклого интегрального критерия и ограничений (особенно 14.2.3 Теорема Шепли–Фолкмана, страницы 463–465)". Математические методы игровой и экономической теории (Переиздание с новым предисловием 1982 North-Holland revision English ed.). Минеола, Нью-Йорк: Dover Publications. ISBN 978-0-486-46265-3. МР  2449499.
• Aubin, J. P.; Ekeland, I. (1976). «Оценки разрыва двойственности в невыпуклой оптимизации». Математика исследования операций . 1 (3): 225–245. doi :10.1287/moor.1.3.225. JSTOR  3689565. MR  0449695.
• Ауманн, Роберт Дж. (январь–апрель 1964 г.). «Рынки с континуумом трейдеров». Econometrica . 32 (1–2): 39–50. doi :10.2307/1913732. JSTOR  1913732. MR  0172689.
• Ауманн, Роберт Дж. (август 1965 г.). «Интегралы функций со значениями множества». Журнал математического анализа и приложений . 12 (1): 1–12. doi : 10.1016/0022-247X(65)90049-1 . MR  0185073.
• Ауманн, Роберт Дж. (январь 1966 г.). «Существование конкурентного равновесия на рынках с континуумом трейдеров». Econometrica . 34 (1): 1–17. doi :10.2307/1909854. JSTOR  1909854. MR  0191623.
• Батор, Фрэнсис М. (октябрь 1961a). «О выпуклости, эффективности и рынках». Журнал политической экономии . 69 (5): 480–483. doi :10.1086/258540. JSTOR  1828537.
• Батор, Фрэнсис М. (октябрь 1961b). «О выпуклости, эффективности и рынках: ответ». Журнал политической экономии . 69 (5): 489. doi :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.
• Bertsekas, Dimitri P. ; Lauer, Gregory S.; Sandell, Nils R. Jr.; Posbergh, Thomas A. (январь 1983 г.). "Оптимальное краткосрочное планирование крупномасштабных энергосистем" (PDF) . IEEE Transactions on Automatic Control . 28 (1): 1–11. doi :10.1109/tac.1983.1103136 . Получено 2 февраля 2011 г. .Труды конференции IEEE 1981 года по принятию решений и управлению, Сан-Диего, Калифорния, декабрь 1981 г., стр. 432–443.
• Борвейн, Дж. М.; О'Брайен, Р. К. (1978). «Отмена характеризует выпуклость». Nanta Mathematica (Университет Наньян) . 11 : 100–102. ISSN  0077-2739. MR  0510842.
• Картер, Майкл (2001). Основы математической экономики. Кембридж, Массачусетс: MIT Press. ISBN 0-262-53192-5. MR  1865841. (Сайт автора с ответами к упражнениям). Архивировано из оригинала 15 сентября 2006 г.
• Cassels, JWS (1975). «Меры невыпуклости множеств и теорема Шепли–Фолкмана–Старра». Математические труды Кембриджского философского общества . 78 (3): 433–436. doi :10.1017/S0305004100051884. MR  0385711.
• Касселс, Дж. В. С. (1981). "Приложение А. Выпуклые множества". Экономика для математиков . Серия лекций Лондонского математического общества. Том 62. Кембридж, Великобритания: Cambridge University Press. ISBN 0-521-28614-X. МР  0657578.
• Серф, Рафаэль (1999). «Большие отклонения для сумм случайных компактных множеств с одинаковым распределением». Труды Американского математического общества . 127 (8): 2431–2436. doi : 10.1090/S0002-9939-99-04788-7 . MR  1487361.
• Дебре, Жерар (март 1991 г.). «Математизация экономической теории». The American Economic Review . 81 (Президентское обращение на 103-м заседании Американской экономической ассоциации, 29 декабря 1990 г., Вашингтон, округ Колумбия): 1–7. JSTOR  2006785.
• Ди Гульельмо, Ф. (1977). «Невыпуклая двойственность в многокритериальной оптимизации». Математика исследования операций . 2 (3): 285–291. doi :10.1287/moor.2.3.285. JSTOR  3689518. MR  0484418.
• Diewert, W. E. (1982). "12 подходов дуальности к микроэкономической теории". В Arrow, Kenneth Joseph ; Intriligator, Michael D. (ред.). Справочник по математической экономике . Справочники по экономике. Том 2. Амстердам: North-Holland Publishing. стр. 535–599. doi :10.1016/S1573-4382(82)02007-4. ISBN 978-0-444-86127-6. МР  0648778.
• Экланд, Ивар (1999) [1976]. "Приложение I: Априорная оценка в выпуклом программировании". В Экланд, Ивар; Темам, Роджер (ред.). Выпуклый анализ и вариационные задачи . Классика прикладной математики. Том 28 (Исправленное переиздание издания North-Holland). Филадельфия: Общество промышленной и прикладной математики (SIAM). стр. 357–373. ISBN 0-89871-450-8. МР  1727362.
• Элликсон, Брайан (1994). Конкурентное равновесие: теория и приложения . Cambridge University Press. doi :10.1017/CBO9780511609411. ISBN 978-0-521-31988-1.
• Фаррелл, М. Дж. (август 1959 г.). «Предположение о выпуклости в теории конкурентных рынков». Журнал политической экономии . 67 (4): 371–391. doi :10.1086/258197. JSTOR  1825163.
• Фаррелл, М. Дж. (октябрь 1961a). «О выпуклости, эффективности и рынках: ответ». Журнал политической экономии . 69 (5): 484–489. doi :10.1086/258541. JSTOR  1828538.
• Фаррелл, М. Дж. (октябрь 1961b). «Предположение о выпуклости в теории конкурентных рынков: ответ». Журнал политической экономии . 69 (5): 493. doi :10.1086/258544. JSTOR  1828541.
• Грин, Джерри; Хеллер, Уолтер П. (1981). "1 Математический анализ и выпуклость с приложениями к экономике". В Arrow, Кеннет Джозеф ; Интрилигатор, Майкл Д. (ред.). Справочник по математической экономике . Справочники по экономике. Том 1. Амстердам: North-Holland Publishing. стр. 15–52. doi :10.1016/S1573-4382(81)01005-9. ISBN 0-444-86126-2. МР  0634800.
• Guesnerie, Roger (1989). "First-best distribution of resources with nonconvexities in production". В Cornet, Bernard; Tulkens, Henry (ред.). Contributions to Operations Research and Economics: The twenty anniversary of CORE (Papers from the symposium performed in Louvain-la-Neuve, January 1987) . Кембридж, Массачусетс: MIT Press. стр. 99–143. ISBN 0-262-03149-3. МР  1104662.
• Хильденбранд, Вернер (1974). Ядро и равновесие большой экономики . Принстонские исследования математической экономики. Том 5. Принстон, Нью-Джерси: Princeton University Press. ISBN 978-0-691-04189-6. МР  0389160.
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). "XII Абстрактная двойственность для практиков". Выпуклый анализ и алгоритмы минимизации, Том  II : Расширенная теория и методы пучков . Основные принципы математических наук. Том 306. Берлин: Springer-Verlag. С. 136–193 (и библиографические комментарии на с. 334–335). ISBN 3-540-56852-2. МР  1295240.
• Хотеллинг, Гарольд (январь 1935 г.). «Функции спроса с ограниченными бюджетами». Econometrica . 3 (1): 66–78. doi :10.2307/1907346. JSTOR  1907346.
• Howe, Roger (ноябрь 1979). On the tendency towards convexity of the vector sum of sets (PDF) (Отчет). Дискуссионные документы Cowles Foundation. Том 538. Нью-Хейвен, Коннектикут: Cowles Foundation for Research in Economics , Йельский университет . Получено 15 января 2011 г.
• Ичииси, Тацуро (1983). Теория игр для экономического анализа . Экономическая теория, эконометрика и математическая экономика. Нью-Йорк: Academic Press [Harcourt Brace Jovanovich, Publishers]. ISBN 0-12-370180-5. МР  0700688.
• Купманс, Тьяллинг К. (1957). «Распределение ресурсов и система цен». В Купманс, Тьяллинг К. (ред.). Три очерка о состоянии экономической науки . Нью-Йорк: McGraw–Hill Book Company. стр. 1–126. ISBN 0-07-035337-9.
• Купманс, Тьяллинг К. (октябрь 1961 г.). «Предположения о выпуклости, эффективность распределения ресурсов и конкурентное равновесие». Журнал политической экономии . 69 (5): 478–479. doi :10.1086/258539. JSTOR  1828536.
• Лемарешаль, Клод (апрель 1973 г.). Utilization de la дуальности в невыпуклых задачах [Использование двойственности для невыпуклых задач] (Отчет) (на французском языке). Domaine de Voluceau, Рокенкур , Ле Шене , Франция: IRIA (ныне INRIA) , Laboratoire de recherche en informationatique et autotique.
• Мас-Колелл, Андре (1978). «Заметка о теореме об эквивалентности ядра: сколько существует блокирующих коалиций?». Журнал математической экономики . 5 (3): 207–215. doi :10.1016/0304-4068(78)90010-1. MR  0514468.
• Мас-Колелл, Андре (1985). "1.L Средние множества". Теория общего экономического равновесия: дифференцируемый подход . Монографии эконометрического общества. Том 9. Cambridge University Press. ISBN 0-521-26514-2. МР  1113262.
• Mas-Colell, A. (1987). «Невыпуклость». В Eatwell, John ; Milgate, Murray ; Newman, Peter (ред.). Новый Palgrave: словарь экономики (первое изд.). Palgrave Macmillan. стр. 653–661. doi :10.1057/9780230226203.3173. ISBN 9780333786765. (PDF-файл на домашней странице Mas-Colell).
• Мас-Колелл, Андре ; Уинстон, Майкл Д.; Грин, Джерри Р. (1995). "17.1 Крупные экономики и невыпуклости". Микроэкономическая теория . Oxford University Press. ISBN 978-0-19-507340-9.
• Молчанов, Илья (2005). "3 Minkowski addition". Теория случайных множеств . Вероятность и ее приложения. Лондон: Springer-Verlag London. стр. 194–240. doi :10.1007/1-84628-150-4. ISBN 978-1-84996-949-9. МР  2132405.
• Пури, Мадан Л.; Ралеску, Дэн А. (1985). «Предельные теоремы для случайных компактных множеств в банаховом пространстве». Математические труды Кембриджского философского общества . 97 (1): 151–158. Bibcode :1985MPCPS..97..151P. doi :10.1017/S0305004100062691. MR  0764504.
• Rockafellar, R. Tyrrell (1997). Выпуклый анализ . Princeton Landmarks in Mathematics. Princeton, NJ: Princeton University Press. ISBN 0-691-01586-4. МР  1451876.. Переиздание 1970 ( MR 274683) Princeton Mathematical Series  28
• Ротенберг, Джером (октябрь 1960 г.). «Невыпуклость, агрегация и оптимальность по Парето». Журнал политической экономии . 68 (5): 435–468. doi :10.1086/258363. JSTOR  1830308.
• Ротенберг, Джером (октябрь 1961 г.). «Комментарии о невыпуклости». Журнал политической экономии . 69 (5): 490–492. doi :10.1086/258543. JSTOR  1828540.
• Ружа, Имре З. (1997). «Неравенство Брунна–Минковского и невыпуклые множества». Geometriae Dedicata . 67 (3): 337–348. doi : 10.1023/A:1004958110076 . MR  1475877.
• Салание, Бернар (2000). «7 невыпуклостей». Микроэкономика провалов рынка . Кембридж, Массачусетс: MIT Press. стр. 107–125. ISBN 0-262-19443-0.Английский перевод французской книги «Микроэкономика: Les défaillances du Marché» (1998 г.) (Economica, Париж)
• Сэмюэлсон, Пол А. (ноябрь 1950 г.). «Проблема интегрируемости в теории полезности». Economica . New Series. 17 (68): 355–385. doi :10.2307/2549499. JSTOR  2549499. MR  0043436.
• Шнайдер, Рольф (1993). Выпуклые тела: Теория Брунна–Минковского. Энциклопедия математики и ее приложений. Том 44. Кембридж, Великобритания: Cambridge University Press. ISBN 0-521-35220-7. МР  1216521.
• Шнайдер, Рольф; Вайль, Вольфганг (2008). Стохастическая и интегральная геометрия . Вероятность и ее приложения. Springer. doi :10.1007/978-3-540-78859-1. ISBN 978-3-540-78858-4. МР  2455326.
• Шепли, Л. С .; Шубик, М. (октябрь 1966 г.). «Квазиядра в денежной экономике с невыпуклыми предпочтениями». Econometrica . 34 (4): 805–827. doi :10.2307/1910101. JSTOR  1910101. Zbl  0154.45303. Архивировано из оригинала 24 сентября 2017 г.
• Старр, Росс М. (1969). «Квазиравновесия на рынках с невыпуклыми предпочтениями (Приложение 2: Теорема Шепли–Фолкмана, стр. 35–37)». Econometrica . 37 (1): 25–38. doi :10.2307/1909201. JSTOR  1909201.
• Starr, Ross M. (2008). «Теорема Шепли–Фолкмана». В Durlauf, Steven N. ; Blume, Lawrence E. (ред.). Новый словарь экономики Palgrave (второе изд.). Palgrave Macmillan. стр. 317–318 (1-е изд.). doi :10.1057/9780230226203.1518. ISBN 978-0-333-78676-5.
• Starr, Ross M. (1997). "8 Выпуклые множества, теоремы разделения и невыпуклые множества в  R (новые главы 22 и 25–26 во втором изд. (2011)). Общая теория равновесия: введение (1-е изд.). Кембридж, Великобритания: Cambridge University Press. ISBN ^{${\displaystyle N}$} 0-521-56473-5. МР  1462618.
• Starr, R. M. ; Stinchcombe, M. B. (1999). "Обмен в сети торговых постов". В Chichilnisky, Graciela (ред.). Рынки, информация и неопределенность: Очерки экономической теории в честь Кеннета Дж. Эрроу . Кембридж, Великобритания: Cambridge University Press. стр. 217–234. doi :10.1017/CBO9780511896583. ISBN 978-0-521-08288-4.
• Тарделла, Фабио (1990). «Новое доказательство теоремы Ляпунова о выпуклости». SIAM Journal on Control and Optimization . 28 (2): 478–481. doi :10.1137/0328026. MR  1040471.
• Трокель, Вальтер (1984). Рыночный спрос: анализ крупных экономик с невыпуклыми предпочтениями . Конспект лекций по экономике и математическим системам. Том 223. Берлин: Springer-Verlag. ISBN 3-540-12881-6. МР  0737006.
• Вариан, Хэл Р. (1992). "21.2 Выпуклость и размер". Микроэкономический анализ (3-е изд.). WW Norton & Company. ISBN 978-0-393-95735-8. МР  1036734.
• Винд, Карл (май 1964). «Распределение Эджворта в экономике обмена со многими трейдерами». International Economic Review . 5 (2): 165–177. doi :10.2307/2525560. JSTOR  2525560.
• Вейль, Вольфганг (1982). «Применение центральной предельной теоремы для случайных величин со значениями в банаховом пространстве к теории случайных множеств». Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete [ Теория вероятностей и смежные области ]. 60 (2): 203–208. дои : 10.1007/BF00531823 . МР  0663901.
• Уолд, Герман (1943b). «Синтез чистого анализа спроса  II ». Skandinavisk Aktuarietidskrift [ Скандинавский актуарный журнал ]. 26 : 220–263. doi :10.1080/03461238.1943.10404737. MR  0011939.
• Уолд, Герман ; Юрен, Ларс (совместно с Уолдом) (1953). "8 Некоторые дополнительные применения полей предпочтений (стр. 129–148)". Анализ спроса: исследование по эконометрике . Публикации Wiley по статистике. Нью-Йорк: John Wiley and Sons. MR  0064385.

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

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