Commit 9a9648
2026-03-27 23:10:14 Štěpán Zapadlo: Add subgradient| /dev/null .. matematické programování/subgradient a subdiferenciál a fenchelova transformace.md | |
| @@ 0,0 1,109 @@ | |
| + | # 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}{./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 |
| + | |
| + | $$\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}{./dualni-uloha}$). |
| + | |
| + | ##### **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)$ |
| + | |
| + | <center> |
| + | <div drawio-diagram="23"><img src="https://bookstack.zapadlo.name/uploads/images/drawio/2022-12/drawing-3-1672502639.png"></div> |
| + | </center> |
| + | |
| + | 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)$$ |