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

</div>

**Úlohou matematického programování** nazveme

kde **přípustná množina** $X$ je zadána systém rovností a nerovností

Omezení zakomponovaná v $P$ se nazývají **přímá**, naopak omezení ve formě $g_l$ se nazývají **funkcionální**. Dále definujme

- je to **kužel**

- **množinu spádových vektorů** (**kužel zlepšujících vektorů**)

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

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

pro každé $x \in X$.

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.

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

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

pro všechna $x \in X$ taková, že $\gradT f(x^*)(x - x^*) = 0$, tj. pro vektory $(x - x^*)\in \ker\gradT f(x^*)$

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

(tj. je to **stacionární bod** ve smyslu Definice $\secRef{4.1.2}$), množina $X$ je **polyedr** a platí

pro všechna $x \in X$ taková, že $x \neq x^*$ a $(x - x^*) \in \ker \gradT f(x^*)$

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

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

Dále ještě zaveďme následující

a dvě další množiny:

- **Množinu aktivních omezení** v bodě $x\str$

- **Množinu indexů** všech funkcí, které se v bodě $x\str$ realizují jako rovnost

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í

---

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

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

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

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

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.

Jestliže

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