Duální úloha
$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\vf{\varphi} \xdef\Tagged#1{(\text{#1})} \xdef\tagged*#1{\text{#1}} \xdef\tagEqHere#1#2{\href{#2\#eq-#1}{(\text{#1})}} \xdef\tagDeHere#1#2{\href{#2\#de-#1}{\text{#1}}} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\gradT#1{\mathrm{grad}^T #1} \xdef\gradx#1{\mathrm{grad}_x #1} \xdef\hess#1{\nabla^2\, #1} \xdef\hessx#1{\nabla^2_x #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} \xdef\iter#1{^{[#1]}} \xdef\str{^*} \xdef\spv{\mcal V} \xdef\civ{\mcal U} \xdef\knvxProg{\tagEqHere{4.1}{./nutne-a-postacujici-podminky-optimality} \, \and \, \tagEqHere{4.2}{nutne-a-postacujici-podminky-optimality}} $$
Definice $\D{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, \tag{\T{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 $\D{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ě $\tagDeHere{4.2.3}{./nutne-a-postacujici-podminky-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 $\tagDe{4.3.2}$ se nazývá regulární.
Definice $\D{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 \tag{\T{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 $\tagEq{4.3.1}$.
Úloha $\tagEq{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 $\D{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 $\tagDe{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 řeeš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 $\D{4.3.6}$ (Silná věta o dualitě)
Nechť úloha $\knvxProg$ je regulární úlohou konvexního programování (viz. Věta $\tagDe{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 $\tagEq{4.3.1}$ je neprázdná a shodná s množinou všech K-T vektorů úlohy $\knvxProg$.
Z Věty $\tagDe{4.3.6}$ vyplývá, že pokud $\knvxProg$ je regulární úlohou konvexního programování (viz Věta $\tagDe{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 $\tagDe{4.3.5}, \tagDe{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 $\D{4.3.8}$ (Kuhnova-Tuckerova v nediferenciálním tvaru)
Nechť úloha $\knvxProg$ je regulární úlohou konvexního programování (viz Věta $\tagDe{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), \tag{\T{4.3.2}}$$ $$y_i\str g_i(x\str) = 0, \quad i \in \set{1, \dots, m}, \tag{\T{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 $\tagDe{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 $\tagEq{4.3.2}$ je ekvivalentní s podmínkou $\tagEqHere{4.2.3}{./nutne-a-postacujici-podminky-optimality}$ pro $y_0\str = 1$, zatímco $\tagEq{4.3.3}$ odpovídá $\tagEqHere{4.2.4}{./nutne-a-postacujici-podminky-optimality}$.
Tedy Věta $\tagDe{4.3.8}$ je skutečně zobecnění KKT Věty $\tagDeHere{4.2.3}{./nutne-a-postacujici-podminky-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 $\tagDeHere{4.2.3}{./nutne-a-postacujici-podminky-optimality}$
Definice $\D{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 $\D{4.3.10}$ (Kuhnova-Tuckerova pro sedlový bod)
Nechť úloha $\knvxProg$ je regulární úlohou konvexní programování (viz Věta $\tagDe{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$.