commit 5fa478

Commit `5fa478`

2026-03-27 23:00:49 Štěpán Zapadlo: Add align

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

`/dev/null` .. `matematické programování/oddělování konvexních množin.md`
@@ 0,0 1,195 @@
+	# 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í
+
+	<div drawio-diagram="15"><img src="https://bookstack.zapadlo.name/uploads/images/drawio/2022-12/drawing-3-1672338675.png"></div>
+
+	##### 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í)
+	<center><div drawio-diagram="16"><img src="https://bookstack.zapadlo.name/uploads/images/drawio/2022-12/drawing-3-1672340559.png"></div></center>
+
+	##### 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$
+
+	[![](https://bookstack.zapadlo.name/uploads/images/gallery/2022-12/scaled-1680-/image-1672340919071.png)](https://bookstack.zapadlo.name/uploads/images/gallery/2022-12/image-1672340919071.png)
+
+	### 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é.
+
+	[![](https://bookstack.zapadlo.name/uploads/images/gallery/2022-12/scaled-1680-/image-1672396933180.png)](https://bookstack.zapadlo.name/uploads/images/gallery/2022-12/image-1672396933180.png)
+
+	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í
+
+	$$\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}$$

Commit 5fa478

Commit `5fa478`