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

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

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

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

История и применение

Теория выпуклых множеств основана Герман Минковский в своей работе геометрии чисел , Лейпциг 1910. найти применение для наборов выпуклых. Б. в выпуклой оптимизации или компьютерной анимации , где выпуклые многогранники легче обрабатывать, чем невыпуклые во многих отношениях.

Определение векторных пространств

Подмножество в реальном или комплексном векторном пространстве называется выпуклым , если для всех и для всех с всегда имеет место: ${\ displaystyle M}$ ${\ displaystyle V}$${\ displaystyle a, b \ in M}$${\ displaystyle \ lambda \ in \ mathbb {R}}$${\ displaystyle 0 \ leq \ lambda \ leq 1}$

${\ displaystyle \ lambda a + (1- \ lambda) b \ in M.}$

Это определение основано на параметрическом представлении связи между и : ${\ displaystyle a}$${\ displaystyle b}$

${\ displaystyle {\ overline {ab}}: = \ {\ lambda a + (1- \ lambda) b \ mid \ lambda \ in \ mathbb {R}, 0 \ leq \ lambda \ leq 1 \}.}$

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

Примеры

Примеры невыпуклых фигур плоскости

• Любое векторное пространство, которое содержит, выпукло, как полуплоскости и полупространства .${\ Displaystyle \ mathbb {R}}$
• Примеры подмножеств описательного евклидова пространства :
  • Пустое множество , и любой одноэлементно выпуклые.
  • Конечные множества являются выпуклыми тогда и только тогда, когда они содержат не более одного элемента.
  • Линии и линии - это выпуклые множества.
  • Каждая треугольная грань и все простые правильные многоугольники выпуклы.
  • Круглые диски и сферы бывают выпуклыми, даже строго выпуклыми.
  • Среди квадратов z. B. Параллелограммы выпуклые, в то время как есть трапеции и квадраты воздушных змеев , которые не являются выпуклыми , например запутанная трапеция или квадрат со стрелкой .
  • Кубы , Платоновы тела и Пики выпуклые.
  • Подмножество , что лежит выше или ниже графика на выпуклой или вогнутой функции является выпуклой.
  • Тор не является выпуклым.
  • Топологическая граница выпуклого множества , как правило , не выпуклые.

характеристики

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

• Пересечение любого числа выпуклых множеств (также бесконечно) выпукло. Таким образом, выпуклые подмножества векторного пространства образуют систему оболочек . В частности, для каждого подмножества существует порожденное им выпуклое множество, так называемая выпуклая оболочка этого множества. Это не что иное, как среднее значение всех выпуклых множеств, составляющих данное подмножество.

• Объединение выпуклых множеств, как правило, не выпукло. Но объединение восходящей цепочки выпуклых множеств снова выпукло.

• В локально выпуклых пространствах , компактное выпуклое множество является закрытием выпуклых комбинаций его крайних точек ( теорема Крейна-Мильман ). Крайняя точка - это точка, которая не находится между двумя точками . В конечномерных пространствах можно даже обойтись без окончательной формации, потому что согласно теореме Каратеодори каждая точка компактного выпуклого подмножества n-мерного пространства является выпуклой комбинацией не более чем n + 1 крайних точек этого множества.${\ displaystyle M}$${\ displaystyle M}$

Стабильность при эксплуатации

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

• Образы и архетипы выпуклых множеств под действием аффинной функции с и снова выпуклы. Как особый случай, это включает в себя перевод по вектору (установка единичной матрицы) и масштабирование по коэффициенту (установка ).${\ displaystyle f (x) = Ax + b}$${\ Displaystyle А \ в \ mathbb {R} ^ {м \ раз п}}$${\ displaystyle b \ in \ mathbb {R} ^ {m}}$${\ displaystyle b}$${\ displaystyle A = E}$${\ displaystyle a}$${\ displaystyle A = aE, \, b = 0}$
• Сумма Минковского двух выпуклых множеств снова выпукла.${\ Displaystyle K_ {1} + K_ {2} = \ {x_ {1} + x_ {2} | \, x_ {1} \ in K_ {1}, \, x_ {2} \ in K_ {2} \}}$
• Декартово произведение двух выпуклых множеств является выпуклым снова.${\ displaystyle K_ {1} \ times K_ {2}}$
• Всякая проекция выпуклого множества на координатную ось снова выпуклая.${\ Displaystyle е (х) = х_ {я}}$
• Если термин для каждого , то образ выпуклого множества находится под функцией${\ displaystyle x \ in K}$${\ displaystyle c ^ {T} x + d> 0}$${\ displaystyle K}$

${\ displaystyle f (x) = {\ frac {Ax + b} {c ^ {T} x + d}}}$

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

Особые случаи

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

• Множество называется строго выпуклым, если открытая линия, соединяющая любые две точки в множестве, полностью находится внутри множества. Ясно, что строго выпуклые множества не имеют прямолинейных граничных частей.${\ displaystyle M}$
• Множество называется гладко выпуклым, если каждая граничная точка множества имеет единственную опорную гиперплоскость . Ясно, что гладкие выпуклые множества не имеют углов и ребер.${\ displaystyle M}$

Стандартные пространства

Условия выпуклости

В нормализованных пространствах , то есть в векторных пространствах с нормой, которая присваивает длину каждому вектору , выпуклые множества могут быть построены с использованием нормы. Наиболее важным выпуклым множеством для теории нормированных пространств является единичная сфера . ${\ Displaystyle (V, \ | \ cdot \ |)}$${\ displaystyle V}$ ${\ Displaystyle \ | \ cdot \ |}$${\ displaystyle x \ in V}$${\ Displaystyle \ | х \ |}$ ${\ Displaystyle B_ {V}: = \ {х \ в V; \, \ | х \ | \ Leq 1 \}}$

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

Нормальная структура

Точка ограниченного выпуклого множества называется диаметральной для M, если она равна диаметру . В единичной сфере диаметрально противоположны именно краевые точки, т. Е. Векторы длины 1. Для сегмента в нормализованном пространстве конечные точки этого сегмента точно диаметральны. В этих двух примерах всегда есть точки, отличные от диаметра. Это считается «нормальным» свойством и определяет: ${\ displaystyle x}$${\ Displaystyle M \ подмножество V}$${\ Displaystyle \ sup \ {\ | ху \ |; \, у \ в М \}}$${\ displaystyle M}$

Ограниченное выпуклое множество имеет нормальную структуру, если каждое замкнутое и выпуклое подмножество, которое оно содержит хотя бы с двумя точками, содержит точки, не диаметрально противоположные относительно . ${\ displaystyle M}$${\ displaystyle M}$

Можно показать, что каждое компактное выпуклое множество в нормализованном пространстве имеет нормальную структуру. Поскольку ограниченные замкнутые множества в конечномерных пространствах компактны согласно теореме Гейне-Бореля , все ограниченные выпуклые множества в конечномерных пространствах имеют нормальную структуру. Таким образом, появление ограниченных выпуклых множеств без нормальной структуры является чисто бесконечномерным явлением.

Обобщения

В общем, для содержательного определения выпуклости достаточно значительно более слабых предпосылок для геометрии, которые применяются к. Из системы аксиом евклидовой геометрии Гильберта нужны только аксиомы связи и аксиомы расположения. Выпуклость зависит, в частности, от определения прямого пути соединения. Полуплоскость, которая определяется как , является выпуклой в евклидовой плоскости , но невыпуклой в плоскости Моултона : например, «прямая линия» проходит между точкой и над ней (не входит в набор) . См. Также коллинеарность . ${\ displaystyle M}$${\ displaystyle \ {(x, y) \ in \ mathbb {R} ^ {2} \ mid x + y \ leq 0 \}}$${\ displaystyle (-1.1)}$${\ displaystyle (1, -1)}$${\ displaystyle (0, {\ tfrac {1} {3}})}$

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

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

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

Набор вместе с набором подмножеств является называется выпуклость пространством , если : ${\ displaystyle X}$ ${\ Displaystyle {\ mathcal {K}} \ substeq {\ mathcal {P}} (X)}$${\ Displaystyle {\ mathcal {K}}}$

• пустое множество и сами лежат в${\ displaystyle X}$${\ Displaystyle {\ mathcal {K}}}$
• пересечение любого числа множеств снова в${\ Displaystyle {\ mathcal {K}}}$${\ Displaystyle {\ mathcal {K}}}$
• Если подмножество вполне упорядочено в отношении включения , так что лежит объединение всех множеств в .${\ displaystyle K \ subset {\ mathcal {K}}}$ ${\ displaystyle K}$${\ Displaystyle {\ mathcal {K}}}$

Тогда множества из называются те выпуклые множества . ${\ Displaystyle {\ mathcal {K}}}$ ${\ displaystyle X}$

Метрически выпуклое пространство

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

Метрическое пространство называется метрический выпуклым , если есть всегда третья точка для каждых двух различных точек таким образом , что равенство даже применяется в неравенстве треугольника : ${\ displaystyle (X, d)}$${\ displaystyle x, y \ in X}$${\ Displaystyle г \ в Икс \ setminus \ {х, у \}}$

${\ displaystyle d (x, y) = d (x, z) + d (z, y)}$ .

С точки , удовлетворяющей этому условию, говорят: ${\ Displaystyle г \ в Икс \ setminus \ {х, у \}}$

${\ displaystyle z}$лежит между и${\ displaystyle x}$${\ displaystyle y}$ .

Однако здесь уже неверно, что пересечение метрически выпуклых множеств снова было бы метрически выпуклым. Круговая линия с метрикой длины дуги является метрически выпуклой, два замкнутых полукруга , которые не пересекаются, за исключением своих двух конечных точек , также являются метрически выпуклыми (частичными) множествами, но их двухэлементное сечение - нет. ${\ displaystyle x, y}$ ${\ Displaystyle \ {х, у \}}$

Основным результатом о метрически выпуклых пространствах является теорема Менгера о связности .

Геодезически выпуклые многообразия

Полуримановы многообразия обладают внутренней метрикой, определяющей геодезические многообразия. Если каждую пару точек в окрестности можно соединить одной геодезической многообразия, целиком лежащей в этой окрестности, эту окрестность просто называют выпуклой . ${\ displaystyle (M, g)}$

Подмногообразие риманово многообразие есть геодезически выпуклая , если любые две точки на кривой в можно подключать ко в длине сведение к минимуму глобальной геодезической есть. ${\ Displaystyle C \ подмножество M}$${\ displaystyle (M, g)}$${\ displaystyle x, y \ in C}$${\ displaystyle C}$${\ displaystyle (M, g)}$

Примеры и отличия

• Эти рациональные числа с обычной формой расстояния метрический выпуклым подмножеством , что не является выпуклым.${\ Displaystyle \ mathbb {R}}$
• То же самое относится к тому, что также не является геодезически выпуклым, как риманово многообразие.${\ Displaystyle \ mathbb {R} ^ {2} \ обратная косая черта \ {0 \}}$
• Выпуклое подмножество евклидова пространства всегда метрически выпукло относительно метрики, индуцированной нормой . Обратный также относится к замкнутым подмножествам.

Кривизна кривых

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

В двумерной , то кривизна в непрерывно дифференцируемой кривой может быть рассмотрен в точке по отношению к зрителю: ${\ displaystyle x_ {0}}$

• Если соседние точки находятся в одной касательной - полуплоскости, что и у зрителя, значит, она там для него вогнутая .${\ displaystyle x_ {0}}$
• Если вокруг есть среда , так что все точки от нее лежат в другой касательной полуплоскости, то кривая в изогнута выпукло для наблюдателя .${\ displaystyle x_ {0}}$${\ displaystyle x_ {0}}$

Углы называются выпуклыми, если все внутренние углы составляют 180 ° или меньше.

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

Классические результаты над выпуклыми множествами (выборка)

• Неравенство Бибербаха
• Отборочное предложение Бляшке
• Неравенство Брунна-Минковского
• Теорема Коши
• Формула многогранника Эйлера
• Теорема Хелли
• Теорема Юнга
• Лемма Какутани
• Теорема Минковского
• Теорема Минковского о точках сетки
• Теорема Пика
• Теорема радона
• Приговор о разделении

Смотри тоже

• Абсолютно выпуклый набор
• Метрика Гильберта
• Выпуклая функция
• Симплекс (математика)
• Обобщенная выпуклость

литература

• Томми Боннесен , Вернер Феннель : теория выпуклых тел . Исправленная перепечатка. Springer-Verlag , Берлин (среди прочего) 1974, ISBN 3-540-06234-3 . 
• Арне Бронстед: Введение в выпуклые многогранники . Springer-Verlag, Нью-Йорк (среди прочего) 1983, ISBN 0-387-90722-X . 
• Леонард М. Блюменталь : теория и приложения дистанционной геометрии (=  Chelsea Scientific Books ). 2-е издание. Chelsea Publishing Company , Бронкс, Нью-Йорк 1970, ISBN 0-8284-0242-6 . 
• WA Coppel: Основы выпуклой геометрии . Издательство Кембриджского университета , Кембридж 1998, ISBN 0-521-63970-0 . 
• Kazimierz Goebel , William A. Kirk : Topics in Metric Fixed Point Theory (=  Кембриджские исследования по высшей математике . Том 28 ). Издательство Кембриджского университета , Кембридж 1990, ISBN 0-521-38289-0 . 
• Питер М. Грубер: Выпуклая и дискретная геометрия . Springer-Verlag, Берлин (среди прочего) 2007, ISBN 978-3-540-71132-2 . 
• Исаак М. Яглом и В. Г. Болтянский : Выпуклые фигуры . Издательство German Science Publishing , Берлин, 1956. 
• Отто Кернер, Джозеф Маурер, Ютта Стеффенс, Томас Тоде, Рудольф Фоллер: Vieweg Mathematik Lexikon . Vieweg Verlag , Брауншвейг (среди прочего) 1988, ISBN 3-528-06308-4 , стр. 159-160 . 
• Виктор Л. Клее (Ред.): Выпуклость . Труды седьмого симпозиума по чистой математике Американского математического общества, проходившего в Вашингтонском университете, Сиэтл, Вашингтон, 13-15 июня 1961 года. Американское математическое общество , Провиденс, Род-Айленд, 1963. 
• Стивен Р. Лэй: Выпуклые множества и их приложения . John Wiley & Sons , Нью-Йорк (и др.) 1982, ISBN 0-471-09584-2 . 
• Курт Лейхтвайс: Выпуклые множества . Springer-Verlag, Берлин [а. а.] 1980, ISBN 3-540-09071-1 . 
• Юрг Т. Марти: Выпуклый анализ . Биркхойзер , Базель (среди прочего) 1977, ISBN 3-7643-0839-7 . 
• Вилли Ринов : Внутренняя геометрия метрических пространств (=  Основные учения математических наук в индивидуальных представлениях с особым учетом областей применения . Том 105 ). Springer Verlag , Берлин, Геттинген, Гейдельберг 1961. 
• Фредерик А. Валентайн : Выпуклые величины (=  карманные книжки университета BI . 402 / 402a). Библиографический институт , Мангейм, 1968 г. 

веб ссылки

• Выпуклый набор . В: PlanetMath . (Английский)
• Выпуклое множество в энциклопедии математики

Индивидуальные доказательства

1. ^ Роберт Платон: Компактная вычислительная математика . Springer, 2013, ISBN 978-3-322-93922-7 , стр. 365 . 
2. ↑ Юрг Т. Марти: Выпуклый анализ . Springer, 2013, ISBN 978-3-0348-5910-3 , стр. 108 . 
3. ^ Василий И. Истратеску: строгая выпуклость и сложная строгая выпуклость, теория и приложения , Taylor & Francis Inc. (1983), ISBN 0-8247-1796-1 , предложение 2.11.20