Home A - Z
Page Index

An Otter Wiki

Commit 4c40b6

2026-03-27 23:06:48 Štěpán Zapadlo: Add convex functions
/dev/null .. matematické programování/konvexní funkce.md
@@ 0,0 1,164 @@
+ # Konvexní funkce
+
+ # Konvexní funkce
+
+ <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{\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>
+
+ ##### **Definice** $\secT{2.2.1}$ (Konvexní funkce)
+ Nechť $X \subseteq \R^n$ je **konvexní** množina. Funkce $f: X \to \R$ se nazývá
+ - **konvexní** na $X$, jestliže pro všechna $x_1, x_2 \in X$ a každé $\l \in [0,1]$ platí
+
+ ```math
+ f(\l x_1 + (1 - \l)x_2) \leq \l f(x_1) + (1-\l) f(x_2) \eqT{2.2.1}
+ ```
+
+ - **ostře konvexní** na $X$, jestliže nerovnost $\eqRef{2.2.1}$ je **ostrá** pro všechna $x_1, x_2 \in X, x_1 \neq x_2$ a každé $\l \in (0,1)$.
+ - **silně konvexní** na $X$ s **konstantou silné konvexnosti** $\th > 0$, jestliže pro všechna $x_1, x_2 \in X$ a každé $\l \in [0,1]$ platí
+
+ ```math
+ \underbrace{f(\l x_1 + (1 - \l)x_2) \leq \l f(x_1) + (1 - \l) f(x_2)}_{\eqRef{2.2.1}} - \th \l(1-\l)\norm{x_1 - x_2}^2 \eqT{2.2.2}
+ ```
+
+ > V praxi je **silná** konvexnost "silnější" než **ostrá** konvexnost a ta je silnější než "*obyčejná*" konvexnost
+
+ ##### **Věta** $\secT{2.2.2}$ (Konvexnost nadgrafu)
+ Nechť $X \subseteq \R^n$ je *konvexní* množina a nechť $f : X \to \R$. Funkce $f$ je **konvexní** na $X$ právě tehdy, když její **nadgraf** (**epigraf**)
+
+ $$\epi f := \brackets{\underbrace{[x, \beta]}_{\text{bod}} \in \R^{n+1} \mid x \in X, \beta \geq f(x)}$$
+
+ je **konvexní** množina.
+
+ ---
+
+ Pro **ostře** konvexní funkci musí "tyto dva body" vždy ležet nad sebou (myšleny jejich souřadnice na ose $y$). Navíc pro **silnou** konvexnost mezi nimi musí vždy být alespoň daná mezera.
+ <center>
+ <div drawio-diagram="20"><img src="https://bookstack.zapadlo.name/uploads/images/drawio/2022-12/drawing-3-1672408884.png"></div>
+ </center>
+
+ > Tyto body **nemusí** ležet nad sebou (na svislé přímce). Navíc ještě
+ >
+ > $f$ **konvexní** $\iff$ $-f$ **konkávní**
+
+ ### Kombinace konvexních funkcí
+
+ ##### **Věta** $\secT{2.2.3}$ (Nezáporná linearní kombinace konvexních funkcí)
+ Nechť $X \subseteq \R^n$ je konvexní množina, funkce $f_1, \dots, f_m: X \to \R$ jsou konvexní na $X$ a $\a_1, \dots, \a_m \geq 0$ jsou daná čísla. Potom $F(x) = \a_1 f_1(x) + \dots + \a_m f_m(x)$ je **konvexní**.
+
+ ##### **Věta** $\secT{2.2.4}$ (*Sublevel set*)
+ Nechť $X \subseteq \R^n$ je konvexní množina a $f: X \to \R$ je *konvexní* funkce na $X$. Pak pro libovolné $K \in \R$ je odpovídající **dolní vrstevnicová množina** (***sublevel set***)
+
+ $$V_K := \brackets{x \in X \mid f(x) \leq K}$$
+
+ také **konvexní**.
+
+ > Platí pouze tato implikace: $f$ ***konvexní*** $\implies$ *sublevel set **konvexní*** \
+ > Například $x^3$ má konvexní *sublevel set*, ale sama konvexní **není**.
+
+ Přesněji říkáme, že pokud má funkce $f$ **konvexní** *sublevel set*, pak $f$ je **kvazikonvexní**.
+
+ ##### **Věta** $\secT{2.2.5}$ (Jensen)
+ Nechť $X \subseteq \R^n$ je konvexní množina a funkce $f:X \to \R$ je konvexní na $X$. Pak pro libovolné $m \in \N, x_1, \dots, x_m \in X$ a čísla $\l_1, \dots, \l_m \geq 0$ splňující $\sum_{i = 1}^m \l_i = 1$ platí
+
+ $$f \left( \sum_{i = 1}^m \l_i x_i \right) \leq \sum_{i = 1}^m \l_i f(x_i). \eqT{2.2.3}$$
+
+ Je-li navíc funkce $f$ **ostře konvexní** a $\l_1, \dots, \l_m \in (0,1)$, pak rovnost v $\eqRef{2.2.3}$ nastane *právě tehdy*, když $x_1 = \dots = x_m$.
+
+ > První část **Věty** $\secRef{2.2.5}$ lze jistě podle **Definice** $\secRef{2.2.1}$ nahradit ekvivalencí
+
+ > Z Jensenovy nerovnosti $\eqRef{2.2.3}$ lze odvodit například **AG nerovnost** \
+ > $${x_1 + \dots + x_m \over m} \leq \sqrt[m]{x_1 \cdot \ldots \cdot x_m}$$
+
+ ### Lokalizace minima konvexní funkce
+
+ ##### **Věta** $\secT{2.2.6}$
+ Nechť $X \subseteq \R^n$ je konvexní množina a funkce $f: X \to \R$ konvexní. Potom následující tvrzení jsou pravdivá
+ - Libovolné **lokální minimum** funkce $f$ na $X$ je současně **globálním minimem**.
+ - Množina bodů množiny $X$, v nichž funkce $f$ nabývá svého **minima** na $X$, je **konvexní**. Je-li funkce dokonce **ostře konvexní**, pak je tato množina **nejvýše jednoprvková**.
+ - Je-li funkce $f$ **diferencovatelná** na **otevřené** množině $\mcal U \supseteq X$ a $x^* \in X$ je jejím **stacionárním bodem**, tj. $\grad f(x^* ) = 0$, pak $x^* $ je bodem **globálního minima** funkce $f$ na množině $X$.
+
+ ---
+
+ Z Věty $\secRef{2.2.6}$ mimo jiné plyne, že je-li $f: X \to \R$ (*ostře*) konvexní a **spojitá** funkce na konvexní a **kompaktní** množině $X \subseteq \R^n$, pak $f$ má na $X$ (*právě jedno*) **globální minumum**.
+
+ -----
+
+ ##### **Věta** $\secT{2.2.7}$ (Základní věta konvexního programování)
+ Máme-li konvexní funkci $f: X \to \R$ na polytopu $X := \conv \brackets{x_1, \dots, x_m} \subseteq \R^n$, pak je maximum funkce $f$ na $X$ dosaženo v některém z bodů $x_1, \dots, x_m$.
+
+ **Obecněji:** je-li $X$ konvexní a **kompaktní** množina, pak maximum nastává v **extrémním bodě** (tj. v takovém bodě, který **není netriviální** konvexní kombinací dvou bodů z $X$)
+
+ > Z Věty $\secRef{2.2.7}$ plyne **základní věta lineárního programování**: \
+ > Je-li funkce $f$ **afinní** (taková funkce je konvexní i konkávní zároveň), pak **globální maximum** nastává v některém z bodů $x_1, \dots, x_m$, tj. v některém z **"vrcholů" polytopu**.
+
+ ### Vlastnosti konvexních funkcí
+
+ ##### **Věta** $\secT{2.4.1}$ (Spojitost konvexní funkce)
+ Nechť $X \subseteq \R^n$ je konvexní množina a funkce $f: X \to \R$ je konvexní na $X$. Pak $f$ je **spojitá** pro každé $x \in \ri X$.
+
+ ---
+
+ Dále ještě známe několik podmínek zaručujících konvexnost funkce $f: \R \to \R$:
+ - má-li $f$ *vlastní* derivaci v **otevřeném** intervalu $I$, pak $f$ je (*ostře*) konvexní na $I$ právě tehdy, když $f'$ je **neklesající** (***rostoucí***) na $I$.
+ - má-li $f$ *vlastní* derivaci v **otevřeném** intervalu $I$, pak $f$ je (*ostře*) konvexní na $I$ právě tehdy, když pro každé $x, x^* \in I$ platí
+
+ ```math
+ f(x) \geq^{(>)} f(x^* ) + f'(x^* )(x - x^* ),
+ ```
+
+ tj. graf funkce $f$ leží **nad tečnou** sestrojenou v **libovolném** bodě.
+ - má-li $f$ vlastní **druhou** derivaci v **otevřeném** intervalu $I$, pak $f$ je konvexní na $I$ právě tehdy, když funkce $f''(x) \geq 0$ (je-li $f''(x) > 0$ na $I$, pak **ostře konvexní**)
+
+ Tyto tvrzení si nyní rozšiřme pro $f: \R^n \to \R$ pro **silnou** konvexnost s konstatnou $\th$ (volbou $\th = 0$ dostáváme **ostrou** konvexnost)
+
+ ##### **Věta** $\secT{2.4.2}$
+ Nechť $X \subseteq \R^n$ je konvexní množina a funkce $f$ diferencovatelná na otevřené množině $\mcal U \supseteq X$. Pak $f$ je **silně** konvexní na $X$ s konstantou **silné** konvexnosti $\th \geq 0$ právě tehdy, když pro každé $x, x^* \in X$ platí
+
+ $$f(x) \geq f(x^* ) + \scal {\grad f(x^* )} {x - x^* } + \th \norm{x - x^* }^2 \eqT{2.4.1}$$
+
+ > Ve $\eqRef{2.4.1}$ výraz $\scal {\grad f(x^* )} {x - x^* }$ hraje úlohu **tečné nadroviny** v bodě $x^* $ s **normálovým vektorem** $\grad f(x^* )$ (tečným jak na nadrovinu, tak na funkci $f$ v bodě $x^* $)
+ >
+ > Ještě jinými slovy je z Věty $\secRef{2.4.2}$ plyne, že nadrovina daná $\scal {\grad f(x) - \grad f(x^* )} {x - x^* } \geq \th \norm{x - x^* }^2$ **opěrnou nadrovinou** pro $\epi f$
+
+ ##### **Důsledek** $\secT{2.4.5}$
+ Nechť $X \subseteq \R^n$ je konvexní množina splňující $\interior X \neq \emptyset$. Nechť funkce $f: X \to \R$ je *dvakrát* spojitě diferencovatelná na **otevřené** množině $\mcal U \supseteq X$ s maticí druhých derivací $\hess f(x)$ (*Hessova matice*). Pak $f$ je **silně** konvexní na $X$ s konstantou silné konvexnosti $\th \geq 0$ právě tehdy, když pro každé $x \in X$ a $h \in \R^n$ platí
+
+ $$\scal {\hess f(x)} h \geq 2 \th \norm{h}^2 \eqT{2.4.3},$$
+
+ jinými slovy $\hess f(x) \geq 2 \th I$ pro všechna $x \in X$.
+
+ ---
+
+ Z Důsledku $\secRef{2.4.5}$ plynou následující tři implikace
+ - $\hess f(x) \geq 0$ pro všechna $x \in X \implies f$ je konvexní na $X$
+ - $\hess f(x) > 0$ pro všechna $x \in X \implies f$ je **ostře** konvexní na $X$
+ - $\interior X \neq \emptyset$ a $f$ je konvexní na $X \implies \hess f(x) \geq 0$ pro všechna $x \in X$
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9