Analýza citlivosti
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
\[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
\[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í
\[\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)\]<div drawio-diagram="28"><img src="https://bookstack.zapadlo.name/uploads/images/drawio/2023-01/drawing-3-1672672543.png"></div>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
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
\[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í
\[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
\[\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.
\[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í
\[G(x) := (g_1(x), \dots, g_m(x))^T, \quad X(b) := \set{x \in P \mid G(x) \leq b}\]\[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
\[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
\[\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
- množina \(B\) je konvexní
- funkce \(F(b)\) je konečná, konvexní a nerostoucí na \(B\)
- 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
funkce \(F(\cdot)\) je spojitá v bodě \(b = 0\)
pro libovolné \(h \in \R^m\) existuje jednostranná směrová derivace
\[F'_ h(0) = \max_ {y\str \in Y(0)} \scal {-y\str} h\]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
\[-F\str(y) \to \max, \quad y \geq 0\]