# Duální úloha <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{\eqRefAt}{2}{\href{#2\#eq-#1}{(\text{#1})}} \letThereBe{\secRefAt}{2}{\href{#2\#sec-#1}{(\text{#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{\vf}{\varphi} \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{\knvxProg}{\eqRefAt{4.1}{./Nutné a postačující podmínky optimality} \, \and \, \eqRefAt{4.2}{./Nutné a postačující podmínky optimality}} \letThereBe{\set}{1}{\left\{ #1 \right\}} ``` </div> ##### **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 ```math 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**: 1. **(Slaterova)** $k = m$ a existuje $\bar x \in P$ takové, že $g_i(\bar x) < 0$ pro $i = 1, \dots, m$ 2. **(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 ```math \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**) ```math Y := \set{y \in Q \mid \vf(y) > -\infty}. ``` Pak úloha ```math \vf(y) \to \max, \qquad y \in Y \eqT{4.3.1} ``` se nazývá ***duální úlohou*** k úloze $\knvxProg$. Číslo ```math \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í ```math 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 ```math 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í ```math 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** ```math 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 1. jestliže $Y \neq \emptyset$, pak **duální úloha je řešitelná** a $f\str > -\infty$ 2. 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: 1. existuje $y\str \in Q$ takové, že $f(x\str) = \vf(y\str)$ 2. existuje $y\str \in Q$ takové, že \ ```math L(x\str,y\str) = \min_{x \in P}L(x, y\str), \eqT{4.3.2} ``` ```math 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 ```math 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í ```math 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$.