Home A - Z
Page Index

An Otter Wiki

Commit 39f582

2026-03-27 22:31:03 Štěpán Zapadlo: Migrate convex set text from Bookstack
/dev/null .. matematické programování/konvexní množiny.md
@@ 0,0 1,125 @@
+ ```math
+ \newcommand{\LetThereBe}[2]{\newcommand{#1}{#2}} \newcommand{\letThereBe}[3]{\newcommand{#1}[#2]{#3}}
+ \letThereBe{\addTag}{2}{\cssId{#1-#2}{\tag{#2}}} \letThereBe{\refTag}{2}{\href{###1-#2}{(\text{#2})}}
+ \letThereBe{\eqT}{1}{\addTag{eq}{#1}}\letThereBe{\secT}{1}{\addTag{sec}{#1}}
+ \letThereBe{\eqRef}{1}{\refTag{eq}{#1}} \letThereBe{\secRef}{1}{\refTag{sec}{#1}}
+ \LetThereBe{\R}{\mathbb{R}} \LetThereBe{\N}{\mathbb{N}}
+ \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\}}
+ ```
+
+ # 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í
+
+ $$\l x_1 + (1 - \l)x_2 \in X$$
+
+ <div drawio-diagram="29"><img src="https://bookstack.zapadlo.name/uploads/images/drawio/2023-01/drawing-3-1672692761.png"></div>
+
+ > **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**.
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9