Выпуклый набор

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

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

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

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

Граница выпуклого множества на плоскости всегда является выпуклой кривой . Пересечение всех выпуклых множеств, содержащих данное подмножество A евклидова пространства, называется выпуклой оболочкой A . Это наименьшее выпуклое множество, содержащее A.

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

Понятие выпуклого множества можно обобщить, как описано ниже.

Определения

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

Пусть S — векторное пространство или аффинное пространство над действительными числами или, в более общем плане, над некоторым упорядоченным полем (сюда входят евклидовы пространства, которые являются аффинными пространствами). Подмножество C из S является выпуклым , если для всех x и y в C отрезок , соединяющий x и y, включен в C .

Это означает, что аффинная комбинация (1 − t ) x + ty принадлежит C для всех x, y в C и t в интервале [0, 1] . Отсюда следует, что выпуклость инвариантна относительно аффинных преобразований . Кроме того, из этого следует, что выпуклое множество в вещественном или комплексном топологическом векторном пространстве линейно связно (и, следовательно, также связно ).

Множество C естьстрого выпуклый, если каждая точка отрезка, соединяющегоxиy, кроме конечных точек, находится внутритопологическойвнутренностиC. Замкнутое выпуклое подмножество является строго выпуклым тогда и только тогда, когда каждая егограничная точкаявляетсякрайней точкой.^[3]

Множество C абсолютно выпукло, если оно выпукло и уравновешено .

Примеры

Выпуклые подмножества R (множество действительных чисел) — это интервалы и точки R . Некоторыми примерами выпуклых подмножеств евклидовой плоскости являются сплошные правильные многоугольники , сплошные треугольники и пересечения сплошных треугольников. Некоторыми примерами выпуклых подмножеств евклидова трехмерного пространства являются архимедовы тела и платоновые тела . Многогранники Кеплера -Пуансо являются примерами невыпуклых множеств.

Невыпуклый набор

Множество, которое не является выпуклым, называется невыпуклым множеством . Многоугольник , который не является выпуклым многоугольником , иногда называют вогнутым многоугольником ^[4] , а в некоторых источниках термин «вогнутый набор» обычно используется для обозначения невыпуклого набора ^[5] , но большинство авторитетных источников запрещают такое использование. ^{[6] [7]}

Дополнение выпуклого множества, такое как надграфик вогнутой функции , иногда называют обратно-выпуклым множеством , особенно в контексте математической оптимизации . ^[8]

Характеристики

Учитывая r точек u ₁ , ..., ur _в выпуклом множестве S и r неотрицательных чисел λ ₁ , ..., λ _r таких, что λ ₁ + ... + λ _r = 1 , аффинная комбинация

$${\displaystyle \sum _{k=1}^{r}\lambda _{k}u_{k}}$$

С.r = 2

Такая аффинная комбинация называется выпуклой комбинацией u 1 _, ... _, ur .

Пересечения и союзы

Совокупность выпуклых подмножеств векторного пространства, аффинного пространства или евклидова пространства обладает следующими свойствами: ^{[9] [10]}

1. Пустое множество и все пространство выпуклые.
2. Пересечение любого набора выпуклых множеств является выпуклым.
3. Объединение последовательности выпуклых множеств называется выпуклым, если они образуют неубывающую по включению цепочку. Для этого свойства важно ограничение на цепи, поскольку объединение двух выпуклых множеств не обязательно должно быть выпуклым.

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

Замкнутые выпуклые множества — это выпуклые множества, содержащие все свои предельные точки . Их можно охарактеризовать как пересечения замкнутых полупространств (множеств точек в пространстве, лежащих на гиперплоскости и по одну ее сторону ).

Из только что сказанного ясно, что такие пересечения выпуклы и тоже будут замкнутыми множествами. Чтобы доказать обратное, т. е. любое замкнутое выпуклое множество можно представить как такое пересечение, нужна опорная теорема о гиперплоскости в виде того, что для данного замкнутого выпуклого множества C и точки P вне его существует замкнутое полупространство H , которое содержит C , а не P. Теорема о опорной гиперплоскости является частным случаем теоремы Хана–Банаха функционального анализа .

Выпуклые множества и прямоугольники

Пусть C — выпуклое тело на плоскости (выпуклое множество, внутренность которого непуста). Мы можем вписать прямоугольник r в C так, что гомотетическая копия R прямоугольника r описана вокруг C . Положительный коэффициент гомотетии не превышает 2 и: ^[11]

$${\displaystyle {\tfrac {1}{2}}\cdot \operatorname {Area} (R)\leq \operatorname {Area} (C)\leq 2\cdot \operatorname {Area} (r)}$$

Диаграммы Бляшке-Сантало

Набор всех плоских выпуклых тел можно параметризовать с точки зрения диаметра выпуклого тела D , его внутреннего радиуса r (самый большой круг, содержащийся в выпуклом теле) и его радиуса описанной окружности R (наименьший круг, содержащий выпуклое тело). Фактически, это множество можно описать набором неравенств, заданных ^{[12], [13]} ${\displaystyle {\mathcal {K}}^{2}}$

$${\displaystyle 2r\leq D\leq 2R}$$

$${\displaystyle R\leq {\frac {\sqrt {3}}{3}}D}$$

$${\displaystyle r+R\leq D}$$

$${\displaystyle D^{2}{\sqrt {4R^{2}-D^{2}}}\leq 2R(2R+{\sqrt {4R^{2}-D^{2}}})}$$

g^точку R2rRDRrDR^[13]

Диаграмма Бляшке-Сантало ( r , D , R ) для плоских выпуклых тел. обозначает отрезок прямой, равносторонний треугольник, треугольник Рело и единичную окружность. ${\displaystyle \mathbb {L} }$ ${\displaystyle \mathbb {I} _{\frac {\pi }{3}}}$ ${\displaystyle \mathbb {RT} }$ ${\displaystyle \mathbb {B} _{2}}$

В качестве альтернативы набор также можно параметризовать по его ширине (наименьшему расстоянию между любыми двумя различными параллельными опорными гиперплоскостями), периметру и площади. ^{[12] [13]} ${\displaystyle {\mathcal {K}}^{2}}$

Другие объекты недвижимости

Пусть X — топологическое векторное пространство и выпукло. ${\displaystyle C\subseteq X}$

• ${\displaystyle \operatorname {Cl} C}$и оба выпуклы (т. е. замыкание и внутренность выпуклых множеств выпуклы). ${\displaystyle \operatorname {Int} C}$
• Если и тогда (где ). ${\displaystyle a\in \operatorname {Int} C}$ ${\displaystyle b\in \operatorname {Cl} C}$ ${\displaystyle [a,b[\,\subseteq \operatorname {Int} C}$ ${\displaystyle [a,b[\,:=\left\{(1-r)a+rb:0\leq r<1\right\}}$
• Если тогда: ${\displaystyle \operatorname {Int} C\neq \emptyset }$
  • ${\displaystyle \operatorname {cl} \left(\operatorname {Int} C\right)=\operatorname {Cl} C}$, и
  • ${\displaystyle \operatorname {Int} C=\operatorname {Int} \left(\operatorname {Cl} C\right)=C^{i}}$, где – алгебраическая внутренность C . ${\displaystyle C^{i}}$

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

Выпуклые оболочки

Каждое подмножество A векторного пространства содержится в наименьшем выпуклом множестве (называемом выпуклой оболочкой A ) , а именно в пересечении всех выпуклых множеств, содержащих A. Оператор выпуклой оболочки Conv() обладает характерными свойствами оператора выпуклой оболочки :

• обширный : S  ⊆ Conv( S ) ,
• неубывающее : S  ⊆  T означает, что Conv( S ) ⊆ Conv( T ) и
• идемпотент : Conv(Conv( S )) = Conv( S ) .

Операция выпуклой оболочки необходима для того, чтобы набор выпуклых множеств образовал решетку , в которой операция « соединения » представляет собой выпуклую оболочку объединения двух выпуклых множеств.

$${\displaystyle \operatorname {Conv} (S)\vee \operatorname {Conv} (T)=\operatorname {Conv} (S\cup T)=\operatorname {Conv} {\bigl (}\operatorname {Conv} (S)\cup \operatorname {Conv} (T){\bigr )}.}$$

решетку

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

Минковский сложение множеств. Сумма квадратов Q ₁ =[0,1] ² и Q ₂ =[1,2] ² представляет собой квадрат Q ₁ +Q ₂ =[1,3] ² .

В реальном векторном пространстве сумма Минковского двух (непустых) множеств, S ₁ и S ₂ , определяется как набор S ₁  +  S ₂ , образованный путем поэлементного сложения векторов из наборов слагаемых.

$${\displaystyle S_{1}+S_{2}=\{x_{1}+x_{2}:x_{1}\in S_{1},x_{2}\in S_{2}\}.}$$

сумма МинковскогоSn - это набор, _{образованный}

$${\displaystyle \sum _{n}S_{n}=\left\{\sum _{n}x_{n}:x_{n}\in S_{n}\right\}.}$$

Для сложения Минковского нулевое множество  {0} , содержащее только нулевой вектор  0, имеет особое значение : для каждого непустого подмножества S векторного пространства

$${\displaystyle S+\{0\}=S;}$$

{0}единичный элемент^[14]

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

Сложение Минковского хорошо работает по отношению к операции взятия выпуклых оболочек, как показывает следующее предложение:

Пусть S1 , S2 _— подмножества вещественного векторного пространства, выпуклая оболочка их суммы Минковского — это сумма Минковского их выпуклых оболочек _.

$${\displaystyle \operatorname {Conv} (S_{1}+S_{2})=\operatorname {Conv} (S_{1})+\operatorname {Conv} (S_{2}).}$$

Этот результат справедлив в более общем смысле для каждого конечного набора непустых множеств:

$${\displaystyle {\text{Conv}}\left(\sum _{n}S_{n}\right)=\sum _{n}{\text{Conv}}\left(S_{n}\right).}$$

В математической терминологии операции суммирования Минковского и формирования выпуклых оболочек являются коммутирующими операциями. ^{[15] [16]}

Суммы Минковского выпуклых множеств

Сумма Минковского двух компактных выпуклых множеств компактна. Сумма выпуклого компакта и выпуклого замкнутого множества замкнута. ^[17]

Следующая знаменитая теорема, доказанная Дьедонне в 1966 году, дает достаточное условие замкнутости разности двух замкнутых выпуклых подмножеств. ^[18] Он использует концепцию конуса рецессии непустого выпуклого подмножества S , определяемого как:

$${\displaystyle \operatorname {rec} S=\left\{x\in X\,:\,x+S\subseteq S\right\},}$$

выпуклый конусS ${\displaystyle 0\in X}$ ${\displaystyle S+\operatorname {rec} S=S}$ ${\displaystyle \operatorname {rec} S}$ ${\displaystyle s_{0}\in S}$

$${\displaystyle \operatorname {rec} S=\bigcap _{t>0}t(S-s_{0}).}$$

Теорема (Дьедонне). Пусть A и B — непустые, замкнутые и выпуклые подмножества локально выпуклого топологического векторного пространства, которое является линейным подпространством. Если A или B локально компактны, то A −  B  замкнуто . ${\displaystyle \operatorname {rec} A\cap \operatorname {rec} B}$

Обобщения и расширения выпуклости.

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

Звездо-выпуклые (звездообразные) множества

Пусть C — множество в вещественном или комплексном векторном пространстве. C является выпуклой звездой (звездообразной), если существует x ₀ в C такой, что отрезок прямой от x ₀ до любой точки y в C содержится в C . Следовательно, непустое выпуклое множество всегда звездно-выпуклое, но звездчатое множество не всегда выпуклое.

Ортогональная выпуклость

Примером обобщенной выпуклости является ортогональная выпуклость . ^[19]

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

Неевклидова геометрия

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

Заказать топологию

Выпуклость может быть распространена на полностью упорядоченное множество X , наделенное порядковой топологией . ^[20]

Пусть Y ⊆ X. _ Подпространство Y является выпуклым множеством, если для каждой пары точек a , b в Y такой, что a ⩽ b , интервал [ a , b ] = { x ∈ X | a ≤ x ≤ b } содержится в Y . То есть Y является выпуклым тогда и только тогда , когда для всех a , b в Y , a ⩽ b влечет [ a , b ] ⊆ Y.

Выпуклое множество вообще не связно: контрпример дается подпространством {1,2,3} в Z , которое одновременно выпукло и несвязно.

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

Понятие выпуклости можно обобщить и на другие объекты, если в качестве аксиом выбрать определенные свойства выпуклости .

Для данного множества X выпуклость над X — это совокупность 𝒞 подмножеств X , удовлетворяющая следующим аксиомам: ^{[9] [10]} [ ^21]

1. Пустое множество и X находятся в 𝒞
2. Пересечение любой коллекции из 𝒞 находится в 𝒞 .
3. Объединение цепи ( по отношению включения ) элементов из 𝒞 находится в 𝒞 .

Элементы 𝒞 называются выпуклыми множествами, а пара ( X , 𝒞 ) называется выпуклым пространством . Для обычной выпуклости справедливы первые две аксиомы, а третья тривиальна.

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

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

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

Смотрите также

• Поглощающий набор
• Алгоритмические задачи на выпуклых множествах
• Ограниченное множество (топологическое векторное пространство)
• Теорема Брауэра о неподвижной точке
• Сложная выпуклость
• Выпуклая оболочка
• Выпуклая серия
• Выпуклое метрическое пространство
• Теорема Каратеодори (выпуклая оболочка)
• Теория Шоке
• Теорема Хелли
• Голоморфно выпуклая оболочка
• Цело-выпуклое множество
• Джон эллипсоид
• Псевдовыпуклость
• Теорема Радона
• Лемма Шепли – Фолкмана.
• Симметричный набор

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

1. Моррис, Карла С.; Старк, Роберт М. (24 августа 2015 г.). Конечная математика: модели и приложения. Джон Уайли и сыновья. п. 121. ИСБН 9781119015383. Проверено 5 апреля 2017 г.
2. Кьельдсен, Тинне Хофф. «История выпуклости и математического программирования» (PDF) . Труды Международного конгресса математиков (ICM 2010): 3233–3257. дои : 10.1142/9789814324359_0187. Архивировано из оригинала (PDF) 11 августа 2017 г. Проверено 5 апреля 2017 г.
3. Халмос, Пол Р. (8 ноября 1982 г.). Книга задач о гильбертовом пространстве . Тексты для аспирантов по математике . Том. 19 (2-е изд.). Нью-Йорк: Springer-Verlag . п. 5. ISBN 978-0-387-90685-0. ОСЛК  8169781.
4. МакКоннелл, Джеффри Дж. (2006). Компьютерная графика: теория на практике. п. 130. ИСБН 0-7637-2250-2..
5. Вайсштейн, Эрик В. «Вогнутый». Математический мир .
6. Такаяма, Акира (1994). Аналитические методы в экономике. Издательство Мичиганского университета. п. 54. ИСБН 9780472081356. Часто встречающаяся путаница - это «вогнутый набор». Вогнутые и выпуклые функции обозначают определенные классы функций, а не множеств, тогда как выпуклое множество обозначает определенный класс множеств, а не класс функций. «Вогнутое множество» путает множества с функциями.
7. Корбэ, Дин; Стинчкомб, Максвелл Б.; Земан, Юрай (2009). Введение в математический анализ для экономической теории и эконометрики. Издательство Принстонского университета. п. 347. ИСБН 9781400833085. Не существует такого понятия, как вогнутый набор.
8. Мейер, Роберт (1970). «Действительность семейства методов оптимизации» (PDF) . SIAM Journal по контролю и оптимизации . 8 : 41–54. дои : 10.1137/0308003. МР  0312915..
9. Солтан, Валериу, Введение в аксиоматическую теорию выпуклости , Штиинца, Кишинев , 1984 (на русском языке).
10. Сингер, Иван (1997). Абстрактный выпуклый анализ . Серия монографий и продвинутых текстов Канадского математического общества. Нью-Йорк: John Wiley & Sons, Inc., стр. xxii+491. ISBN 0-471-16015-6. МР  1461544.
11. Лассак, М. (1993). «Приближение выпуклых тел прямоугольниками». Геометрии посвященные . 47 : 111–117. дои : 10.1007/BF01263495. S2CID  119508642.
12. Сантало, Л. (1961). «Собре лос системс завершено де десигуалдадес энтре трех элементов де уна фигура выпуклых плоскостей». Математические заметки . 17 : 82–104.
13. Бранденберг, Рене; Гонсалес Мерино, Бернардо (2017). «Полная трехмерная диаграмма Бляшке-Сантало». Математические неравенства и приложения (2): 301–348. arXiv : 1404.6808 . дои : 10.7153/mia-20-22 . ISSN  1331-4343.
14. Пустой набор важен для сложения Минковского, потому что пустой набор аннулирует все остальные подмножества: Для каждого подмножества S векторного пространства его сумма с пустым набором пуста: . ${\displaystyle S+\emptyset =\emptyset }$
15. Теорема 3 (страницы 562–563): Крейн, М .; Шмулян, В. (1940). «О правильно выпуклых множествах в пространстве, сопряженном с банаховым пространством». Анналы математики . Вторая серия. 41 (3): 556–583. дои : 10.2307/1968735. JSTOR  1968735.
16. О коммутативности сложения и овыпукливания Минковского см. Теорему 1.1.2 (страницы 2–3) у Шнайдера; в этом справочнике обсуждается большая часть литературы по выпуклым оболочкам сумм Минковского в «Добавлении Минковского к главе 3» (страницы 126–196): Шнайдер, Рольф (1993). Выпуклые тела: теория Брунна–Минковского. Энциклопедия математики и ее приложений. Том. 44. Кембридж: Издательство Кембриджского университета. стр. xiv+490. ISBN 0-521-35220-7. МР  1216521.
17. Лемма 5.3: Алипрантис, CD; Граница, КЦ (2006). Бесконечномерный анализ, Путеводитель для автостопщика . Берлин: Шпрингер. ISBN 978-3-540-29587-7.
18. Залинеску, К. (2002). Выпуклый анализ в общих векторных пространствах . Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., Inc., с. 7. ISBN 981-238-067-1. МР  1921556.
19. Роулинз Г.Дж.Э. и Вуд Д., «Ортовыпуклость и ее обобщения», в: Вычислительная морфология , 137–152. Эльзевир , 1988.
20. Манкрес, Джеймс ; Топология , Прентис Холл; 2-е издание (28 декабря 1999 г.). ISBN 0-13-181629-2 . 
21. ван Де Вель, Марсель LJ (1993). Теория выпуклых структур . Математическая библиотека Северной Голландии. Амстердам: North-Holland Publishing Co., стр. xvi+540. ISBN 0-444-81505-8. МР  1234493.

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

• «Выпуклое подмножество». Энциклопедия математики . ЭМС Пресс . 2001 [1994].
• Лекции по выпуклым множествам, заметки Нильса Лауритцена, в Орхусском университете , март 2010 г.