# 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.  > 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$