Nutné a postačující podmínky optimality
Obecný úvod
Úlohou matematického programování nazveme
\[f(x) \to \min, \quad x \in X \eqT{4.1}\]kde přípustná množina \(X\) je zadána systém rovností a nerovností
\[X := \set{x \in P \subseteq \R^n \mid g_i(x) \leq 0, \, g_j(x) = 0, \, i = 1, \dots, k, \, j = k+1, \dots, m} \eqT{4.2}\]Zde je důležité podotknout, že vždy chceme nerovnostní omezení pouze tvaru \(\bm{g_i(x) \leq 0}\)
- množinu přípustných vektorů\[\spv(x^*, X) := \set{h \in \lin X \mid \exists \, \a_0 > 0 : x^*+ th \in X \text{ pro } \forall t \in (0, \a_0)}\]
- je to kužel
- množinu spádových vektorů (kužel zlepšujících vektorů)\[\civ(x^*, f) := \set{h \in \lin X \mid \exists \, \a_0 > 0 : x^*+ th \in D(f) \, \and \, f(x^*+ th) < f(x^*) \text{ pro } \forall t \in (0, \a_0)}\]
<div drawio-diagram="26"><img src="https://bookstack.zapadlo.name/uploads/images/drawio/2023-01/drawing-3-1672652858.png"></div>Je dobré si zapatovat, že
- \(m\) - počet omezení
- \(k\) - počet nerovností (tzn. \(g_1, \dots, g_k\) jsou nerovnosti, zbytek rovnosti) Omezení zakomponovaná v \(P\) se nazývají přímá, naopak omezení ve formě \(g_l\) se nazývají funkcionální. Dále definujme
Lemma \(\secT{4.1.1}\)
Nechť \(X \subseteq \R\) a \(f: X \to \R\) jsou dány. Je-li bod \(x^*\in X\) lokálním řešením úlohy \(\eqRef{4.1}\), potom
\[\spv (x^*, X) \cap \civ (x^*, f) = \emptyset\]Definice \(\secT{4.1.2}\) (Stacionární bod)
Nechť množina \(X \subseteq \R^n\) je konvexní a funkce \(f: X \to \R\) je diferencovatelná na (nějaké otevřené množině obsahující) \(X\). Řekneme, že bod \(x^*\in X\) je stacionárním bodem úlohy \(\eqRef{4.1}\) (nebo také **stacionárním bodem funkce*** \(f\) *na množině \(X\)), jestliže
\[\scal {\grad f(x^*)} {x - x^*} \geq 0 \eqT{4.1.2},\]pro každé \(x \in X\).
Výraz v \(\eqRef{4.1.2}\) je směrová derivace \(x^*\) do libovolného bodu v \(X\) - v těchto směrech musí být \(f\) neklesající Pro \(X = \R^n\) je podmínka \(\eqRef{4.1.2}\) splněna pouze v případě \(\grad f(x^*) = 0\) Dále ukažme, že stacionární bod ve smyslu Definice \(\secRef{4.1.2}\) má vlastnosti, které od něj očekáváme.
Věta \(\secT{4.1.3}\) (Vlastnosti stacionárního bodu)
Nechť \(f: X \to \R\) je diferencovatelná na (nějaké otevřené množině obsahující konvexní množinu) \(X \subseteq \R^n\).
- Je-li \(x^*\in X\) lokálním extrémem funkce \(f\) na \(X\) (tj. lokálním řešením úlohy \(\eqRef{4.1}\)), pak \(x^*\) je stacionárním bodem funkce \(f\) na \(X\)
- Naopak, je-li \(f\) (ostře) konvexní na \(X\) a \(x^*\in X\) je stacionárním bodem \(f\) na \(X\), pak \(x^*\) je (jediným) řešením úlohy \(\eqRef{4.1}\), tj. (jediným) globálním minimem \(f\) na \(X\).
Pokud avšak \(f\) není konvexní, potřebujeme o rozhodnutí "extrémnosti" stacionárního bodu další nástroje
Nutná podmínka pro \(\eqRef{4.1}\)
Je-li \(x^*\in X\) lokálním minimem funkce \(f: X \to \R, \, f \in C^2\), na konvexní množině \(X \subseteq \R^n\), pak
\[(x - x^*)^T \hess f(x^*)(x - x^*) \geq 0\]pro všechna \(x \in X\) taková, že \(\gradT f(x^*)(x - x^*) = 0\), tj. pro vektory \((x - x^*)\in \ker\gradT f(x^*)\)
Postačující podmínka pro \(\eqRef{4.1}\)
Bod \(x^*\) je lokálním minimem funkce \(f: X \to \R, f \in C^2\), na konvexní množině \(X \subseteq \R^n\), jestliže
\[\gradT f(x^*) (x - x^*) \geq 0, \, \forall x \in X,\](tj. je to stacionární bod ve smyslu Definice \(\secRef{4.1.2}\)), množina \(X\) je polyedr a platí
\[(x - x^*)^T \hess f(x^*) (x - x^*) > 0\]pro všechna \(x \in X\) taková, že \(x \neq x^*\) a \((x - x^*) \in \ker \gradT f(x^*)\)
Je-li \(X\) polyedr, pak je \(\spv (x^*, X)\) uzavřená
Nutné a postačující podmínky optimality
Uvažujme přidruženou Lagrangeovu funkci \(L: P \times \R \times \R^m \to \R\) k úloze \(\eqRef{4.1} \, \and \, \eqRef{4.2}\) definovanou jako
\[L(x, y_0, y) := y_0 f(x) + \sum_{i = 1}^m y_i g_i(x), \eqT{4.1.2}\]přičemž v případě \(y_0 = 1\) bude \(L(x, 1, y) := L(x,y)\). Navíc čísla \(y_0, \dots, y_m\) nazyváme Lagrangeovými multiplikátory.
\[Q := \set{y = (y_1, \dots, y_m)^T \mid y_1, \dots, y_k \geq 0}\]Omezení nazveme aktivní, pokud se realizuje jako rovnost Dále ještě zaveďme následující
a dvě další množiny:
Množinu aktivních omezení v bodě \(x\str\)
\[I(x\str) := \set{i \in \set{1, \dots, k} \mid g_i(x\str) = 0}, \quad x\str \in X\]Množinu indexů všech funkcí, které se v bodě \(x\str\) realizují jako rovnost
\[S(x\str) := I(x\str) \cup \set{k+1, \dots, m}, \quad x\str \in X\]
Věta \(\secT{4.2.1}\) (Lagrangeův princip)
Nechť množina \(P \subseteq \R^n\) je konvexní, funkce \(f, g_1, \dots, g_k : P \to \R\) jsou diferencovatelné v bodě \(x^*\in X\) a \(g_{k+1}, \dots, g_m\) jsou spojitě diferencovatelné na nějakém okolí bodu \(x^*\). Je-li bod \(x^*\in X\) lokálním řešením úlohy \(\eqRef{4.1} \, \and \, \eqRef{4.2}\), pak existují Lagrangeovy multiplikátory \(y_0\str > 0\) a \(y\str \in Q\) takové, že ne všechna \(y_0\str, \dots, y_m\str\) jsou nulová a platí
\[\scal {\gradx L(x\str, y_0\str, y\str)} {x - x\str} \geq 0 \quad \forall x \in P \eqT{4.2.3}\]\[y_i\str g_i(x\str) = 0, \quad i = 1, \dots, m \eqT{4.2.4}\]Podmínka \(\eqRef{4.2.3}\) znamená, že \(x\str\) musí být stacionárním bodem funkce \(L(x, y_0\str, y\str)\) (podmínka stacionarity). Dále podmínka \(\eqRef{4.2.4}\) se nazývá podmínka komplementarity a požadavek \(y_1\str, \dots, y_k\str > 0\) jako podmínka duality.
- Regulárnost bodu \(x\str\), tj, bod \(x\str\) je regulární, pokud jsou \(\grad g_i(x\str)\) pro \(i \in S(x\str)\) lineárně nezávislé (tj. gradienty aktivních omezení jsou LNZ)
- afinní omezení - funkce \(g_1, \dots, g_m\) jsou afinní
- Slaterova podmínka - \(g_1, \dots, g_k\) jsou konvexní, \(g_{k+1}, \dots, g_m\) jsou afinní, konstantní vektory \(\grad g_i\) jsou lineárně nezávislé pro \(i \in \set{k+1, \dots, m}\) a existuje \(\bar x \in P\) takové, že \(g_i(\bar x) < 0\) pro \(i \in \set{1, \dots, k}\) a \(g_j(\bar x) = 0\) pro \(j \in \set{k+1, \dots, m}\)
Jistě \(y_0\str, y_1\str, \dots, y_k\str \geq 0\), \(y_{k+1}\str, \dots, y_m\str \in \R \iff y_0\str > 0\) a \(y\str \in Q\) Jelikož situace s \(y_0\str = 0\) je problematická, existují podmínky na zaručení \(y_0\str \neq 0\), což je ekvivalentní s \(y_0\str = 1\). Tyto podmínky se nazývají podmínky kvalifikovaného omezení:
Důsledek \(\secT{4.2.2}\)
Nechť \(P \subseteq \R^n\) je konvexní množina, funkce \(f, g_1, \dots, g_m\) jsou diferencovatelné na (nějaké otevřené množině obsahující) \(P\) a pro \(x\str \in X\) existují multiplikátory \(y\str \in Q\) takové, že platí \(\eqRef{4.2.3}\) & \(\eqRef{4.2.4}\) s \(y_0\str = 1\). Nechť je dále splněn (alespoň) jeden z následujících předpokladů:
- funkce \(L(x, y\str)\) je konvexní na množině \(P\)
- úloha \(\eqRef{4.1}\) & \(\eqRef{4.2}\) je úlohou konvexního programování, tj. na konvexní množině \(P\) jsou funkce \(f, g_1, \dots, g_k\) konvexní a \(g_{k+1}, \dots, g_m\) afinní Pak bod \(x\str\) je globálním řešením úlohy \(\eqRef{4.1}\) & \(\eqRef{4.2}\).
Teoreticky stačí pouze kvazikonvexní \(g_1, \dots, g_k\)
Věta \(\secT{4.2.3}\) (Karushova-Kuhnova-Tuckerova v diferenciálním tvaru)
Nechť \(P \subseteq \R^n\) je konvexní množina, funkce \(f, g_1, \dots, g_k\) konvexní a diferencovatelné na (nějaké otevřené množině obsahující) \(P\), funkce \(g_{k+1}, \dots, g_m\) afinní na \(P\) a nechť platí (alespoň) jedna z následujících podmínek:
- (LNZ) množina \(P\) je otevřená, vektory \(\grad g_i(x), i \in S(x)\) jsou lineárně nezávislé pro každé \(x \in X\).
- (Slaterova) funkcionální omezení jsou pouze tvaru nerovností, tj. \(k = m\), a existuje bod \(\bar x \in P\) takový, že \(g_i(\bar x) < 0\) pro \(i \in \set{1, \dots, k}\)
- (lineární) množina \(P\) je polyedr a funkce \(g_1, \dots, g_k\) jsou afinní Pak \(x\str\) je řešením úlohy \(\eqRef{4.1}\) & \(\eqRef{4.2}\) právě tehdy, když existuje \(y\str \in Q\) takové, že platí \(\eqRef{4.2.3}\) & \(\eqRef{4.2.4}\) s \(y_0\str = 1\).
Věta \(\secT{4.2.4}\)
Nechť funkce \(f, g_1, \dots, g_m\) jsou dvakrát spojitě diferencovatelné v bodě \(x\str\) a \(x\str \in \interior P\) je takový, že existují multiplikátory \(y\str \in Q\) splňující \(\eqRef{4.2.3}\) & \(\eqRef{4.2.4}\) s \(y_0\str = 1\) a současně \(y_i\str > 0\) pro \(i \in I(x\str)\) (tzv. podmínka ostré komplementarity), tj.
\[\gradx L(x\str, y\str) = 0,\]\[g_i(x\str) \leq 0 \text{ pro } i \in \set{1, \dots, k}, \qquad g_i(x\str) = 0 \text{ pro } i \in \set{k+1, \dots, m},\]\[y_i\str > 0 \text{ pro } i \in I(x\str), \qquad y_i\str = 0 \text{ pro } i \in \set{1, \dots, k} \setminus I(x\str),\]\[y_i\str \in \R \text{ pro } i \in \set{k+1, \dots, m}\]Jestliže
\[\hessx L(x\str, y\str) > 0 \text{ na } \ker (\gradT g_i(x\str))_{i \in S(x\str)},\]tj. \(h^T \hessx L(x\str, y\str) h > 0\) pro všechna \(h \in \R^n \setminus \brackets{0}\) taková, že \(\scal {\grad g_i(x\str)} h = 0\) pro \(i \in S(x\str)\), pak bod \(x\str\) je ostré lokální minimum funkce \(f\) na množině \(X\).