Subgradient a subdiferenciál a Fenchelova transformace

\[\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{\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{\hess}{1}{\nabla^2\, #1}\]\[\letThereBe{\subdif}{1}{\partial #1} \letThereBe{\co}{1}{\mathrm{co}\, #1}\]\[\letThereBe{\iter}{1}{^{[#1]}}\]\[\letThereBe{\set}{1}{\left\{ #1 \right\}}\]

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

\[f(x) - f(x^*) \geq \scal a {x - x^*} \eqT{2.5.1}\]

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}{./Konvexní 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 2.5.7 (viz prezentace) existují jednostranné derivace \(f'_ +(x^*), f'_ -(x^*)\), přičemž platí \(f'_ -(x^*) \leq f'_ +(x^*)\). V tomto případě pak máme

\[\subdif f(x^*) = [f'_ -(x^*), f'_ +(x^*)]\]

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}{./Duální úloha}\)).

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

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

\[f^*(y) := \sup_{x \in \R^n} [\scal x y - f(x)]\]

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

\[f^{**} = f\]

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

\[g(x) := \sup \set{h(x) \mid h \text{ je konvexní a } h(x) \leq f(x) \; \forall x \in X}\]

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

Konvexní obálka

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í

\[\co f(x) = f^{* * }(x)\]