Home A - Z
Page Index

An Otter Wiki

Commit e63e3e

2026-03-28 10:17:16 Štěpán Zapadlo: Fix display math
/dev/null .. nutné a postačující podmínky optimality.md
@@ 0,0 1,210 @@
+ # Nutné a postačující podmínky optimality
+
+ <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{\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{\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{\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{\set}{1}{\left\{ #1 \right\}}
+ ```
+
+ </div>
+
+ ### Obecný úvod
+ **Úlohou matematického programování** nazveme
+
+ ```math
+ 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í
+
+ ```math
+ 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}$
+
+ > 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
+ - **množinu přípustných vektorů**
+ ```math
+ \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ů**)
+ ```math
+ \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>
+
+ ##### **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
+
+ ```math
+ \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
+
+ ```math
+ \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$.
+ 1. 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$
+ 2. 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
+
+ ```math
+ (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
+
+ ```math
+ \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í
+
+ ```math
+ (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
+
+ ```math
+ 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**.
+
+ > Omezení nazveme **aktivní**, pokud se realizuje jako **rovnost**
+ Dále ještě zaveďme následující
+
+ ```math
+ Q := \set{y = (y_1, \dots, y_m)^T \mid y_1, \dots, y_k \geq 0}
+ ```
+
+ a dvě další množiny:
+ - **Množinu aktivních omezení** v bodě $x\str$
+ ```math
+ 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
+ ```math
+ 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í
+
+ ```math
+ \scal {\gradx L(x\str, y_0\str, y\str)} {x - x\str} \geq 0 \quad \forall x \in P \eqT{4.2.3}
+ ```
+
+ ```math
+ 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**.
+
+ > 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í**:
+ - **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}$
+
+ ##### **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ů:
+ 1. funkce $L(x, y\str)$ je **konvexní** na množině $P$
+ 2. ú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:
+ 1. **(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$.
+ 2. **(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}$
+ 3. **(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.
+
+ ```math
+ \gradx L(x\str, y\str) = 0,
+ ```
+
+ ```math
+ 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},
+ ```
+
+ ```math
+ 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),
+ ```
+
+ ```math
+ y_i\str \in \R \text{ pro } i \in \set{k+1, \dots, m}
+ ```
+
+ Jestliže
+
+ ```math
+ \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$.
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