Home A - Z
Page Index

An Otter Wiki

Blame

9a9648 Štěpán Zapadlo 2026-03-27 23:10:14
Add subgradient
1 
# Subgradient a subdiferenciál a Fenchelova transformace
2
3
<div style="visibility:hidden;height:0;overflow:hidden;margin:0;padding:0">
4
5
```math
6
\newcommand{\LetThereBe}[2]{\newcommand{#1}{#2}} \newcommand{\letThereBe}[3]{\newcommand{#1}[#2]{#3}}
7
\letThereBe{\addTag}{2}{\cssId{#1-#2}{\tag{#2}}} \letThereBe{\addLabel}{2}{\cssId{#1-#2}{\text{#2}}} \letThereBe{\refTag}{2}{\href{###1-#2}{(\text{#2})}}
8
\letThereBe{\eqT}{1}{\addTag{eq}{#1}}\letThereBe{\secT}{1}{\addLabel{sec}{#1}}
9
\letThereBe{\eqRef}{1}{\refTag{eq}{#1}} \letThereBe{\secRef}{1}{\refTag{sec}{#1}}
10
\letThereBe{\eqRefAt}{2}{\href{#2\#eq-#1}{(\text{#1})}}
11
\letThereBe{\secRefAt}{2}{\href{#2\#sec-#1}{(\text{#1})}}
12
\LetThereBe{\R}{\mathbb{R}} \LetThereBe{\N}{\mathbb{N}}
13
\letThereBe{\rcases}{1}{\left.\begin{align}#1\end{align}\right\}}
14
\letThereBe{\rcasesAt}{2}{\left.\begin{alignat}{#1}#2\end{alignat}\right\}}
15
\letThereBe{\lcases}{1}{\begin{cases}#1\end{cases}}
16
\letThereBe{\lcasesAt}{2}{\left\{\begin{alignat}{#1}#2\end{alignat}\right.}
17
\letThereBe{\scal}{2}{\langle #1, #2 \rangle} \letThereBe{\norm}{1}{\left\lVert #1 \right\rVert} \LetThereBe{\dist}{\rho}
18
\LetThereBe{\and}{\&}\letThereBe{\brackets}{1}{\left\{ #1 \right\}}
19
\letThereBe{\parc}{2}{\frac {\partial #1}{\partial #2}}
20
\letThereBe{\mtr}{1}{\begin{pmatrix}#1\end{pmatrix}}
21
\letThereBe{\bm}{1}{\boldsymbol{#1}} \letThereBe{\mcal}{1}{\mathcal{#1}}
22
\letThereBe{\vv}{1}{\mathbf{#1}}\letThereBe{\vvp}{1}{\pmb{#1}}
23
\LetThereBe{\ve}{\varepsilon} \LetThereBe{\l}{\lambda} \LetThereBe{\th}{\vartheta} \LetThereBe{\a}{\alpha}
24
\letThereBe{\conv}{1}{\mathrm{conv}\, #1} \letThereBe{\cone}{1}{\mathrm{cone}\, #1}
25
\letThereBe{\aff}{1}{\mathrm{aff}\, #1} \letThereBe{\lin}{1}{\mathrm{Lin}\, #1} \letThereBe{\span}{1}{\mathrm{span}\, #1}
26
\LetThereBe{\O}{\mathcal O}
27
\letThereBe{\ri}{1}{\mathrm{ri}\, #1} \letThereBe{\rd}{1}{\mathrm{r}\partial\, #1} \letThereBe{\interior}{1}{\mathrm{int}\, #1}
28
\LetThereBe{\proj}{\Pi} \letThereBe{\epi}{1}{\mathrm{epi}\, #1}
29
\letThereBe{\grad}{1}{\mathrm{grad}\, #1} \letThereBe{\hess}{1}{\nabla^2\, #1}
30
\letThereBe{\subdif}{1}{\partial #1} \letThereBe{\co}{1}{\mathrm{co}\, #1}
31
\letThereBe{\iter}{1}{^{[#1]}}
32
\letThereBe{\set}{1}{\left\{ #1 \right\}}
33
```
34
35
</div>
36
37
### Subgradient a subdiferenciál
38
39
##### **Definice** $\secT{2.5.1}$ (Subgradient a subdiferenciál)
40
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
41
42
$$f(x) - f(x^* ) \geq \scal a {x - x^* } \eqT{2.5.1}$$
43
44
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$.
45
46
> Jistě platí podle Věty $\secRefAt{2.4.2}{./konvexni-funkce}$ i $\grad f(x^* ) \in \subdif f(x^* )$
47
48
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
49
50
$$\subdif f(x^* ) = [f'_ -(x^* ), f'_ +(x^* )]$$
51
52
##### **Věta** $\secT{2.5.4}$
53
Nechť $X \subseteq \R^n$ je konvexní množina a $f: X \to \R$
54
- Je-li funkce $f$ **konvexní** a $x^* \in \ri X$, pak $\subdif f(x^* )$ je **neprázdná, uzavřená** a **konvexní** množina
55
- Je-li $\subdif f(x)$ **neprázdná** pro každé $x \in X$, pak $f$ je **konvexní** na $X$
56
57
### Fenchelova transformace
58
59
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}$).
60
61
##### **Definice** $\secT{2.6.1}$ (Fenchelova transformace)
62
Nechť $f: \R^n \to \R$. Funkce
63
64
$$f^* (y) := \sup_{x \in \R^n} [\scal x y - f(x)]$$
65
66
se nazývá **Fenchelova transformace** funkce $f$ (nebo také **(konvexně) konjugovanou funkcí** funkce $f$).
67
68
> 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}$
69
70
##### **Lemma** $\secT{2.6.3}$
71
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á:
72
- Funkce $f^* $ je konvexní na množině $Y := \set{y \in \R^n \mid f^* (y) < \infty}$
73
- Pro každé $x \in X$ a $y \in \R^n$ platí tzv. *Fenchelova(-Youngova) nerovnost*
74
75
```math
76
f(x) + f^* (y) \geq \scal x y
77
```
78
79
přičemž **rovnost nastane** právě tehdy, když $y \in \subdif f(x)$.
80
- Je-li $f(x) \geq g(x)$ na $X$, pak $f^* (y) \leq g^* (y)$ pro všechna $y \in \R^n$.
81
82
##### **Věta** $\secT{2.6.6}$ (Fenchel & Moreau)
83
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*
84
85
$$f^{** } = f$$
86
87
> 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^* $
88
89
##### **Definice** $\secT{2.6.7}$ (Obálka funkce)
90
Nechť $X \subseteq \R^n$ je konvexní množina a $f: X \to \R$. Potom funkce
91
92
$$g(x) := \sup \set{h(x) \mid h \text{ je konvexní a } h(x) \leq f(x) \; \forall x \in X}$$
93
94
se nazývá **konvexní obálka (obal) funkce** $f$ a značí se $\co f$.
95
96
> Jinak řečeno, $\co f$ je **největší** konvexní funkce, která je **majorizována** funkcí $f$
97
98
Jistě platí $D(\co f) = \conv (D (f))$, z čehož plyne $\conv (\epi f) \subseteq \epi (\co f)$
99
100
<center>
101
<div drawio-diagram="23"><img src="https://bookstack.zapadlo.name/uploads/images/drawio/2022-12/drawing-3-1672502639.png"></div>
102
</center>
103
104
Zde $\conv (\epi f) = \epi {|x|} \setminus \set{0}$, ale $0 \in \epi (\co f)$
105
106
##### **Věta** $\secT{2.6.9}$
107
Nechť $X \subseteq \R^n$ je konvexní množina a $f: X \to \R$. Potom pro každé $x \in \ri X$ platí
108
109
$$\co f(x) = f^{* * }(x)$$