Konvexní množiny

$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\tagged#1{(\text{#1})} \xdef\tagged*#1{\text{#1}} \xdef\tagEqHere#1#2{\href{#2\#eq-#1}{(\text{#1})}} \xdef\tagDeHere#1#2{\href{#2\#de-#1}{\text{#1}}} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\hess#1{\nabla^2\, #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} \xdef\iter#1{^{[#1]}} $$

Definice $\D{1.1}$ (Konvexní množina)

Nechť $X \subseteq \R^n$. Množina $X$ se nazývá konvexní, jestliže pro všechna $x_1, x_2 \in X$ a pro každé $\l \in [0,1]$ platí $$ \l x_1 + (1 - \l) x_2 \in X \tag{KM} $$

Speciálně prázdnou množinu $\emptyset$ považujeme za konvexní

Operace nad konvexními množinami

Mějme $X_i, i \in I$ konvexní množiny. Potom

• jejich sjednocení $\bigcap_{i \in I} X_i$ je konvexní množina
• jejich součet $\a_1 X_1 + \dots + \a_m X_m = \brackets{x \in \R^n \mid x = \displaystyle \sum_{i = 1}^m \a_i x_i \text{ pro nějaká } x_i \in X_i}$ je opět konvexní

Vlastnosti konvexních množin

Definice $\D{2.1.3}$ (Speciální množiny)

Množina $X \subseteq \R^n$ se nazývá

• kužel, jestliže pro každé $x \in X$ a pro každé $\l \in [0, \infty)$ je také $\l x \in X$

• konvexní kužel, jestliže je množina $X$ konvexní a současně kuželem

• afinní, jestliže pro každé $x_1, x_2 \in X$ a pro každé $\l \in \R$ platí $$ \l x_1 + (1 - \l)x_2 \in X $$

Polyedr je mnohostěn v $\R^n$. Dále ohraničený polyedr nazveme polytop.

Dále si rozeberme různé kombinace bodů

Definice $\D{2.1.4}$ (Lineární kombinace)

Nechť $x_1, \dots, x_m \in \R^n$. Lineární kombinace $\l_1 x_1 + \dots + \l_m x_m$ se nazývá

• konvexní, jestliže $\l_1, \dots, \l_m \geq 0$ a $\sum_{i = 1}^m \l_i = 1$
• nezáporná, jestliže $\l_1, \dots, \l_m \geq 0$
• afinní, jestliže $\sum_{i = 1}^m \l_i = 1$.

Tedy jistě platí

• Množina obsahující všechny linearní kombinace libovolných dvou svých bodů (tj. s libovolnými dvěma body obsahuje i přímku procházející těmito body a počátek) je vektorový (lineární) prostor
• Množina obsahující všechny afinní kombinace libovolných dvou svých bodů (tj. s libovolnými dvěma body obsahuje i přímku procházející těmito body) je afinní
• Množina obsahující všechny nezáporné kombinace libovolných dvou svých bodů (tj. s libovolnými dvěma body obsahuje i celou výšeč určenou polopřímkami vycházejícími z počátku a procházejícími těmito body) je konvexní kužel
• Množina obsahující všechny konvexní kombinace dvou libovolných svých bodů (tj. s libovolnámi dvěma body obsahuje i celou úsečku je spojující) je konvexní

Definice $\D{2.1.6}$ (Obaly)

Nechť $X \subseteq \R^n$

• průnik všech konvexních množin obsahujících množinu $X$ se nazývá konvexní obal množiny $X$ a značí se $\conv X$.
• průnik všech konvexních kuželů obsahujících množinu $X$ se nazývá kónický obal množiny $X$ a značí se $\cone X$.
• průnik všech afinních množin obsahujících množin $X$ se nazyvá afinní obal množiny $X$ a značí se $\aff X$. Jeho zaměření se nazývá lineární obal množiny $X$ a značí se $\lin X$. Dimenze afinního obalu množiny $X$ se značí $\dim X$ a klademe $\dim X := \dim {\lin X}$.

Všimněme si, že $\span X = \{$ $\forall$ lineární kombinace prvků z $X$ $\}$,
ale $\lin X = \span \brackets{x_2 - x_1, x_3 - x_1, \dots, x_m - x_1}$. (pro $X = \set{x_1, \dots, x_m}$) Viz obrázek z přednášky

Jinak řečeno, konvexní obal je nejmenší konvexní množina obsahující $X$ ve smyslu množinové inkluze.
Kónický obal je nejmenší konvexní kužel obsahující $X$ atd..

Jako simplex definujeme konvexní obal $n+1$ afinně nezávislých bodů $v_1, \dots, v_{n+1} \in \R^m$, kde $m \geq n$. Pod pojmem afinně nezávislé body rozumíme, že vektory $$ v_2 - v_1, v_3 - v_1, \dots, v_{n+1} - v_1 $$ jsou lineárně nezávislé.

Věta $\D{2.1.7}$

Nechť $X \subseteq \R^n$. Pak platí

• $\conv X = \brackets{x \mid x = \displaystyle\sum_{i = 1}^m \l_i x_i, \text{ kde } m \in \N \text{ je libovolné}, x_1, \dots, x_m \in X, \l_1, \dots, \l_m \geq 0, \sum_{i = 1}^m \l_i = 1}$
• $\cone X = \brackets{x \mid x = \displaystyle\sum_{i = 1}^m \l_i x_i, \text{ kde } m \in \N \text{ je libovolné}, x_1, \dots, x_m \in X, \l_1, \dots, \l_m \geq 0}$
• $\aff X = \brackets{x \mid x = \displaystyle\sum_{i = 1}^m \l_i x_i, \text{ kde } m \in \N \text{ je libovolné}, x_1, \dots, x_m \in X, \l_1, \dots, \l_m \in \R, \sum_{i = 1}^m \l_i = 1}$

Libovolný bod x v konvexní kuželu v $\R^n$ lze vyjádřit pomocí nezáporné kombinace $n$ bodů

Věta $\D{2.1.9}$ (Caratheódoryho)

Nechť $X \subseteq \R^n$. Každý bod konvexního obalu $\conv X$ může být vyjádřen jako konvexní kombinace nejvýše $n+1$ prvků množiny $X$, tj. pro $x \in X$ existují $x_1, \dots, x_{n+1} \in X$ a $\l_1, \dots, \l_{n+1} \geq 0$ splňující $\sum_{i = 1}^{n+1} \l_i = 1$ taková, že $$ x = \l_1 x_1 + \dots + \l_{n+1} x_{n+1} $$

POZOR: Univerzální konvexní báze (stejná pro všechny $x \in \conv X$) konvexního obalu $\conv X$ nemusí existovat!

Lze ukázat, že pokud $X \subseteq \R^n$ je kompaktní množina, pak $\conv X$ je také kompaktní.

To stejné neplatí o uzavřenosti.

Zobecnění vnitřku množiny

Definice $\D{2.1.11}$ (Relativně vnitřní bod)

Nechť $X \subseteq \R^n$. Bod $x^* \in X$ se nazývá relativně vnitřním bodem množiny $X$, jestliže existuje okolí $\O(x^* )$ bodu $x^* $ takové, že $$ \O(x^* ) \cap \aff X \subseteq X $$ Množinu všech relativně vnitřních bodů nazýváme relativním vnitřkem množiny $X$ a značime $\ri X$.
Množina $\rd X := \overline X \setminus \ri X$ se nazývá relativní hranice množiny $X$.

Jistě platí $\interior X \subseteq \ri X$
a také $\ri X \subseteq X \subseteq \overline X \subseteq \aff X$

Platí $\overline {\ri X} = \bar X$, tj. relativní vnitřek je dost velký na vygenerování uzávěru.