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

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

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

Определения

Пусть A {displaystyle A} — аффинное или векторное пространство над полем вещественных чисел R {displaystyle mathbb {R} } .

Множество K ⊂ A {displaystyle Ksubset A} называется выпуклым, если вместе с любыми двумя точками x , y ∈ K {displaystyle x,;yin K} множеству K {displaystyle K} принадлежат все точки отрезка x y {displaystyle xy} , соединяющего в пространстве A {displaystyle A} точки x {displaystyle x} и y {displaystyle y} . Этот отрезок можно представить как

⋃ t ∈ [ 0 ; 1 ] { x + t ⋅ x y → } . {displaystyle igcup limits _{tin [0;;1]}{x+tcdot {overrightarrow {xy}}}.}

Связанные определения

Множество K {displaystyle K} векторного пространства V {displaystyle V} называется абсолютно выпуклым, если оно выпукло и уравновешенно.

Примеры

• Выпуклые подмножества множества R {displaystyle mathbb {R} } (множество вещественных чисел) представляют собой интервалы из R {displaystyle mathbb {R} } .
• Примерами выпуклых подмножеств в двумерном евклидовом пространстве ( R 2 {displaystyle mathbb {R} ^{2}} ) являются правильные многоугольники.
• Примерами выпуклых подмножеств в трёхмерном евклидовом пространстве ( R 3 {displaystyle mathbb {R} ^{3}} ) являются архимедовы тела и правильные многогранники.
• Тела Кепплера — Пуансо (правильные звездообразные многогранники) являются примерами невыпуклых множеств.

Свойства

• Пустое множество и все пространство являются выпуклыми множествами. Поскольку пустое пространство и все пространство являются также и замкнутыми множествами, то они также являются замкнутыми выпуклыми множествами.
• Совокупность всех выпуклых множеств линейного пространства по отношению порядка образованного отношением включения является частично упорядоченным множеством с минимальным элементом, являющимся пустым множеством и максимальным элементом равным всему пространству. Такое же утверждение справедливо и для совокупности замкнутых выпуклых множеств.
• Выпуклое множество в топологическом линейном пространстве является связным и линейно связным, гомотопически эквивалентным точке.
• В терминах связности, выпуклое множество можно определить так: множество выпукло, если его пересечение с любой (вещественной) прямой связно.
• Пусть K {displaystyle K} — выпуклое множество в линейном пространстве. Тогда для любых элементов u 1 , u 2 , … , u r {displaystyle u_{1},;u_{2},;ldots ,;u_{r}} принадлежащих K {displaystyle K} и для всех неотрицательных λ 1 , λ 2 , … , λ r {displaystyle lambda _{1},;lambda _{2},;ldots ,;lambda _{r}} , таких что λ 1 + λ 2 + … + λ r = 1 {displaystyle lambda _{1}+lambda _{2}+ldots +lambda _{r}=1} , вектор w = ∑ k = 1 r λ k u k {displaystyle w=sum _{k=1}^{r}lambda _{k}u_{k}}

принадлежит K {displaystyle K} . Вектор w {displaystyle w} называется выпуклой комбинацией элементов u 1 , u 2 , … , u r {displaystyle u_{1},;u_{2},;ldots ,;u_{r}} .

• Пересечение любой совокупности выпуклых множеств является выпуклым множеством. Поскольку операция пересечения обладает также свойствами ассоциативности и коммутативности, совокупность выпуклых множеств по операции пересечения образует коммутативную полугруппу. Эта полугруппа содержит единицу, равную всему пространству. Таким образом совокупность выпуклых множеств является моноидом по операции пересечения.
• Из замкнутости семейства выпуклых множеств по операции пересечения следует, что для любого подмножества A {displaystyle A} линейного пространства существует наименьшее выпуклое множество, его содержащее. Это множество является пересечением всех выпуклых множеств, содержащих A {displaystyle A} , и называется выпуклой оболочкой множества A {displaystyle A} . Обозначается c o A {displaystyle coA} , c o ( A ) {displaystyle co(A)} , а также Conv ⁡ A {displaystyle operatorname {Conv} A} .
  • Выпуклая оболочка выпуклого множества совпадает с самим множеством.
  • Выпуклая оболочка замкнутого множества является замкнутым (и выпуклым) множеством.
  • Выпуклая оболочка множества K {displaystyle K} совпадает с множеством всех выпуклых линейных комбинаций векторов K {displaystyle K} , u 1 , u 2 , … , u r ∈ K {displaystyle u_{1},;u_{2},;ldots ,;u_{r}in K} :
  w = ∑ k = 1 r λ k u k {displaystyle w=sum _{k=1}^{r}lambda _{k}u_{k}} , где λ 1 , λ 2 , … , λ r {displaystyle lambda _{1},;lambda _{2},;ldots ,;lambda _{r}} неотрицательные числа, такие что λ 1 + λ 2 + … + λ r = 1 {displaystyle lambda _{1}+lambda _{2}+ldots +lambda _{r}=1} .
  • Любой вектор X ∈ Conv ⁡ K {displaystyle Xin operatorname {Conv} K} , где K {displaystyle K} — подмножество n {displaystyle n} - мерного линейного пространства E n {displaystyle E^{n}} , может быть представлен в виде выпуклой комбинации не более чем n + 1 {displaystyle n+1} векторов множества K {displaystyle K} . Это утверждение называется теоремой Каратеодори о выпуклой оболочке.
• Пусть Ω ⊂ E n {displaystyle Omega subset E^{n}} — некоторое замкнутое выпуклое множество. Тогда найдётся точка X ∗ ∈ Ω {displaystyle X^{*}in Omega } такая, что для всех X ∈ Ω {displaystyle Xin Omega } выполняется

( X , X ∗ ) ⩾ ( X ∗ , X ∗ ) {displaystyle (X,X^{*})geqslant (X^{*},X^{*})} .

• Для произвольного замкнутого выпуклого множества C {displaystyle C} и не принадлежащей ему точки P {displaystyle P} существует гиперплоскость, разделяющая C {displaystyle C} и P {displaystyle P} . Это утверждение называется теоремой об отделимости, а также теоремой об опорной гиперплоскости. Теорема об опорной гиперплоскости является частным случаем теоремы Хана — Банаха функционального анализа.
• Из теоремы об опорной гиперплоскости следует, что для выпуклого замкнутого множества C {displaystyle C} и находящейся вне множества C {displaystyle C} точки P {displaystyle P} существует замкнутое полупространство (множеств точек в пространстве, лежащих с одной стороны гиперплоскости, включая также саму гиперплоскость) H {displaystyle H} , включающее C {displaystyle C} и не содержащее P {displaystyle P} . Из этого следует, что все замкнутые выпуклые множества могут быть образованы пересечениями замкнутых полупространств.
• Теорема Хелли: Предположим, что в конечном семействе выпуклых подмножеств R d {displaystyle mathbb {R} ^{d}} , пересечение любых d + 1 {displaystyle d+1} из них непусто. Тогда пересечение всех подмножеств из этого семейства непусто.
• Любое выпуклое множество единичной площади в R 2 {displaystyle mathbb {R} ^{2}} можно целиком заключить в некоторый треугольник площади 2.

Вариации и обобщения

• Без каких-либо изменений определение верно и для аффинных пространств над произвольным расширением поля вещественных чисел.