Oddělování konvexních množin
Oddělitelnost množin
Definice \(\secT{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í nadrovinou množin \(X_1\) a \(X_2\).
<div drawio-diagram="15"><img src="https://bookstack.zapadlo.name/uploads/images/drawio/2022-12/drawing-3-1672338675.png"></div>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 \(\secT{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 \(\secT{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\) 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í)
Věta \(\secT{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 \(\secT{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 \(\secT{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 \(\secT{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 \(\secT{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 \(\secT{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, \eqT{2.3.5}\] \[A^T y \geq 0, \quad \scal y b < 0 \eqT{2.3.6}\]Jinak řečeno soustava \(\eqRef{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 \(\secRef{2.3.9}\) můžeme také napsat jako:
Jestliže systé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í.
Věta \(\secT{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í
\[\rcases{f_i(x) < 0, & i \in \brackets{1, \dots, k} \\ f_j(x) = 0, & j \in \brackets{k+ 1, \dots, m}} \eqT{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 \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\).
Věta \(\secT{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, \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}\]