Skip to main content

Oddělování konvexních množin

$$ \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\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\a{\alpha} \xdef\tagged#1{(\text{#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} $$

Definice 2.3.1 (Oddělitelnost množin)

Neprázdné množiny $X_1, X_2$ se nazývají

  • oddělitelné, jestliže existuje $p \in \R^n \setminus \brackets{\vv 0}$ takové, že
    $$\scal p {x_1} \geq \scal p {x_2}$$ pro každé $x_1 \in X_1, x_2 \in X_2$.
  • vlastně oddělitelné, jestliže jsou oddělitelné a zároveň existují body $x_1^* \in X_1, x_2^* \in X_2$ takové, že
    $$\scal p {x_1^* } > \scal p {x_2^* }$$
  • silně oddělitelné, jestliže existuje $p \in \R^n \setminus \brackets{\vv 0}$ takové, že
    $$\inf_{x_1 \in x_1} \scal p {x_1} > \sup_{x_2 \in X_2} \scal p {x_2},$$ je-li navíc $\beta \in [\sup_{x_2 \in X_2} \scal p {x_2}, \inf_{x_1 \in X_1} \scal p {x_1}]$, nadrovina $$H_{p,\beta} := \brackets{x \in \R^n \mid \scal p x = \beta}$$ se nazývá oddělující narovinou množin $X_1$ a $X_2$.

Ve vyjádření $\brackets{x \in \R^n \mid \scal p x = \beta}$ značí $p$ normálový vektor nadroviny a $\beta$ její posunutí

Definice 2.3.2 (Projekce bodu)

Nechť $X \subseteq \R^n$ je neprázdná množina a $x \in \R^n$. Bod $x^* \in X$ nazveme projekcí bodu $x$ na množinu $X$ a označíme $\proj_X (x)$, jestliže $$ \norm{\proj_X (x) - x} \leq \norm{y - x} $$ pro každé $y \in X$.

Věta 2.3.4

Neprázdné konvexní množiny $X_1,X_2 \in \R^n$ jsou silně oddělitelné právě tehdy, když mají nenulovou vzdálenost, tj. $$ \dist (X_1, X_2) := \inf_{x_1 \in X_1, x_2 \in X_2} \norm{x_1 - x_2} > 0, $$ což je ekvivalentní s podmínkou $0 \notin \overline{X_1 - X_2}$.

Pod kompaktní množinou myslíme množinu, která je ohraničená (má konečný průměr) a uzavřená (obsahuje svou hranici).

Pokud jsou množiny $X_1, X_2 \subseteq \R^n$ neprázdné, konvexní a disjunktní a navíc BÚNO je $X_1$ ohraničená a $X_2$ kompaktní, tak jsou množiny silně oddělitelné.
Požadavek kompaktnosti množiny $X_2$ vynechat nelze, viz protipříklad dvou hyperbol (obrázek je pouze ilustrativní)

Věta 2.3.5a (Geometrický popis konvexních množin)

Libovolná uzavřená konvexní množina $X \subseteq \R^n$ je řešením (nekonečné) soustavy neostrých lineárních rovnic.

Geometricky: každá uzavřená konvexní množina $X \subsetneqq \R^n$ je průnikem uzavřených poloprostorů, konkrétně všech uzavřených poloprostorů obsahujících $X$

Definice 2.3.6 (Opěrná nadrovina)

Nechť $X \subseteq \R^n$ je neprázdná množina a nechť $a \in \partial X := \overline X \setminus \interior X$. Nadrovina $H_{p, \beta}$ se nazývá

  • opěrnou nadrovinou množiny $X$ v bodě $a$, jestliže
    $$\scal p x \geq \beta = \scal p a$$ pro každé $x \in X$
  • vlastní opěrnou nadrovinou množiny $X$, jestliže je opěrnou nadrovinou množiny $X$ a zároveň existuje $x^* \in X$ takové, že
    $$\scal p {x^* } > \beta$$

Jinak řečeno množina musí ležet pouze v jednom z poloprostorů určených opěrnou nadrovinou.

Back to top