# Oddělování konvexních množin <div style="visibility:hidden;height:0;overflow:hidden;margin:0;padding:0"> ```math \newcommand{\LetThereBe}[2]{\newcommand{#1}{#2}} \newcommand{\letThereBe}[3]{\newcommand{#1}[#2]{#3}} \letThereBe{\addTag}{2}{\cssId{#1-#2}{\tag{#2}}} \letThereBe{\addLabel}{2}{\cssId{#1-#2}{\text{#2}}} \letThereBe{\refTag}{2}{\href{###1-#2}{(\text{#2})}} \letThereBe{\eqT}{1}{\addTag{eq}{#1}}\letThereBe{\secT}{1}{\addLabel{sec}{#1}} \letThereBe{\eqRef}{1}{\refTag{eq}{#1}} \letThereBe{\secRef}{1}{\refTag{sec}{#1}} \letThereBe{\eqRefAt}{2}{\href{#2\#eq-#1}{(\text{#1})}} \LetThereBe{\R}{\mathbb{R}} \LetThereBe{\N}{\mathbb{N}} \letThereBe{\rcases}{1}{\left.\begin{align}#1\end{align}\right\}} \letThereBe{\rcasesAt}{2}{\left.\begin{alignat}{#1}#2\end{alignat}\right\}} \letThereBe{\lcases}{1}{\begin{cases}#1\end{cases}} \letThereBe{\lcasesAt}{2}{\left\{\begin{alignat}{#1}#2\end{alignat}\right.} \letThereBe{\scal}{2}{\langle #1, #2 \rangle} \letThereBe{\norm}{1}{\left\lVert #1 \right\rVert} \LetThereBe{\dist}{\rho} \LetThereBe{\and}{\&}\letThereBe{\brackets}{1}{\left\{ #1 \right\}} \letThereBe{\parc}{2}{\frac {\partial #1}{\partial #2}} \letThereBe{\mtr}{1}{\begin{pmatrix}#1\end{pmatrix}} \letThereBe{\bm}{1}{\boldsymbol{#1}} \letThereBe{\mcal}{1}{\mathcal{#1}} \letThereBe{\vv}{1}{\mathbf{#1}}\letThereBe{\vvp}{1}{\pmb{#1}} \LetThereBe{\ve}{\varepsilon} \LetThereBe{\l}{\lambda} \LetThereBe{\th}{\vartheta} \LetThereBe{\a}{\alpha} \LetThereBe{\vf}{\varphi} \letThereBe{\conv}{1}{\mathrm{conv}\, #1} \letThereBe{\cone}{1}{\mathrm{cone}\, #1} \letThereBe{\aff}{1}{\mathrm{aff}\, #1} \letThereBe{\lin}{1}{\mathrm{Lin}\, #1} \letThereBe{\span}{1}{\mathrm{span}\, #1} \LetThereBe{\O}{\mathcal O} \letThereBe{\ri}{1}{\mathrm{ri}\, #1} \letThereBe{\rd}{1}{\mathrm{r}\partial\, #1} \letThereBe{\interior}{1}{\mathrm{int}\, #1} \LetThereBe{\proj}{\Pi} \letThereBe{\epi}{1}{\mathrm{epi}\, #1} \letThereBe{\grad}{1}{\mathrm{grad}\, #1} \letThereBe{\gradT}{1}{\mathrm{grad}^T #1} \letThereBe{\gradx}{1}{\mathrm{grad}_x #1} \letThereBe{\hess}{1}{\nabla^2\, #1} \letThereBe{\hessx}{1}{\nabla^2_x #1} \letThereBe{\jacobx}{1}{D_x #1} \letThereBe{\jacob}{1}{D #1} \letThereBe{\subdif}{1}{\partial #1} \letThereBe{\co}{1}{\mathrm{co}\, #1} \letThereBe{\iter}{1}{^{[#1]}} \LetThereBe{\str}{^\*} \LetThereBe{\spv}{\mcal V} \LetThereBe{\civ}{\mcal U} \LetThereBe{\knvxProg}{\eqRefAt{4.1}{./nutne-a-postacujici-podminky-optimality} \, \and \, \eqRefAt{4.2}{./nutne-a-postacujici-podminky-optimality}} \letThereBe{\set}{1}{\left\{ #1 \right\}} ``` </div> ### 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 ```math \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 ```math \scal p {x_1^* } > \scal p {x_2^* } ``` - **silně oddělitelné**, jestliže existuje $p \in \R^n \setminus \brackets{\vv 0}$ takové, že ```math \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 ```math 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$. --- > 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 ```math \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 ```math \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* $$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í**. --- ##### **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í ```math \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}$$