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\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\vf{\varphi} \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\gradT#1{\mathrm{grad}^T #1} \xdef\gradx#1{\mathrm{grad}_x #1} \xdef\hess#1{\nabla^2\, #1} \xdef\hessx#1{\nabla^2_x #1} \xdef\jacobx#1{D_x #1} \xdef\jacob#1{D #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} \xdef\iter#1{^{[#1]}} \xdef\str{^*} \xdef\spv{\mcal V} \xdef\civ{\mcal U} \xdef\knvxProg{\tagEqHere{4.1}{./nutne-a-postacujici-podminky-optimality} \, \and \, \tagEqHere{4.2}{nutne-a-postacujici-podminky-optimality}} $$

Oddělitelnost množin

Definice $\D{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~~nadrovinou 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 $\D{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 $\D{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 $\D{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$

Opěrné nadroviny

Definice $\D{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.

Věta $\D{2.3.7}$ (Existenci opěrné nadroviny)

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

Pro relativní vnitřek $\ri X$ množiny $X$ a její vnitřek platí $\interior X \subseteq \ri X$ a tedy jistě
$$\overline X \setminus \ri X = \rd X \subseteq \partial X = \overline X \setminus \interior X$$

Podmínky oddělitelnosti

Věta $\D{2.3.7a}$ (Oddělitelnost množin)

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.

Věta $\D{2.3.8}$

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

Věta $\D{2.3.9}$ (Farkas & Minkowski)

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, \tag{\T{2.3.5}} $$ $$ A^T y \geq 0, \quad \scal y b < 0 \tag{\T{2.3.6}} $$

Jinak řečeno soustava $\tagEq{2.3.5}$ má řešení právě tehdy, když pro všechna $y \in \R^m$ platí $A^T y \geq 0$ a zároveň $\scal y b \geq 0$

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 $\tagDe{2.3.9}$ můžeme také napsat jako:
Jestliže systém $$ 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 $\tagDe{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í.

Věta $\D{2.3.12}$ (Fan & Glicksburg & Hoffman)

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í $$ \begin{rcases} f_i(x) < 0, & i \in \brackets{1, \dots, k} \ f_j(x) = 0, & j \in \brackets{k+ 1, \dots, m} \end{rcases} \tag{\T{2.3.8}} $$ 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 \tag{\T{2.3.9}} $$

nebo

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 $\tagEq{2.3.9}$. Po vydělení vztahu $\tagEq{2.3.9}$ tímto $y_i$ dostaneme BÚNO $y_i = 1$.

Věta $\D{2.3.13}$ (Podmínky regularity)

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, \tag{\T{2.3.10}} $$ $$ f_i(x) < 0, \quad i \in \brackets{1, \dots, m} \tag{\T{2.3.11}} $$ nemá řešení na $X$ a podsystém $\tagEq{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 \tag{\T{2.3.12}} $$