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

Перейти к навигацииПерейти к поиску
Выпуклое множество.
Невыпуклое множество.

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

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

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

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

Определения

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

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

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

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

Примеры

Свойства

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

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

Алгоритмы

Алгоритм Дикстры — нахождение точки из пересечения выпуклых множеств.

См. также

Литература

  • Яглом И. М., Болтянский В. Г. Выпуклые фигуры. — М.Л.: ГТТИ, 1951. — 343 с. — (Библиотека математического кружка, вып. 4).
  • Лейхтвейс, К. Выпуклые множества. — М.: Наука, 1985. — 336 с.
  • Половинкин Е. С., Балашов М. В.. Элементы выпуклого и сильно выпуклого анализа. — М.: ФИЗМАТЛИТ, 2004. — 416 с. — ISBN 5-9221-0499-3..
  • Тиморин В. А. Комбинаторика выпуклых многогранников. — М.: МЦНМО, 2002. — 16 с. — ISBN 5-94057-024-0..
  • Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. — Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1972. — 368 с.

Примечания

  1. 1 2 3 4 5 Демьянов, Малоземов, 1972.
  2. Weisstein, Eric W. Triangle Circumscribing (англ.) на сайте Wolfram MathWorld.