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

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

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

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

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

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

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

Определения

Пусть $A$ — аффинное или векторное пространство над полем вещественных чисел $\mathbb {R}$.

Множество $K\subset A$ называется выпуклым, если вместе с любыми двумя точками $x,\;y\in K$ множеству $K$ принадлежат все точки отрезка $xy$, соединяющего в пространстве $A$ точки $x$ и $y$. Этот отрезок можно представить как

$\bigcup \limits _{t\in [0;\;1]}\{x+t\cdot {\overrightarrow {xy}}\}.$

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

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

Примеры

• Выпуклые подмножества множества $\mathbb {R}$ (множество вещественных чисел) представляют собой промежутки из $\mathbb {R}$.
• Примерами выпуклых подмножеств в двумерном евклидовом пространстве ($\mathbb {R} ^{2}$) являются правильные многоугольники.
• Примерами выпуклых подмножеств в трёхмерном евклидовом пространстве ($\mathbb {R} ^{3}$) являются архимедовы тела и правильные многогранники.
• Тела Кепплера — Пуансо (правильные звездообразные многогранники) являются примерами невыпуклых множеств.

Свойства

• Пустое множество и все пространство являются выпуклыми множествами. Поскольку пустое пространство и все пространство являются также и замкнутыми множествами, то они также являются замкнутыми выпуклыми множествами.
• Совокупность всех выпуклых множеств линейного пространства по отношению порядка образованного отношением включения является частично упорядоченным множеством с минимальным элементом, являющимся пустым множеством и максимальным элементом равным всему пространству. Такое же утверждение справедливо и для совокупности замкнутых выпуклых множеств.
• Выпуклое множество в топологическом линейном пространстве является связным и линейно связным, гомотопически эквивалентным точке.
• В терминах связности, выпуклое множество можно определить так: множество выпукло, если его пересечение с любой (вещественной) прямой связно.
• Пусть $K$ — выпуклое множество в линейном пространстве. Тогда для любых элементов $u_{1},\;u_{2},\;\ldots ,\;u_{r}$ принадлежащих $K$ и для всех неотрицательных $\lambda _{1},\;\lambda _{2},\;\ldots ,\;\lambda _{r}$, таких что $\lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1$, вектор

  $w=\sum _{k=1}^{r}\lambda _{k}u_{k}$

принадлежит $K$.

Вектор $w$ называется выпуклой комбинацией элементов $u_{1},\;u_{2},\;\ldots ,\;u_{r}$.

• Пересечение любой совокупности выпуклых множеств является выпуклым множеством. Поскольку операция пересечения обладает также свойствами ассоциативности и коммутативности, совокупность выпуклых множеств по операции пересечения образует коммутативную полугруппу. Эта полугруппа содержит единицу, равную всему пространству. Таким образом совокупность выпуклых множеств является моноидом по операции пересечения.
• Из замкнутости семейства выпуклых множеств по операции пересечения следует, что для любого подмножества $A$ линейного пространства существует наименьшее выпуклое множество, его содержащее. Это множество является пересечением всех выпуклых множеств, содержащих $A$, и называется выпуклой оболочкой множества $A$. Обозначается $coA$, $co(A)$, а также $\operatorname {Conv} A$.
  • Выпуклая оболочка выпуклого множества совпадает с самим множеством.
  • Выпуклая оболочка замкнутого множества является замкнутым (и выпуклым) множеством.
  • Выпуклая оболочка множества $K$ совпадает с множеством всех выпуклых линейных комбинаций векторов $K$, $u_{1},\;u_{2},\;\ldots ,\;u_{r}\in K$:

  $w=\sum _{k=1}^{r}\lambda _{k}u_{k}$, где $\lambda _{1},\;\lambda _{2},\;\ldots ,\;\lambda _{r}$ неотрицательные числа, такие что $\lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1$.

  • Любой вектор $X\in \operatorname {Conv} K$, где $K$ — подмножество $n$ - мерного линейного пространства $E^{n}$, может быть представлен в виде выпуклой комбинации не более чем $n+1$ векторов множества $K$. Это утверждение называется теоремой Каратеодори о выпуклой оболочке.
• Пусть $\Omega \subset E^{n}$ — некоторое замкнутое выпуклое множество. Тогда найдётся точка $X^{*}\in \Omega$ такая, что для всех $X\in \Omega$ выполняется

$(X,X^{*})\geqslant (X^{*},X^{*})$.

• Для произвольного замкнутого выпуклого множества $C$ и не принадлежащей ему точки $P$ существует гиперплоскость, разделяющая $C$ и $P$. Это утверждение называется теоремой об отделимости, а также теоремой об опорной гиперплоскости. Теорема об опорной гиперплоскости является частным случаем теоремы Хана — Банаха функционального анализа.
• Из теоремы об опорной гиперплоскости следует, что для выпуклого замкнутого множества $C$ и находящейся вне множества $C$ точки $P$ существует замкнутое полупространство (множеств точек в пространстве, лежащих с одной стороны гиперплоскости, включая также саму гиперплоскость) $H$, включающее $C$ и не содержащее $P$. Из этого следует, что все замкнутые выпуклые множества могут быть образованы пересечениями замкнутых полупространств.
• Теорема Хелли: Предположим, что в конечном семействе выпуклых подмножеств $\mathbb {R} ^{d}$, пересечение любых $d+1$ из них непусто. Тогда пересечение всех подмножеств из этого семейства непусто.
• Любое выпуклое множество единичной площади в $\mathbb {R} ^{2}$ можно целиком заключить в некоторый треугольник площади 2.
• Теорема Крейна — Мильмана. Выпуклый компакт $K$ в локально выпуклом пространстве $L$ совпадает с замыканием выпуклой оболочки множества своих крайних точек $E(K)$.
• Замкнутое множество $K$ евклидова пространсва $\mathbb {E} ^{d}$ является выпуклым тогда и только тогда, когда для любой точки $x\in \mathbb {E} ^{d}$ найдётся единственная ближайшая к ней точка $x^{*}\in K$.
  • В этом случае проекция $\mathbb {E} ^{d}\to K$ определяемая как $x\mapsto x^{*}$ является коротким отображением; то есть

    $|x-y|\geqslant |x^{*}-y^{*}|$

для любых $x,y\in \mathbb {E} ^{d}$.

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

• Без каких-либо изменений определение верно и для аффинных пространств над произвольным расширением поля вещественных чисел.

Алгоритмы

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

См. также

• Выпуклая функция
• Выпуклое метрическое пространство
• Выпуклый анализ
• Звёздная область
• Лемма Шепли — Фолкмана

Литература

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