# Subgradient a subdiferenciál a Fenchelova transformace <div style="visibility:hidden;height:0;overflow:hidden;margin:0;padding:0"> ```math \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\}} ``` </div> ### 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* ```math 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)$  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)$$