Duální úloha
Definice \(\secT{4.3.1}\) (Kuhnovy-Tuckerovy vektory)
Vektor \(y\str \in Q\) (prvních \(k\) složek je nezáporných) se nazývá Kuhnnovým-Tuckerovým vektorem (K-T vektorem) úlohy \(\knvxProg\), jestliže
\[f\str \leq f(x) + \sum_{i = 1}^m y_i\str g_i(x) = L(x,y\str) \quad \forall x\in P, \eqT{4.3.0}\]kde \(f\str := \inf_{x \in X} f(x)\) je hodnota úlohy \(\knvxProg\).
K-T vektor pro danou úlohu nemusí existovat
Věta \(\secT{4.3.2}\)
Nechť úloha \(\knvxProg\) je úlohou konvexního programování, tj. množina \(P \subseteq \R^n\) je konvexní, funkce \(f, g_1, \dots, g_k\) konvexní a \(g_{k+1}, \dots, g_m\) jsou afinní, a nechť dále platí (alespoň) jedna z podmínek regularity:
- (Slaterova) \(k = m\) a existuje \(\bar x \in P\) takové, že \(g_i(\bar x) < 0\) pro \(i = 1, \dots, m\)
- (lineární) množina \(P\) je polyedr, funkce \(f, g_1, \dots, g_k\) jsou afinní a \(X \neq \emptyset\).
Pak existuje K-T vektor úlohy \(\knvxProg\).
Zde se podmínka 2. liší od podmínky 3. ve Větě \(\secRefAt{4.2.3}{./Nutné a postačující podmínky optimality}\) - vyžaduje ještě neprázdnost přípustné množiny
Úloha konvexního programování splňující nějakou z podmínek z Věty \(\secRef{4.3.2}\) se nazývá regulární.
Definice \(\secT{4.3.3}\) (Duální úloha)
Nechť \(y \in Q\). Definujme funkci
\[\vf(y) := \inf_{x \in P} L(x,y) = \inf_{x \in P} \left( f(x) + \sum_{i = 1}^m y_i g_i(x) \right)\]a množinu (tzv. efektivní definiční obor)
\[Y := \set{y \in Q \mid \vf(y) > -\infty}.\]Pak úloha
\[\vf(y) \to \max, \qquad y \in Y \eqT{4.3.1}\]se nazývá duální úlohou k úloze \(\knvxProg\). Číslo
\[\vf\str := \sup_{y \in Y} \vf(y)\]se nazývá hodnotou duální úlohy \(\eqRef{4.3.1}\).
Úloha \(\eqRef{4.3.1}\) je úlohou konkávního programování, tj. množina \(Y\) je konvexní a funkce \(\vf\) je konkávní na \(Y\).
Věta \(\secT{4.3.5}\) (Slabá věta o dualitě)
Pro každé \(x \in X\) a každé \(y \in Q\) platí
\[f(x) \geq \vf(y)\]Zejména, pokud \(X \neq \emptyset\) a \(Y \neq \emptyset\), pak \(f\str \geq \vf\str\).
V případě \(X = \emptyset\) a/nebo \(Y = \emptyset\) je nerovnost splněna triviálně, neboť \(\inf \emptyset = \infty\) a \(\sup \emptyset = - \infty\).
Věta \(\secRef{4.3.5}\) říká, že pro duální rozdíl \(g\) (duality gap) s \(x \in X \neq \emptyset\) a \(y \in Y \neq \emptyset\) bude platit
\[g(x,y) := f(x) - \vf(y) \geq 0\]Navíc číslo \(g(x\str,y\str) := f\str - g\str\) udává tzv. optimální duální rozdíl (optimal duality gap). Dá se také říct, že pro libovolné \(y \in Q\) je hodnota \(\vf(y)\) dolní hranicí minima účelové funkce úlohy \(\knvxProg\).
Certifikát optimality
Jsou-li \(x\str \in X\) a \(y\str \in Q\) taková, že platí
\[f(x\str) = \vf(y\str),\]pak \(x\str\) a \(y\str\) jsou optimálními řešeními svých příslušných úloh.
Duální rozdíl je úzce spjat s existencí K-T vektorů. Jestliže je duální rozdíl nenunlový, tj. \(f\str > \vf\str\), pak množina K-T vektorů musí být prázdná.
Jinak řečeno, existence K-T vektorů zaručuje \(f\str = \vf\str\)
Věta \(\secT{4.3.6}\) (Silná věta o dualitě)
Nechť úloha \(\knvxProg\) je regulární úlohou konvexního programování (viz. Věta \(\secRef{4.3.2}\)). Pokud \(f\str > -\infty\), pak platí tzv. vztah duality
\[f\str = \vf\str, \quad \text{ tj. } \quad \inf_{x \in P}\sup_{y \in Q}L(x,y) = \sup_{y \in Q}\inf_{x \in P} L(x,y),\]přičemž množina řešení duální úlohy \(\eqRef{4.3.1}\) je neprázdná a shodná s množinou všech K-T vektorů úlohy \(\knvxProg\).
Z Věty \(\secRef{4.3.6}\) vyplývá, že pokud \(\knvxProg\) je regulární úlohou konvexního programování (viz Věta \(\secRef{4.3.2}\)) a
- jestliže \(Y \neq \emptyset\), pak duální úloha je řešitelná a \(f\str > -\infty\)
- jestliže \(Y = \emptyset\), pak \(f\str = -\infty\)
Celkem z Vět \(\secRef{4.3.5}, \secRef{4.3.6}\) a z bezprostředně výše uvedného důsledku vyplývá, že v případě regulární úlohy konvexního programování mohou nastat pouze 2 možnosti
| Duální Ú. \ Primární Ú. | Nepřípustná (\(f\str = \infty\)) | Přípustná a Omezená | Neomezená (\(f\str = -\infty\)) |
|---|---|---|---|
| Neomezená (\(\vf\str = \infty\)) | NE (Ano bez regularity) | NE | NE |
| Přípustná a Omezená | NE (Možná bez regularity) | ANO | NE |
| Nepřípustná (\(\vf\str = -\infty\)) | NE (Ano bez regularity) | NE | ANO |
Z regularity plyne, že \(X \neq \emptyset\)
Věta \(\secT{4.3.8}\) (Kuhnova-Tuckerova v nediferenciálním tvaru)
Nechť úloha \(\knvxProg\) je regulární úlohou konvexního programování (viz Věta \(\secRef{4.3.2}\)). Pak \(x\str \in X\) je řešením této úlohy právě tehdy, když platí (alespoň) jedna z podmínek:
existuje \(y\str \in Q\) takové, že \(f(x\str) = \vf(y\str)\)
existuje \(y\str \in Q\) takové, že \
\[L(x\str,y\str) = \min_{x \in P}L(x, y\str), \eqT{4.3.2}\]\[y_i\str g_i(x\str) = 0, \quad i \in \set{1, \dots, m}, \eqT{4.3.3}\]
Navíc množina takovýchto vektorů \(y\str \in Q\) splývá s množinou řešení duální úlohy (a podle Věty \(\secRef{4.3.6}\) tedy i s množinou K-T vektorů úlohy \(\knvxProg\)).
Jsou-li navíc funkce \(f, g_1, \dots, g_m\) diferencovatelné v bodě \(x\str\), pak podmínka \(\eqRef{4.3.2}\) je ekvivalentní s podmínkou \(\eqRefAt{4.2.3}{./Nutné a postačující podmínky optimality}\) pro \(y_0\str = 1\), zatímco \(\eqRef{4.3.3}\) odpovídá \(\eqRefAt{4.2.4}{./Nutné a postačující podmínky optimality}\).
Tedy Věta \(\secRef{4.3.8}\) je skutečně zobecnění KKT Věty \(\secRefAt{4.2.3}{./Nutné a postačující podmínky optimality}\) pro případ nediferencovatelných funkcí
Také se dá říct, že koncept K-T vektorů je zobecněním Lagrangeových multiplikátorů s kvalifikovanými omezeními (kvůli \(y_0\str = 1\)) - K-T vektory splývají s multiplikátory za podmínek Věty \(\secRefAt{4.2.3}{./Nutné a postačující podmínky optimality}\)
Definice \(\secT{4.3.9}\) (Sedlový bod)
Bod \([x\str, y\str] \in P \times Q\) se nazývá sedlovým bodem Lagrangeovy funkce \(L(x,y)\) úlohy \(\knvxProg\) na \(P \times Q\), jestliže
\[L(x\str,y) \leq L(x\str, y\str) \leq L(x,y\str) \quad \forall x \in P, y \in Q,\]tj. platí
\[L(x\str,y\str) = \max_{y \in Q} L(x\str, y) = \min_{x \in P} L(x,y\str)\]Věta \(\secT{4.3.10}\) (Kuhnova-Tuckerova pro sedlový bod)
Nechť úloha \(\knvxProg\) je regulární úlohou konvexní programování (viz Věta \(\secRef{4.3.2}\)). Pak bod \(x\str \in P\) je řešením úlohy \(\knvxProg\) právě tehdy, když existuje \(y\str \in Q\) takové, že \([x\str, y\str]\) je sedlovým bodem Lagrangeovy funkce \(L(x,y)\) úlohy \(\knvxProg\) na \(P \times Q\).