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

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

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

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

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

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

Определения

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

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

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

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

Примеры

Свойства

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

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

Алгоритмы

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

См. также

Литература


  • Лейхтвейс, К. Выпуклые множества. М.: Наука, 1985. — 336 с.
  • Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. — Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1972. — 368 с.

Примечания

  1. Демьянов, Малоземов, 1972.
  2. Weisstein, Eric W. Triangle Circumscribing (англ.) на сайте Wolfram MathWorld.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.