Konvexní množiny
Definice \(\secT{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 \eqT{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 \(\secT{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í
Polyedr je mnohostěn v \(\R^n\). Dále ohraničený polyedr nazveme polytop.
Dále si rozeberme různé kombinace bodů
Definice \(\secT{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 \(\secT{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 \(\secT{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 \(\secT{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 \(\secT{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.