# Konvexní množiny <div style="visibility:hidden;height:0;overflow:hidden;margin:0;padding:0"> ```math \newcommand{\LetThereBe}[2]{\newcommand{#1}{#2}} \newcommand{\letThereBe}[3]{\newcommand{#1}[#2]{#3}} \letThereBe{\addTag}{2}{\cssId{#1-#2}{\tag{#2}}} \letThereBe{\addLabel}{2}{\cssId{#1-#2}{\text{#2}}} \letThereBe{\refTag}{2}{\href{###1-#2}{(\text{#2})}} \letThereBe{\eqT}{1}{\addTag{eq}{#1}}\letThereBe{\secT}{1}{\addLabel{sec}{#1}} \letThereBe{\eqRef}{1}{\refTag{eq}{#1}} \letThereBe{\secRef}{1}{\refTag{sec}{#1}} \LetThereBe{\R}{\mathbb{R}} \LetThereBe{\N}{\mathbb{N}} \letThereBe{\rcases}{1}{\left.\begin{align}#1\end{align}\right\}} \letThereBe{\rcasesAt}{2}{\left.\begin{alignat}{#1}#2\end{alignat}\right\}} \letThereBe{\lcases}{1}{\begin{cases}#1\end{cases}} \letThereBe{\lcasesAt}{2}{\left\{\begin{alignat}{#1}#2\end{alignat}\right.} \letThereBe{\scal}{2}{\langle #1, #2 \rangle} \letThereBe{\norm}{1}{\left\lVert #1 \right\rVert} \LetThereBe{\dist}{\rho} \LetThereBe{\and}{\&}\letThereBe{\brackets}{1}{\left\{ #1 \right\}} \letThereBe{\parc}{2}{\frac {\partial #1}{\partial #2}} \letThereBe{\mtr}{1}{\begin{pmatrix}#1\end{pmatrix}} \letThereBe{\bm}{1}{\boldsymbol{#1}} \letThereBe{\mcal}{1}{\mathcal{#1}} \letThereBe{\vv}{1}{\mathbf{#1}}\letThereBe{\vvp}{1}{\pmb{#1}} \LetThereBe{\ve}{\varepsilon} \LetThereBe{\l}{\lambda} \LetThereBe{\th}{\vartheta} \LetThereBe{\a}{\alpha} \letThereBe{\conv}{1}{\mathrm{conv}\, #1} \letThereBe{\cone}{1}{\mathrm{cone}\, #1} \letThereBe{\aff}{1}{\mathrm{aff}\, #1} \letThereBe{\lin}{1}{\mathrm{Lin}\, #1} \letThereBe{\span}{1}{\mathrm{span}\, #1} \LetThereBe{\O}{\mathcal O} \letThereBe{\ri}{1}{\mathrm{ri}\, #1} \letThereBe{\rd}{1}{\mathrm{r}\partial\, #1} \letThereBe{\interior}{1}{\mathrm{int}\, #1} \LetThereBe{\proj}{\Pi} \letThereBe{\epi}{1}{\mathrm{epi}\, #1} \letThereBe{\grad}{1}{\mathrm{grad}\, #1} \letThereBe{\hess}{1}{\nabla^2\, #1} \letThereBe{\subdif}{1}{\partial #1} \letThereBe{\co}{1}{\mathrm{co}\, #1} \letThereBe{\iter}{1}{^{[#1]}} \letThereBe{\set}{1}{\left\{ #1 \right\}} ``` </div> ##### **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í ```math \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** $\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**.