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

Vlastnosti konvexních množin

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

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

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á

Tedy jistě platí

Definice $\D{2.1.6}$ (Obaly)

Nechť $X \subseteq \R^n$


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í


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.


Revision #29
Created 21 December 2022 21:40:07 by Admin
Updated 6 January 2023 10:31:44 by Sceptri