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

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

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

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

Визначення

• Іншими словами, множина $X\subset {ℝ}^n$ називається опуклою, якщо для точок $x_1,x_2\in X$, що задаються радіус-векторами ${\overrightarrow{r}}_1,{\overrightarrow{r}}_2$, точка:

$\alpha {\overrightarrow{r}}_1+(1-\alpha ){\overrightarrow{r}}_2\in X,\alpha \in [0,1].$

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

$[x_1,x_2]=\{x:x={\overrightarrow{r}}_1+\alpha ({\overrightarrow{r}}_2-{\overrightarrow{r}}_1),\alpha \in [0,1]\}$.

Приклади

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

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

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

$l_{{𝐱}_{0}h}=\{x\in {ℝ}^n:x=x_0+\alpha h,\alpha \in {ℝ}^n\}$;

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

$l_{𝐗0h}^{+}=\{x\in {ℝ}^n:x=x_0+\alpha h,\alpha ⩾0\}$;

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

${\mathrm{H}}_{p\beta }=\{x\in {ℝ}^n:(p,x)=\beta \}$;

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

${\mathrm{H}}_{p\beta }^{+}=\{x\in {ℝ}^n:(p,x)⩾\beta \}$,

${\mathrm{H}}_{p\beta }^{-}=\{x\in {ℝ}^n:(p,x)⩽\beta \}$.

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

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

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

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

Див. також

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

Література

• Шаблон:Книга.