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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Выпуклое множество.
Невыпуклое множество.

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

Выпуклые множества играют важную роль во многих оптимизационных задачах.[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.