Home A - Z
Page Index

An Otter Wiki

Commit ea58fa

2026-03-28 10:38:46 Štěpán Zapadlo: Add sensitivity analysis
/dev/null .. matematické programování/analýza citlivosti.md
@@ 0,0 1,166 @@
+ # Analýza citlivosti
+
+ <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{\secRefAt}{2}{\href{#2\#sec-#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}{./Nutné a postačující podmínky optimality} \, \and \, \eqRefAt{4.2}{./Nutné a postačující podmínky optimality}}
+ \letThereBe{\set}{1}{\left\{ #1 \right\}}
+ ```
+
+ </div>
+
+ Nyní se budeme věnovat řešení úlohy matematické programování v **závislosti na parametru**.
+
+ První se podíváme na úlohu matematické programování **s omezeními pouze ve tvaru rovností**, ale s obecnou závislostí na parametrech.
+
+ A v druhém (a posledním) případě se podíváme na úlohu **s omezeními ve tvaru nerovností**, ale s parametry **pouze** v podobě **absolutních členů** ve funkcích zadávajících tyto omezení.
+
+ > Zde je dobré podotknout, že druhý případ je mírně užitečnější a navíc si uvědomme, že **1 rovnost lze napsat jako 2 nerovnosti**
+
+ ### Úlohy s rovnostmi
+
+ ##### **Věta** $\secT{4.4.1}$ (O obálce)
+ Mějme úlohu
+
+ ```math
+ f(x,r) \to \min, \qquad g_1(x, r) = 0, \, \dots, \, g_m(x,r) = 0 \eqT{AC.1}
+ ```
+
+ kde $x \in \R^n, r \in \R^k, f, g_1, \dots, g_m \in C^1$. Připusťme, že pro **každou hodnotu parametru** $r$ má úloha $\eqRef{AC.1}$ **jediné řešení**, které označíme $x\str (r)$. Potom **hodnota úlohy** $\eqRef{AC.1}$ je
+
+ ```math
+ f\str(r) = f(x\str(r), r).
+ ```
+
+ Je-li $x\str(r)$ **diferencovatelná** vzhledem k $r$ a **Jacobiho matice** $\jacobx G(x\str (r), r) \in \R^{m\times n}$ má **plnou hodnost** $m$, pak platí
+
+ ```math
+ \parc {} {r_i}f\str(r) = \parc f {r_i} (x\str(r), r) + \sum_{j = 1}^m y_j\str(r) \parc {g_j} {r_i} (x\str(r), r)
+ ```
+
+ > Obálka je křivka, která se **množiny křivek dotýká** (tj. se dotýká každé křívky) a má společnou tečnu s danou křivkou
+ >
+ > Jinak řečeno je **tečná** k množině **křivek**
+
+ <div drawio-diagram="28"><img src="https://bookstack.zapadlo.name/uploads/images/drawio/2023-01/drawing-3-1672672543.png"></div>
+
+ Požadavky Věty $\secRef{4.4.1}$ jsou relativně silné, proto uveďme její "slabší verzi".
+
+ ##### **Věta** $\secT{4.4.2}$
+ Nechť $f, g_1, \dots, g_m \in C^2$ a $x\str$ je **lokálním řešením** úlohy
+
+ ```math
+ f(x) \to \min, \qquad g_1(x) = 0, \dots, g_m(x) = 0
+ ```
+
+ s odpovídajícími Lagrangeovými multiplikátory $y\str$. Nechť dále tato dvojice splňuje **postačující podmínku druhého řádu**, tj. $\hessx L(x\str, y\str) > 0$ na $\ker \jacob G(x\str)$, přičemž současně $x\str$ je **regulárním bodem**, tj. $\jacobx G(x\str) \in \R^{m\times n}$ má **plnou hodnost** $m$. Uvažme úlohu *parametrického programování*
+
+ ```math
+ f(x) \to \min, \qquad G(x) = u \eqT{AC.2},
+ ```
+
+ pro parametr $u \in \R^m$. Pak **existuje otevřená koule** $S$ se **středem v počátku** ($u = 0$) taková, že pro každé $u \in S$ existuje **lokální řešení** $x\str(u) \in \R^n$ úlohy $\eqRef{AC.2}$ a odpovídající $y\str(u) \in \R^m$. Navíc $x\str(\cdot)$ a $y\str(\cdot)$ jsou **spojitě diferencovatelné** funkce na $S$ a platí $x\str(0) = x\str, y\str(0) = y\str$ a pro každé $u \in S$ máme
+
+ ```math
+ \grad f\str(u) = - y\str(u),
+ ```
+
+ kde $f\str(u)$ značí **optimální hodnotu úlohy** $\eqRef{AC.2}$ vzhledem k $u$, tj. klademe $f\str(u) := f(x\str(u))$.
+
+ > Jednoduše řečeno se optimální hodnota mění **podle Lagrangeových multiplikátorů** pro danou hodnotu $u$
+
+ ### Úlohy s nerovnostmi
+
+ Uvažujme úlohu závislou na $m$-tici parametrů $b = (b_1, \dots, b_m)^T \in \R^m$, tj.
+
+ ```math
+ f(x) \to \min, \qquad x \in X(b) := \set{x \in P \subseteq \R^n \mid g_i(x) \leq b_i, \, i \in \set{1, \dots, m}} \eqT{4.4.2}
+ ```
+
+ A dále zaveďme značení
+
+ ```math
+ G(x) := (g_1(x), \dots, g_m(x))^T, \quad X(b) := \set{x \in P \mid G(x) \leq b}
+ ```
+
+ ```math
+ B := \set{b \in \R^m \mid X(b) \neq \emptyset}, \quad F(b) := \inf_{x \in X(b)} f(x), \, b \in B
+ ```
+
+ množinu **K-T vektorů** úlohy $\eqRef{4.4.2}$ označme
+
+ ```math
+ Y(b) := \set{y \in \R^m \mid y \geq 0, \, F(b) \leq f(x) + \scal{y} {G(x) - b} \, \forall x \in P}
+ ```
+
+ a **subdifereniál** funkce $F(b)$ (viz Definice $\secRefAt{2.5.1}{./Subgradient a subdiferenciál a Fenchelova transformace}$) označme
+
+ ```math
+ \subdif F(b) := \set{a \in \R^m \mid F(b') - F(b) \geq \scal a {b' - b} \, \forall b' \in B}
+ ```
+
+ ##### **Věta** $\secT{4.4.3}$
+ Nechť množina $P \subseteq \R^n$ je **konvexní**, funkce $f, g_1, \dots, g_m$ jsou **konvexní** na $P$ a platí $0 \in B, F(0) > -\infty$ a $Y(0) \neq \emptyset$. Potom
+ 1. množina $B$ je **konvexní**
+ 2. funkce $F(b)$ je **konečná, konvexní** a **nerostoucí** na $B$
+ 3. platí $\subdif F(b) = -Y(b)$ pro **všechna** $b \in B$
+
+ > Z předpokladů Věty $\secRef{4.4.3}$ plyne, že
+ > - úloha $\eqRef{4.4.2}$ je **přípustná** pro $b = 0$
+ > - úloha $\eqRef{4.4.2}$ **má řešení** pro $b = 0$
+ > - množina **K-T vektorů** úlohy $\eqRef{4.4.2}$ je **neprázdná** (toto **není** splněno automaticky, viz Věta $\secRefAt{4.3.2}{./Duální úloha}$)
+ >
+ > Navíc je-li $F$ dokonce **diferencovatelná** v $b$, pak $\subdif F(b)$ je **jednoprvková** množina, která obsahuje **pouze** $-\gradT F(b)$ a tedy tento vektor musí být roven $(-1) \cdot$ _**jediný K-T vektor**_ této úlohy. (Toto je analogie Věty *O obálce* $\secRef{4.4.1}$)
+
+ > Podle Věty $\secRefAt{4.3.6}{./Duální úloha}$ jsme popsali **K-T vektory** úlohy $\knvxProg$ pomocí řešení **duální úlohy** $\eqRefAt{4.3.1}{./Duální úloha}$. Část 3. této věty jim navíc dává ještě charaketeristiku **subgradientu hodnoty úlohy parametrického programování** $\eqRef{4.4.2}$.
+ >> V případě **regulární** úlohy *konvexního programování* dostáváme zkombinováním těchto dvou výsledků $\subdif F(b) = - Y\str(b)$, kde $Y\str(b)$ je množina řešení **duální úlohy** (viz Věta $\secRefAt{4.3.6}{./Duální úloha}$).
+
+ Pomocí Věty $\secRef{4.4.3}$ jsme schopni dostat zajímavé výsledky o původní úloze *matematického programování*, tj. $\eqRef{4.4.2}$ s $b = 0$.
+
+ ##### **Důsledek** $\secT{4.4.4}$
+ Nechť množina $P \subseteq \R^n$ je **konvexní**, funkce $f, g_1, \dots, g_m$ jsou **konvexní** na $P$, platí $F(0) > - \infty$ a **existuje** $\bar x \in P$ takové, že $G(\bar x) < 0$ (viz **Slaterova podmínka** ve Větě $\secRefAt{4.3.2}{./Duální úloha}$). Potom $0 \in B$ a
+ 1. funkce $F(\cdot)$ je **spojitá** v bodě $b = 0$
+ 2. pro libovolné $h \in \R^m$ **existuje jednostranná směrová** derivace
+
+ ```math
+ F'_ h(0) = \max_ {y\str \in Y(0)} \scal {-y\str} h
+ ```
+
+ 3. funkce $F$ je **diferencovatelná** v bodě $b = 0$ právě tehdy, když $Y(0)$ je **jednoprvková** množina, tj. $Y(0) = \brackets{y\str}$. Navíc platí $\gradT F(0) = -y\str$.
+
+ > Z části 3. okamžitě plyne, že pokud **existuje více K-T vektorů** $\iff$ funkce $F$ **není diferencovatelná**
+
+ ### Fenchelova transformace a duální úloha
+
+ Lze ukázat, že pro $F(b)$ **hodnotu primární úlohy** je $F\str(y) = -\vf(y)$ a tedy duální úlohu $\eqRefAt{4.3.1}{./Duální úloha}$ je možné psát jako
+
+ ```math
+ -F\str(y) \to \max, \quad y \geq 0
+ ```
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