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

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

Иллюстрация выпуклого множества в форме деформированного круга. Отрезок прямой, соединяющий точки 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 ₁ , ..., u _r в выпуклом множестве S и r неотрицательных чисел λ ₁ , ..., λ _r таких, что λ ₁ + ... + λ _r = 1 аффинная комбинация принадлежит S. Поскольку определение выпуклого множества имеет место при r = 2 , это свойство характеризует выпуклые множества. $${\displaystyle \sum _{k=1}^{r}\lambda _{k}u_{k}}$$

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

Пересечения и объединения

Совокупность выпуклых подмножеств векторного пространства, аффинного пространства или евклидова пространства обладает следующими свойствами: ^{[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],} и может быть визуализировано как изображение функции g , которая отображает выпуклое тело в точку R ^{2 ,} заданную как ( r / R , D /2 ​​R ). Изображение этой функции известно как ( r , D , R ) диаграмма Блахке-Сантало. ^[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}}})}$$

Диаграмма Блашке-Сантало ( 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 ₂ , образованное поэлементным сложением векторов из множеств слагаемых. В более общем смысле, сумма Минковского конечного семейства (непустых) множеств S _n — это множество, образованное поэлементным сложением векторов. $${\displaystyle S_{1}+S_{2}=\{x_{1}+x_{2}:x_{1}\in S_{1},x_{2}\in S_{2}\}.}$$ $${\displaystyle \sum _{n}S_{n}=\left\{\sum _{n}x_{n}:x_{n}\in S_{n}\right\}.}$$

Для сложения Минковского нулевое множество  {0} , содержащее только нулевой вектор  0, имеет особое значение : для каждого непустого подмножества S векторного пространства в алгебраической терминологии {0} является единичным элементом сложения Минковского (на совокупности непустых множеств). ^[14] $${\displaystyle S+\{0\}=S;}$$

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

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

Пусть S ₁ , S ₂ — подмножества действительного векторного пространства, выпуклая оболочка их суммы Минковского — это сумма Минковского их выпуклых оболочек. $${\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 , определяемого как: где это множество является выпуклым конусом, содержащим и удовлетворяющим . Обратите внимание, что если S замкнуто и выпукло, то замкнуто и для всех , $${\displaystyle \operatorname {rec} S=\left\{x\in X\,:\,x+S\subseteq S\right\},}$$ ${\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 г.). Конечная математика: модели и приложения. John Wiley & Sons. стр. 121. ISBN 9781119015383. Получено 5 апреля 2017 г.
2. Kjeldsen, Tinne Hoff. "History of Convexity and Mathematical Programming" (PDF) . Труды Международного конгресса математиков (ICM 2010): 3233–3257. doi :10.1142/9789814324359_0187. Архивировано из оригинала (PDF) 2017-08-11 . Получено 5 апреля 2017 .
3. Халмош, Пол Р. (8 ноября 1982 г.). Книга задач о Гильбертовом пространстве . Graduate Texts in Mathematics . Том 19 (2-е изд.). Нью-Йорк: Springer-Verlag . С. 5. ISBN 978-0-387-90685-0. OCLC  8169781.
4. Макконнелл, Джеффри Дж. (2006). Компьютерная графика: теория на практике. стр. 130. ISBN 0-7637-2250-2..
5. Вайсштейн, Эрик В. «Вогнутый». MathWorld .
6. Такаяма, Акира (1994). Аналитические методы в экономике. Издательство Мичиганского университета. стр. 54. ISBN 9780472081356. Часто встречающаяся путаница — это «вогнутое множество». Вогнутые и выпуклые функции обозначают определенные классы функций, а не множеств, тогда как выпуклое множество обозначает определенный класс множеств, а не класс функций. «Вогнутое множество» путает множества с функциями.
7. Corbae, Dean; Stinchcombe, Maxwell B.; Zeman, Juraj (2009). Введение в математический анализ для экономической теории и эконометрики. Princeton University Press. стр. 347. ISBN 9781400833085. Вогнутых множеств не существует.
8. Мейер, Роберт (1970). «Достоверность семейства методов оптимизации» (PDF) . Журнал SIAM по управлению и оптимизации . 8 : 41–54. doi :10.1137/0308003. MR  0312915..
9. Солтан, Валериу, Введение в аксиоматическую теорию выпуклости , Штиинца, Кишинев , 1984 (на русском языке).
10. Singer, Ivan (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/миа-20-22 . ISSN  1331-4343.
14. Пустое множество важно в сложении Минковского, поскольку пустое множество аннулирует все остальные подмножества: Для каждого подмножества S векторного пространства его сумма с пустым множеством пуста: . ${\displaystyle S+\emptyset =\emptyset }$
15. Теорема 3 (страницы 562–563): Крейн, М.; Шмульян, В. (1940). «О регулярно выпуклых множествах в пространстве, сопряженном с банаховым пространством». Annals of Mathematics . Вторая серия. 41 (3): 556–583. doi :10.2307/1968735. JSTOR  1968735.
16. О коммутативности сложения и выпуклости Минковского см. теорему 1.1.2 (стр. 2–3) в Schneider; эта ссылка обсуждает большую часть литературы по выпуклым оболочкам сумм Минковского в своей "Главе 3 Сложение Минковского" (стр. 126–196): Schneider, Rolf (1993). Выпуклые тела: Теория Брунна–Минковского. Энциклопедия математики и ее приложений. Т. 44. Кембридж : Издательство Кембриджского университета. С. xiv+490. ISBN  0-521-35220-7. МР  1216521.
17. Лемма 5.3: Aliprantis, CD; Border, KC (2006). Бесконечномерный анализ, A Hitchhiker's Guide . Берлин: Springer. ISBN 978-3-540-29587-7.
18. Zălinescu, C. (2002). Выпуклый анализ в общих векторных пространствах . River Edge, NJ: World Scientific Publishing Co., Inc. стр. 7. ISBN 981-238-067-1. МР  1921556.
19. Роулинс Г. Дж. Э. и Вуд Д., «Орто-выпуклость и ее обобщения», в: Computational Morphology , 137-152. Elsevier , 1988.
20. Манкрес, Джеймс ; Топология , Prentice Hall; 2-е издание (28 декабря 1999 г.). ISBN 0-13-181629-2 . 
21. Ван Де Вел, Марсель Л. Дж. (1993). Теория выпуклых структур . Математическая библиотека Северной Голландии. Амстердам: North-Holland Publishing Co. стр. xvi+540. ISBN 0-444-81505-8. МР  1234493.

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

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