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

$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \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} $$

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