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

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

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

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

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

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

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

 

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

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

ПримерыПравить

СвойстваПравить

  • Пустое множество и все пространство являются выпуклыми множествами. Поскольку пустое пространство и все пространство являются также и замкнутыми множествами, то они также являются замкнутыми выпуклыми множествами.
  • Совокупность всех выпуклых множеств линейного пространства по отношению порядка образованного отношением включения является частично упорядоченным множеством с минимальным элементом, являющимся пустым множеством и максимальным элементом равным всему пространству. Такое же утверждение справедливо и для совокупности замкнутых выпуклых множеств.
  • Выпуклое множество в топологическом линейном пространстве является связным и линейно связным, гомотопически эквивалентным точке.
  • В терминах связности, выпуклое множество можно определить так: множество выпукло, если его пересечение с любой (вещественной) прямой связно.
  • Пусть   — выпуклое множество в линейном пространстве. Тогда для любых элементов   принадлежащих   и для всех неотрицательных  , таких что  , вектор
     
принадлежит  .
Вектор   называется выпуклой комбинацией элементов  .
  • Пересечение любой совокупности выпуклых множеств является выпуклым множеством. Поскольку операция пересечения обладает также свойствами ассоциативности и коммутативности, совокупность выпуклых множеств по операции пересечения образует коммутативную полугруппу. Эта полугруппа содержит единицу, равную всему пространству. Таким образом совокупность выпуклых множеств является моноидом по операции пересечения.
  • Из замкнутости семейства выпуклых множеств по операции пересечения следует, что для любого подмножества   линейного пространства существует наименьшее выпуклое множество, его содержащее. Это множество является пересечением всех выпуклых множеств, содержащих  , и называется выпуклой оболочкой множества  . Обозначается  ,  , а также  .
    • Выпуклая оболочка выпуклого множества совпадает с самим множеством.
    • Выпуклая оболочка замкнутого множества является замкнутым (и выпуклым) множеством.
    • Выпуклая оболочка множества   совпадает с множеством всех выпуклых линейных комбинаций векторов  ,  :
     , где   неотрицательные числа, такие что  .
    • Любой вектор  , где   — подмножество   - мерного линейного пространства  , может быть представлен в виде выпуклой комбинации не более чем   векторов множества  . [1] Это утверждение называется теоремой Каратеодори о выпуклой оболочке.
  • Пусть   — некоторое замкнутое выпуклое множество. Тогда найдётся точка   такая, что для всех   выполняется
 .[1]
  • Для произвольного замкнутого выпуклого множества   и не принадлежащей ему точки   существует гиперплоскость, разделяющая   и  .[1] Это утверждение называется теоремой об отделимости[1], а также теоремой об опорной гиперплоскости. Теорема об опорной гиперплоскости является частным случаем теоремы Хана — Банаха функционального анализа.
  • Из теоремы об опорной гиперплоскости следует, что для выпуклого замкнутого множества   и находящейся вне множества   точки   существует замкнутое полупространство (множеств точек в пространстве, лежащих с одной стороны гиперплоскости, включая также саму гиперплоскость)  , включающее   и не содержащее  . Из этого следует, что все замкнутые выпуклые множества могут быть образованы пересечениями замкнутых полупространств.
  • Теорема Хелли: Предположим, что в конечном семействе выпуклых подмножеств  , пересечение любых   из них непусто. Тогда пересечение всех подмножеств из этого семейства непусто.
  • Любое выпуклое множество единичной площади в   можно целиком заключить в некоторый треугольник площади 2[2].

Вариации и обобщенияПравить

См. такжеПравить

ЛитератураПравить

  • Половинкин Е. С., Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. — М.: ФИЗМАТЛИТ, 2004. — 416 с. — ISBN 5-9221-0499-3..

ПримечанияПравить

  1. 1 2 3 4 5 Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.:, Главная редакция физико-математической литературы изд-ва «Наука», 1972, 368 стр.
  2. Weisstein, Eric W. Triangle Circumscribing (англ.) на сайте Wolfram MathWorld.