Skip to main content

Subgradient a subdiferenciál a Fenchelova transformace

$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\tagged#1{(\text{#1})} \xdef\tagged*#1{\text{#1}} \xdef\tagEqHere#1#2{\href{#2\#eq-#1}{(\text{#1})}} \xdef\tagDeHere#1#2{\href{#2\#de-#1}{\text{#1}}} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\hess#1{\nabla^2\, #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} $$

Subgradient a subdiferenciál

Definice $\D{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^* } \tag{\T{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 $\tagDeHere{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 $\tagDeHere{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 $$ \subdif f(x^* ) = [f'_ -(x^* ), f'_ +(x^* )] $$

Věta $\D{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 $\tagDeHere{4.3.3}{./dualni-uloha}$).

Definice $\D{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 $\D{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 $\D{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 $\D{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)$

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

Věta $\D{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) $$

Back to top