Subgradient a subdiferenciál a Fenchelova transformace

Subgradient a subdiferenciál

Definice \(\secT{2.5.1}\) (Subgradient a subdiferenciál)

Nechť \(X \subseteq \R^n\) je konvexní množina. Vektor \(a \in \R^n\) se nazývá subgradient funkce \(f: X \to \R\) v bodě \(x^* \in X\), jestliže

pro každé \(x \in X\). Množina všech subgradientů funkce \(f\) v bodě $x^* $ se nazývá subdiferenciál funkce \(f\) v bodě $x^* $ a značí se \(\subdif f(x^* )\). Funkce \(f\) se nazývá subdiferencovatelná v bodě $x^* $, jestliže \(\subdif f(x^* ) \neq \emptyset\).

Jistě platí podle Věty \(\secRefAt{2.4.2}{./konvexni-funkce}\) i \(\grad f(x^* ) \in \subdif f(x^* )\)

Speciálně, je-li \(f:X \subseteq \R \to \R\) konvexní a \(x^* \in \ri X\), pak podle Věty \(\secRefAt{2.4.7}{./konvexni-funkce}\) existují jednostranné derivace \(f'_ +(x^* ), f'_ -(x^* )\), přičemž platí \(f'_ -(x^* ) \leq f'_ +(x^* )\). V tomto případě pak máme

Věta \(\secT{2.5.4}\)

Nechť \(X \subseteq \R^n\) je konvexní množina a \(f: X \to \R\)

• Je-li funkce \(f\) konvexní a \(x^* \in \ri X\), pak \(\subdif f(x^* )\) je neprázdná, uzavřená a konvexní množina
• Je-li \(\subdif f(x)\) neprázdná pro každé \(x \in X\), pak \(f\) je konvexní na \(X\)

Fenchelova transformace

Fenchelova transformace je transformace, která k funkci \(f: X \subseteq \R^n \to \R\) přiřadí konvexní funkci \(f^* : \R^n \to \R\). Této přidružené funkci $f^* $ se v řeči optimalizace/matematického programování říká duální úloha (viz Definice \(\secRefAt{4.3.3}{./dualni-uloha}\)).

Definice \(\secT{2.6.1}\) (Fenchelova transformace)

Nechť \(f: \R^n \to \R\). Funkce

se nazývá Fenchelova transformace funkce \(f\) (nebo také (konvexně) konjugovanou funkcí funkce \(f\)).

Jistě \(f: \R^n \to \R \cup \set{\infty}\) a proto definujeme ještě efektivní definiční obor \(D^* (f) = \set{x \in D(f) \mid f(x) < \infty}\)

Lemma \(\secT{2.6.3}\)

Nechť je dána funkce \(f: X \subseteq \R^n \to \R\) a $f^* $ je její Fenchelova transformace. Pak následující tvrzení jsou pravdivá:

• Funkce $f^* $ je konvexní na množině \(Y := \set{y \in \R^n \mid f^* (y) < \infty}\)

• Pro každé \(x \in X\) a \(y \in \R^n\) platí tzv. Fenchelova(-Youngova) nerovnost

  \[f(x) + f^* (y) \geq \scal x y\]

  přičemž rovnost nastane právě tehdy, když \(y \in \subdif f(x)\).

• Je-li \(f(x) \geq g(x)\) na \(X\), pak \(f^* (y) \leq g^* (y)\) pro všechna \(y \in \R^n\).

Věta \(\secT{2.6.6}\) (Fenchel & Moreau)

Nechť \(X \subseteq \R^n\) je konvexní množina a funkce \(f: X \to \R\) konvexní na \(X\). Pak v každém bodě spojitosti funkce \(f\) platí tzv. Fenchelova rovnost

Jinak řečeno, druhá Fenchelova transformace ke konvexní funkci je s touto funkcí totožná, tj. \(f^{**} \equiv f\) pro \(f\) konvexní. Navíc jelikož $f^* $ je vždy konvexní, tak dostáváme, že počítat třetí Fenchelovu transformaci \(f^{* * * }\) nemá smysl, protože bude totožná s první Fenchelovou transformací $f^* $

Definice \(\secT{2.6.7}\) (Obálka funkce)

Nechť \(X \subseteq \R^n\) je konvexní množina a \(f: X \to \R\). Potom funkce

se nazývá konvexní obálka (obal) funkce \(f\) a značí se \(\co f\).

Jinak řečeno, \(\co f\) je největší konvexní funkce, která je majorizována funkcí \(f\)

Jistě platí \(D(\co f) = \conv (D (f))\), z čehož plyne \(\conv (\epi f) \subseteq \epi (\co f)\)

Zde \(\conv (\epi f) = \epi {|x|} \setminus \set{0}\), ale \(0 \in \epi (\co f)\)

Věta \(\secT{2.6.9}\)

Nechť \(X \subseteq \R^n\) je konvexní množina a \(f: X \to \R\). Potom pro každé \(x \in \ri X\) platí