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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

АлгоритмыПравить

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

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

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

  • Половинкин Е. С., Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. — М.: ФИЗМАТЛИТ, 2004. — 416 с. — ISBN 5-9221-0499-3..
  • Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. — Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1972. — 368 с.

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

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