Опукла множина

Опукла множина виглядає як деформоване коло. Чорний відрізок з'єднує точки x та y і розташований повністю в (зеленій) множині. Оскільки це виконується для будь-яких точок x та y множини, то множина буде опуклою.

Приклад неопуклої множини. Так як червона частина (чорне та червоне) відрізку, що з'єднує точки x та y, розташована за межами (зеленої) множини, то множина не буде опуклою.

Опуклою множиною в евклідовому або афінному просторі називається така множина, яка разом з довільними двома точками, що належать множині, має у собі відрізок, що їх з'єднує.

Визначення

• Іншими словами, множина $X\subset \mathbb {R} ^{n}$ називається опуклою, якщо для точок $x_{1},x_{2}\in X$, що задаються радіус-векторами ${\vec {r}}_{1},{\vec {r}}_{2}$, точка:

$\alpha {\vec {r}}_{1}+(1-\alpha ){\vec {r}}_{2}\in X,\,\alpha \in [0,1].$

• Тобто, множина $X$ разом з будь-якими двома точками $\ x_{1},x_{2}$, які належать цій множині, містить відрізок, який їх з'єднує:

$[x_{1},x_{2}]=\left\{x\colon \,x={\vec {r}}_{1}+\alpha ({\vec {r}}_{2}-{\vec {r}}_{1}),\,\alpha \in [0,1]\right\}$.

Приклади

У просторі $\mathbb {R} ^{1}$ опуклими множинами будуть точка, відрізок, інтервал, промінь, пряма.

У просторі $\mathbb {R} ^{n}$ опуклим буде сам простір, будь-який його лінійний підпростір, куля, опуклі множини просторів меншої вимірності. Також, опуклими будуть такі множини:

• пряма $l_{x_{0}h}$, що проходить через точку $x_{0}$ в напрямку вектора $h$:

$l_{\mathbf {x} _{0}h}=\left\{x\in \mathbb {R} ^{n}:\,x=x_{0}+\alpha h,\alpha \in \mathbb {R} ^{n}\right\}$;

• промінь $l_{x_{0}h}+$, який виходить із точки $x_{0}$ в напрямку вектора $h$:

$l_{\mathbf {X} 0h}^{+}=\left\{x\in \mathbb {R} ^{n}:\,x=x_{0}+\alpha h,\,\alpha \geqslant 0\right\}$;

• гіперплощина H_pβ з нормаллю p:

$\mathrm {H} _{p\beta }=\left\{x\in \mathbb {R} ^{n}:\,(p,x)=\beta \right\}$;

• півпростори на які гіперплощина поділяє простір:

$\mathrm {H} _{p\beta }^{+}=\left\{x\in \mathbb {R} ^{n}:\,(p,x)\geqslant \beta \right\}$,

$\mathrm {H} _{p\beta }^{-}=\left\{x\in \mathbb {R} ^{n}:\,(p,x)\leqslant \beta \right\}$.

Всі перелічені множини (крім кулі) є частковими випадками опуклої множини поліедру.

Чотирикутник на площині може бути опуклим і неопуклим.

Властивості опуклих множин

• Перетин опуклих множин є опуклим.
• Лінійна комбінація точок опуклої множини опукла.
• Опукла множина містить будь-яку опуклу комбінацію своїх точок.
• Будь-яку точку n-вимірного евклідового простору з опуклої оболонки множини можна представити як опуклу комбінацію не більш ніж n+1 точок цієї множини.

Див. також

• Задача опуклого програмування
• Опукла оболонка
• Опуклий політоп
• Опукла поверхня
• Лема Шеплі — Фолкмана

Література

• Половинкин Е. С., Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. — М. : ФИЗМАТЛИТ. — 416 с. — ISBN 5-9221-0499-3..