<div style="visibility:hidden;height:0;overflow:hidden;margin:0;padding:0">

</div>

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

kde $f\str := \inf_{x \in X} f(x)$ je hodnota úlohy $\knvxProg$.

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$.

Ú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í**.

Nechť $y \in Q$. Definujme funkci

a množinu (tzv. **efektivní definiční obor**)

Pak úloha

se nazývá ***duální úlohou*** k úloze $\knvxProg$. Číslo

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$.

Pro každé $x \in X$ a každé $y \in Q$ platí

Zejména, pokud $X \neq \emptyset$ a $Y \neq \emptyset$, pak $f\str \geq \vf\str$.

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

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$.

Jsou-li $x\str \in X$ a $y\str \in Q$ taková, že platí

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á**.

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**

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$) |

| ------------------------|-------------------------------|---------------------|-------------------------------|

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 \

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$).

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

tj. platí

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$.