<div style="visibility:hidden;height:0;overflow:hidden;margin:0;padding:0">

</div>

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

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

- **silně oddělitelné**, jestliže existuje $p \in \R^n \setminus \brackets{\vv 0}$ takové, že

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

se nazývá **oddělující nadrovinou** množin $X_1$ a $X_2$.

---

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$.

---

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$ **uzavř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í)

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

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

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

Nechť $X \subseteq \R^n$ je neprázdná konvexní množina a nechť $a \in \rd X \subseteq \partial X$. Pak v bodě $a$ existuje **vlastní** opěrná nadrovina množiny $X$.

$$\overline X \setminus \ri X = \rd X \subseteq \partial X = \overline X \setminus \interior X$$

Nechť $X_1, X_2 \subseteq \R^n$ jsou neprázdné, konvexní a disjunktní množiny. Pak pro tyto množiny existuje oddělující nadrovina.

Neprázdné konvexní množiny $X_1, X_2 \subseteq \R^n$ jsou **vlastně** oddělitelné právě tehdy, když $\ri X_1 \cap \ri X_2 = \emptyset$.

---

Nechť $A \in \R^{m \times n}$ a $b \in \R^m$. Potom je **právě jeden** z následujících systémů rovnic a nerovnic řešitelný:

$$Ax = b, \quad x \geq 0, \eqT{2.3.5}$$

$$A^T y \geq 0, \quad \scal y b < 0 \eqT{2.3.6}$$

Ještě jinak můžeme větu formulovat tak, že buď $b$ leží v *konvexním kuželu* $\cone{\brackets{a_i}_{i=1}^n}$ nebo jsou $b$ a *konvexní kužel* **silně oddělitelné**.

Z této věty pak plynou tzv. **věty o alternativě**, které můžeme najít například v lineárním programování.

Tvrzení **Věty** $\secRef{2.3.9}$ můžeme také napsat jako:\

$$f_0(x) := \scal {a_0} x < 0, \quad f_i(x) := \scal {a_i} x \leq 0, \quad i \in \brackets{1, \dots, m}$$

*nemá pro daná* $a_0, \dots, a_m \in \R^m$ *řešení* na $\R^n$*, pak existují čísla* $y_1, \dots, y_m \geq 0$ *taková, že*

$$a_0 + \sum_{i = 1}^m y_i a_i = 0, \quad \text{tj. }f_0(x) + \sum_{i = 1}^m y_i f_i(x)= 0$$

*pro každé* $x \in \R^n$.

Toto plyne z toho, že pokud v $\secRef{2.3.9}$ položíme $b = a_0$ a $A = -(a_1, \dots, a_m)$ (a zaměníme-li $x$ a $y$), pak podle předpokladu **nemá** systém $A^T x \geq 0 \, \and \, \scal x {a_0} < 0$ řešení. A tedy dostáváme, že systém $Ay = a_0, y \geq 0$ řešení **mít musí**.

---

Nechť množina $X \subseteq \R^n$ je konvexní, funkce $f_1, \dots, f_k: X \to \R$ jsou **konvexní** a funkce $f_{k+1}, \dots, f_m$ **afinní**, tj. pro $j \in \brackets{k+1, \dots, m}$ máme $f_j = \scal {a_j} x + \beta_j$ pro vhodná $a_j \in \R^n$ a $\beta_j \in \R$. Jestliže systém nerovností a rovností

**nemá řešení** na $X$, pak existují takové konstanty

$$y_1, \dots, y_k \geq 0 \quad \and \quad y_{k+1}, \dots, y_m \in \R$$

že pro alespoň jedno $l \in \brackets{1, \dots, m}$ je $y_l \neq 0$ a pro všechna $x \in X$ platí

$$\sum_{i = 1}^m y_i f_i(x) \geq 0 \eqT{2.3.9}$$

---

Následující věta udává podmínky, které zajišťují kladnost jistého význačného $y_i$ (BÚNO $i = 0$) ve vztahu $\eqRef{2.3.9}$. Po vydělení vztahu $\eqRef{2.3.9}$ tímto $y_i$ dostaneme BÚNO $y_i = 1$.

Nechť množina $X \subseteq \R^n$ je konvexní a funkce $f_0, \dots, f_m: X \to \R$ jsou konvexní. Jestliže systém nerovností

$$f_0(x) < 0, \eqT{2.3.10}$$

$$f_i(x) < 0, \quad i \in \brackets{1, \dots, m} \eqT{2.3.11}$$

**nemá řešení** na $X$ a podsystém $\eqRef{2.3.11}$ **má řešení** na $X$, pak existují $y_1, \dots, y_m \geq 0$ taková, že pro všechna $x \in X$ platí

$$f_0(x) + \sum_{i = 1}^m y_i f_i(x) \geq 0 \eqT{2.3.12}$$