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

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

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

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

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

Определения

Пусть $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$ . ^[1] Это утверждение называется теоремой Каратеодори о выпуклой оболочке.
Пусть $\Omega \subset E^{n}$ — некоторое замкнутое выпуклое множество. Тогда найдётся точка $X^{*}\in \Omega$ такая, что для всех $X\in \Omega$ выполняется

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

.^[1]

Для произвольного замкнутого выпуклого множества $C$ и не принадлежащей ему точки $P$ существует гиперплоскость, разделяющая $C$ и $P$ .^[1] Это утверждение называется теоремой об отделимости^[1], а также теоремой об опорной гиперплоскости. Теорема об опорной гиперплоскости является частным случаем теоремы Хана — Банаха функционального анализа.
Из теоремы об опорной гиперплоскости следует, что для выпуклого замкнутого множества $C$ и находящейся вне множества $C$ точки $P$ существует замкнутое полупространство (множеств точек в пространстве, лежащих с одной стороны гиперплоскости, включая также саму гиперплоскость) $H$ , включающее $C$ и не содержащее $P$ . Из этого следует, что все замкнутые выпуклые множества могут быть образованы пересечениями замкнутых полупространств.
Теорема Хелли: Предположим, что в конечном семействе выпуклых подмножеств $\mathbb {R} ^{d}$ , пересечение любых $d+1$ из них непусто. Тогда пересечение всех подмножеств из этого семейства непусто.
Любое выпуклое множество единичной площади в $\mathbb {R} ^{2}$ можно целиком заключить в некоторый треугольник площади 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 с.

Примечания

↑ ¹ ² ³ ⁴ ⁵ Демьянов, Малоземов, 1972.
↑ Weisstein, Eric W. Triangle Circumscribing (англ.) на сайте Wolfram MathWorld.

[_454cba1cbe251e80-1] ¹ ² ³ ⁴ ⁵ Демьянов, Малоземов, 1972.

[2] Weisstein, Eric W. Triangle Circumscribing (англ.) на сайте Wolfram MathWorld.

[1]

[2]