Skip to main content

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 1.1\D{1.1} (Konvexní množina)

Nechť X⊂RnX \subset \R^n. Množina XX se nazývá konvexní, jestliže pro všechna x1,x2∈Xx_1, x_2 \in X a pro každé λ∈[0,1]\l \in [0,1] platí λx1+(1−λ)x2∈X(KM) \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 Xi,i∈IX_i, i \in I konvexní množiny. Potom

  • jejich sjednocení ⋂i∈IXi\bigcap_{i \in I} X_i je konvexní množina
  • jejich součet α1X1+⋯+αmXm={x∈Rn∣x=∑i=1mαixi pro neˇjakaˊ xi∈Xi}\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 2.1.3\D{2.1.3} (Speciální konvexní množiny)

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

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

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

  • afinní, jestliže pro každé x1,x2∈Xx_1, x_2 \in X a pro každé λ∈R\l \in \R platí λx1+(1−λ)x2∈X \l x_1 + (1 - \l)x_2 \in X

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

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

Nechť x1,…,xm∈Rnx_1, \dots, x_m \in \R^n. Lineární kombinace λ1x1+⋯+λmxm\l_1 x_1 + \dots + \l_m x_m se nazývá

  • konvexní, jestliže λ1,…,λm≥0\l_1, \dots, \l_m \geq 0 a ∑i=1mλi=1\sum_{i = 1}^m \l_i = 1
  • nezáporná, jestliže λ1,…,λm≥0\l_1, \dots, \l_m \geq 0
  • afinní, jestliže ∑i=1mλi=1\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 2.1.6\D{2.1.6} (Obaly)

Nechť X⊆RnX \subseteq \R^n

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

Všimněme si, že span X={\span X = \{ ∀\forall lineárních kombinacíkombinace prvků z XX }\},
ale Lin X=span {x2−x1,x3−x1,…,xm−x1}\lin X = \span \brackets{x_2 - x_1, x_3 - x_1, \dots, x_m - x_1}. Viz obrázek z přednášky

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

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

Věta 2.1.7\D{2.1.7}

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

  • conv X={x∣x=∑i=1mλixi, kde m∈N je libovolneˊ,x1,…,xm∈X,λ1,…,λm≥0,∑i=1mλi=1}\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={x∣x=∑i=1mλixi, kde m∈N je libovolneˊ,x1,…,xm∈X,λ1,…,λm≥0}\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={x∣x=∑i=1mλixi, kde m∈N je libovolneˊ,x1,…,xm∈X,λ1,…,λm∈R,∑i=1mλi=1}\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}
Věta 2.1.9\D{2.1.9} (Caratheódoryho)

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

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

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

To stejné neplatí o uzavřenosti.

Zobecnění vnitřku množiny

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

Nechť X⊆RnX \subseteq \R^n. Bod x∗∈Xx^* \in X se nazývá relativně vnitřním bodem množiny XX, jestliže existuje okolí O(x∗)\O(x^* ) bodu x∗x^* takové, že O(x∗)∩aff X⊆X \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 XX a značime ri X\ri X.
Množina r∂ X:=X‾∖ri X\rd X := \overline X \setminus \ri X se nazývá relativní hranice množiny XX.

Jistě platí int X⊆ri X\interior X \subseteq \ri X
a také ri X⊆X⊆X‾⊆aff X\ri X \subseteq X \subseteq \overline X \subseteq \aff X

Back to top