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

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

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

Выпуклая оболочка множества $X$ обычно обозначается $\mathrm{Conv}X$.

Пример

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

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

Свойства

• $X$ — выпуклое множество тогда и только тогда, когда $\mathrm{Conv}X=X$.
• Для произвольного подмножества линейного пространства $X$ существует единственная выпуклая оболочка $\mathrm{Conv}X$ — это пересечение всех выпуклых множеств, содержащих $X$.
  • При этом

    $\mathrm{Conv}X=\bigcup _{n=1}^{\mathrm{\infty }}\bigcup _{a_1,\dots ,a_n\in X}\bigcup _{{\lambda }_1+\dots +{\lambda }_n=1}{\lambda }_1{a}_1+\dots +{\lambda }_n{a}_n,{\lambda }_i\ge 0$

  • Более того, если размерность пространства равна $N$ то верна следующая теорема Каратеодори:

    $\mathrm{Conv}X=\bigcup _{a_1,\dots ,a_{N+1}\in X}\bigcup _{{\lambda }_1+\dots +{\lambda }_{N+1}=1}{\lambda }_1{a}_1+\dots +{\lambda }_{N+1}{a}_{N+1},{\lambda }_i\ge 0$

• Выпуклой оболочкой конечного набора точек на плоскости является выпуклый плоский многоугольник (в вырожденных случаях — отрезок или точка), причём его вершины являются подмножеством исходного набора точек. Аналогичный факт верен и для конечного набора точек во многомерном пространстве.
• Выпуклая оболочка $X$ равна пересечению всех полупространств, содержащих $X$.
• Теорема Крейна — Мильмана. Выпуклый компакт $K$ в локально выпуклом пространстве $L$ совпадает с замыканием выпуклой оболочки множества своих крайних точек $E(K)$

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

Выпуклой оболочкой функции f называют такую функцию $\mathrm{Conv}f$, что

$\mathrm{epi}\mathrm{Conv}f=\mathrm{Conv}\mathrm{epi}f$,

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

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

$f^{**}=\overline{\mathrm{Conv}}f$

$\overline{\mathrm{Conv}}f$ — выпуклое замыкание f, то есть функция, надграфик которой является замыканием надграфика f.

Сложность построения

Из теоремы о верхней границе вытекает, что выпуклая оболочка множества из $n$ точек в пространстве размерности $d$ может быть построена алгоритмом сложности $O(n\log n)$ для двумерного и трёхмерного случая и алгоритмом сложности $O(n^{\lfloor d/2\rfloor })$ в пространствах более высокой размерности.

См. также

• Алгоритм быстрой оболочки
• Алгоритм Грэхема
• Алгоритм Джарвиса
• Алгоритм Киркпатрика
• Алгоритм Чена
• Выпуклость
• Лемма Шепли — Фолкмана
• Метод эластичной сети

Литература

• Половинкин Е. С, Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. — Шаблон:М: Физматлит, 2004. — 416 с. — ISBN 5-9221-0499-3.
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Source
• Г. Г. Магарил-Ильяев, В. М. Тихомиров. Выпуклый анализ и его приложения. Изд. 2-е, исправл. —М.: Едиториал УРСС. 2003. —176 с. —ISBN 5-354-0262-1.