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 X1,X2X_1, X_2 se nazývají

  • oddělitelné, jestliže existuje p∈Rn∖\brackets\vv0p \in \R^n \setminus \brackets{\vv 0} takové, že
    \scalpx1≥\scalpx2\scal p {x_1} \geq \scal p {x_2} pro každé x1∈X1,x2∈X2x_1 \in X_1, x_2 \in X_2.
  • vlastně oddělitelné, jestliže jsou oddělitelné a zároveň existují body x1∗∈X1,x2∗∈X2x_1^* \in X_1, x_2^* \in X_2 takové, že
    \scalpx1∗>\scalpx2∗\scal p {x_1^* } > \scal p {x_2^* }
  • silně oddělitelné, jestliže existuje p∈Rn∖\brackets\vv0p \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},undefinedH_{p,\beta} := \brackets{x \in \R^n \mid \scal p x = \beta}$$ se nazývá oddělující narovinou množin X1X_1 a X2X_2.

Ve vyjádření \bracketsx∈Rn∣\scalpx=β\brackets{x \in \R^n \mid \scal p x = \beta} značí pp normálový vektor nadroviny a β\beta její posunutí

Definice 2.3.2 (Projekce bodu)

Nechť X⊆RnX \subseteq \R^n je neprázdná množina a x∈Rnx \in \R^n. Bod x∗∈Xx^* \in X nazveme projekcí bodu xx na množinu XX a označíme \projX(x)\proj_X (x), jestliže \norm\projX(x)−x≤\normy−x \norm{\proj_X (x) - x} \leq \norm{y - x} pro každé y∈Xy \in X.

Věta 2.3.4

Neprázdné konvexní množiny X1,X2∈RnX_1,X_2 \in \R^n jsou silně oddělitelné právě tehdy, když mají nenulovou vzdálenost, tj. \dist(X1,X2):=inf⁡x1∈X1,x2∈X2\normx1−x2>0, \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∉X1−X2‾0 \notin \overline{X_1 - X_2}.

Back to top