Выпуклая оболочка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Выпуклой оболочкой множества называется наименьшее выпуклое множество, содержащее . «Наименьшее множество» здесь означает наименьший элемент по отношению к вложению множеств, то есть такое выпуклое множество, содержащее данную фигуру, что оно содержится в любом другом выпуклом множестве, содержащем данную фигуру.

Обычно выпуклая оболочка определяется для подмножеств векторного пространства над вещественными числами (в частности в евклидовом пространстве) и на соответствующих аффинных пространствах.

Выпуклая оболочка множества обычно обозначается .

Пример[править | править вики-текст]

Выпуклая оболочка: пример с лассо

Представьте себе доску, в которую вбито — но не по самую шляпку — много гвоздей. Возьмите верёвку, свяжите на ней скользящую петлю (лассо) и набросьте её на доску, а потом затяните. Верёвка окружает все гвозди, но касается она только некоторых, самых внешних. Те гвозди, которых она касается, составляют выпуклую оболочку для всей группы гвоздей[1].

Свойства[править | править вики-текст]

  •  — выпуклое множество тогда и только тогда, когда .
  • Для произвольного подмножества линейного пространства существует единственная выпуклая оболочка  — это пересечение всех выпуклых множеств, содержащих .
    • При этом
    • Более того, если размерность пространства равна то верна следующая теорема Каратеодори:
  • Выпуклой оболочкой конечного набора точек на плоскости является выпуклый плоский многоугольник (в вырожденных случаях — отрезок или точка), причём его вершины являются подмножеством исходного набора точек. Аналогичный факт верен и для конечного набора точек во многомерном пространстве.
  • Выпуклая оболочка равна пересечению всех полупространств, содержащих .

Вариации и обобщения[править | править вики-текст]

Выпуклой оболочкой функции f называют такую функцию , что

,

где epi f — надграфик функции f.

Стоит отметить связь понятия выпуклой оболочки функции с преобразованием Лежандра невыпуклых функций. Пусть f * — преобразование Лежандра функции f. Тогда если —собственная функция (принимает конечные значения на непустом множестве), то


 — выпуклое замыкание f, то есть функция, надграфик которой является замыканием надграфика f.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Даниэль Хэльпер, курс «Построение алгоритмов», Хайфский университет.