Konvexní funkce

\[\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\}}\]

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í
\[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í
\[\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í
\[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$

Konvexní funkce

Konvexní funkce

Definice \(\secT{2.2.1}\) (Konvexní funkce)

Věta \(\secT{2.2.2}\) (Konvexnost nadgrafu)

Kombinace konvexních funkcí

Věta \(\secT{2.2.3}\) (Nezáporná linearní kombinace konvexních funkcí)

Věta \(\secT{2.2.4}\) (Sublevel set)

Věta \(\secT{2.2.5}\) (Jensen)

Lokalizace minima konvexní funkce

Věta \(\secT{2.2.6}\)

Věta \(\secT{2.2.7}\) (Základní věta konvexního programování)

Vlastnosti konvexních funkcí

Věta \(\secT{2.4.1}\) (Spojitost konvexní funkce)

Věta \(\secT{2.4.2}\)

Důsledek \(\secT{2.4.5}\)