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

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

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

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

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

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

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

Определения [ править ]

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

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

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

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

Невыпуклый набор [ править ]

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

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

Свойства [ править ]

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

${\ Displaystyle \ сумма _ {к = 1} ^ {г} \ лямбда _ {к} и_ {к}}$

принадлежит S . Поскольку определение выпуклого множества относится к случаю r = 2 , это свойство характеризует выпуклые множества.

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

Перекрестки и союзы [ править ]

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

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

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

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

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

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

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

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

Диаграммы Бляшке-Сантало [ править ]

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

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

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

${\ Displaystyle г + р \ leq D}$

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

и можно представить в виде изображения функции г , который отображает выпуклое тело в R ² точки , заданной уравнением ( г / R , D / 2 R ). Образ этой функции известен как ( r , D , R ) диаграмма Блахке-Сантало. ^[12]

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

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

Другие свойства [ править ]

Пусть X - топологическое векторное пространство и выпукло. ${\ Displaystyle C \ substeq 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 . Оператор выпуклой оболочки Conv () обладает характеристическими свойствами оператора оболочки :

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

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

Conv ( S ) ∨ Conv ( T ) = Conv ( S  ∪  T ) = Conv (Conv ( S ) ∪ Conv ( T )) .

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

Дополнение Минковского [ править ]

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

S ₁  +  S ₂ = { x ₁  +  x ₂  : x ₁  ∈  S ₁ , x ₂  ∈  S ₂ } .

В более общем смысле, сумма Минковского конечного семейства (непустых) множеств S _n - это множество, образованное поэлементным сложением векторов

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

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

S  + {0} = S ;

в алгебраической терминологии {0} - это единичный элемент сложения Минковского (на совокупности непустых множеств). ^[13]

Выпуклые оболочки сумм Минковского [ править ]

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

Пусть S ₁ , S ₂ - подмножества реального векторного пространства, выпуклая оболочка их суммы Минковского - это сумма Минковского их выпуклых оболочек.

Conv ( S ₁  +  S ₂ ) = Conv ( S ₁ ) + Conv ( S ₂ ) .

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

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

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

Суммы Минковского выпуклых множеств [ править ]

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

Следующая знаменитая теорема, доказанная Дьедонне в 1966 году, дает достаточное условие замкнутости разности двух замкнутых выпуклых подмножеств. ^[17] Он использует концепцию конуса рецессии непустого выпуклого подмножества 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 - непустые, замкнутые и выпуклые подмножества локально выпуклого топологического векторного пространства, такое что является линейным подпространством. Если или B является локально компактным , то  -  B закрыт.${\displaystyle \operatorname {rec} A\cap \operatorname {rec} B}$

Обобщения и расширения для выпуклости [ править ]

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

Звездно-выпуклые (звездчатые) множества [ править ]

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

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

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

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

Неевклидова геометрия [ править ]

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

Топология заказа [ править ]

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

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

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

Выпуклые пространства [ править ]

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

Принимая во внимание множество Х , А выпуклость над X представляет собой набор 𝒞 подмножеств X , удовлетворяющих следующим аксиомам: ^{[8] [9] [20]}

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

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

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

См. Также [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

Найдите выпуклый набор в Викисловаре, бесплатном словаре.

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