Skip to main content

Konvexní funkce

\xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\tagged#1{(\text{#1})} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\hess#1{\nabla^2\, #1}

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

Nechť X⊆RnX \subseteq \R^n je konvexní množina. Funkce f:X→Rf: X \to \R se nazývá

  • konvexní na XX, jestliže pro všechna x1,x2∈Xx_1, x_2 \in X a každé λ∈[0,1]\l \in [0,1] platí
    f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)(2.2.1)f(\l x_1 + (1 - \l)x_2) \leq \l f(x_1) + (1-\l) f(x_2) \tag{\T{2.2.1}}
  • ostře konvexní na XX, jestliže nerovnost (2.2.1)\tagEq{2.2.1} je ostrá pro všechna x1,x2∈X,x1≠x2x_1, x_2 \in X, x_1 \neq x_2 a každé λ∈(0,1)\l \in (0,1).
  • silně konvexní na XX s konstantou silné konvexnosti ϑ>0\th > 0, jestliže pro všechna x1,x2∈Xx_1, x_2 \in X a každé λ∈[0,1]\l \in [0,1] platí
    f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)⏟(2.2.1)−ϑλ(1−λ)∥x1−x2∥2(2.2.2)\underbrace{f(\l x_1 + (1 - \l)x_2) \leq \l f(x_1) + (1 - \l) f(x_2)}_{\tagEq{2.2.1}} - \th \l(1-\l)\norm{x_1 - x_2}^2 \tag{\T{2.2.2}}

V praxi je silná konvexnost "silnější" než ostrá konvexnost a ta je silnější než "obyčejná" konvexnost

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

Nechť X⊆RnX \subseteq \R^n je konvexní množina a nechť f:X→Rf : X \to \R. Funkce ff je konvexní na XX právě tehdy, když její nadgraf (epigraf) epi f:={[x,β]⏟bod∈Rn+1∣x∈X,β≥f(x)} \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 yy). 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ě

ff konvexní   ⟺  \iff −f-f konkávní

Kombinace konvexních funkcí

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

Nechť X⊆RnX \subseteq \R^n je konvexní množina, funkce f1,…,fm:X→Rf_1, \dots, f_m: X \to \R jsou konvexní na XX a α1,…,αm≥0\a_1, \dots, \a_m \geq 0 jsou daná čísla. Potom F(x)=α1f1(x)+⋯+αmfm(x)F(x) = \a_1 f_1(x) + \dots + \a_m f_m(x) je konvexní.

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

Nechť X⊆RnX \subseteq \R^n je konvexní množina a f:X→Rf: X \to \R je konvexní funkce na XX. Pak pro libovolné K∈RK \in \R je odpovídající dolní vrstevnicová množina (sublevel set) VK:={x∈X∣f(x)≤K} V_K := \brackets{x \in X \mid f(x) \leq K} také konvexní.

Platí pouze tato implikace: ff konvexní   ⟹  \implies sublevel set konvexní
Například x3x^3 má konvexní sublevel set, ale sama konvexní není.

Přesněji říkáme, že pokud má funkce ff konvexní sublevel set, pak ff je kvazikonvexní.

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

Nechť X⊆RnX \subseteq \R^n je konvexní množina a funkce f:X→Rf:X \to \R je konvexní na XX. Pak pro libovolné m∈N,x1,…,xm∈Xm \in \N, x_1, \dots, x_m \in X a čísla λ1,…,λm≥0\l_1, \dots, \l_m \geq 0 splňující ∑i=1mλi=1\sum_{i = 1}^m \l_i = 1 platí f(∑i=1mλixi)≤∑i=1mλif(xi).(2.2.3) f \left( \sum_{i = 1}^m \l_i x_i \right) \leq \sum_{i = 1}^m \l_i f(x_i). \tag{\T{2.2.3}} Je-li navíc funkce ff ostře konvexní a λ1,…,λm∈(0,1)\l_1, \dots, \l_m \in (0,1), pak rovnost v (2.2.3)\tagEq{2.2.3} nastane právě tehdy, když x1=⋯=xmx_1 = \dots = x_m.

První část Věty 2.2.5 lze jistě podle Definice 2.2.1\tagDe{2.2.1} nahradit ekvivalencí

Z Jensenovy nerovnosti (2.2.3)\tagEq{2.2.3} lze odvodit například AG nerovnost
x1+⋯+xmm≤x1⋅…⋅xmm{x_1 + \dots + x_m \over m} \leq \sqrt[m]{x_1 \cdot \ldots \cdot x_m}

Lokalizace minima konvexní funkce

Věta 2.2.6\D{2.2.6}

Nechť X⊆RnX \subseteq \R^n je konvexní množina a funkce f:X→Rf: X \to \R konvexní. Potom následující tvrzení jsou pravdivá

  • Libovolné lokální minimum funkce ff na XX je současně globálním minimem.
  • Množina bodů množiny XX, v nichž funkce ff nabývá svého minima na XX, je konvexní. Je-li funkce dokonce ostře konvexní, pak je tato množina nejvýše jednoprvková.
  • Je-li funkce ff diferencovatelná na otevřené množině U⊇X\mcal U \supseteq X a x∗∈Xx^* \in X je jejím stacionárním bodem, tj. grad f(x∗)=0\grad f(x^* ) = 0, pak x∗x^* je bodem globálního minima funkce ff na množině XX.

Z Věty 2.2.6\tagDe{2.2.6} mimo jiné plyne, že je-li f:X→Rf: X \to \R (ostře) konvexní a spojitá funkce na konvexní a kompaktní množině X⊆RnX \subseteq \R^n, pak ff má na XX (právě jedno) globální minumum.

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

Máme-li konvexní funkci f:X→Rf: X \to \R na polytopu X:=conv {x1,…,xm}⊆RnX := \conv \brackets{x_1, \dots, x_m} \subseteq \R^n, pak je maximum funkce ff na XX dosaženo v některém z bodů x1,…,xmx_1, \dots, x_m.

Obecněji: je-li XX 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 XX)

Z Věty 2.2.7\tagDe{2.2.7} plyne základní věta lineárního programování:
Je-li funkce ff afinní (taková funkce je konvexní i konkávní zároveň), pak globální maximum nastává v některém z bodů x1,…,xmx_1, \dots, x_m, tj. v některém z "vrcholů" polytopu.

Vlastnosti konvexních funkcí

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

Nechť X⊆RnX \subseteq \R^n je konvexní množina a funkce f:X→Rf: X \to \R je konvexní na XX. Pak ff je spojitá pro každé x∈ri Xx \in \ri X.

Dále ještě známe několik podmínek zaručujících spojitost funkce f:R→Rf: \R \to \R:

  • má-li ff vlastní derivaci v otevřeném intervalu II, pak ff je (ostře) konvexní na II právě tehdy, když f′f' je neklesající (rostoucí) na II.
  • má-li ff vlastní derivaci v otevřeném intervalu II, pak ff je (ostře) konvexní na II právě tehdy, když pro každé x,x∗∈Ix, x^* \in I platí
    f(x)≥(>)f(x∗)+f′(x∗)(x−x∗),f(x) \geq^{(>)} f(x^* ) + f'(x^* )(x - x^* ), tj. graf funkce ff leží nad tečnou sestrojenou v libovolném bodě.
  • má-li ff vlastní druhou derivaci v otevřeném intervalu II, pak ff je konvexní na II právě tehdy, když funkce f′′(x)≥0f''(x) \geq 0 (je-li f′′(x)>0f''(x) > 0 na II, pak ostře konvexní)

Tyto tvrzení si nyní rozšiřme pro f:Rn→Rf: \R^n \to \R pro silnou konvexnost s konstatnou ϑ\th (volbou ϑ=0\th = 0 dostáváme ostrou konvexnost)

Věta 2.4.2\D{2.4.2}

Nechť X⊆RnX \subseteq \R^n je konvexní množina a funkce ff diferencovatelná na otevřené množině U⊇X\mcal U \supseteq X. Pak ff je silně konvexní na XX s konstantou silné konvexnosti ϑ≥0\th \geq 0 právě tehdy, když pro každé x,x∗∈Xx, x^* \in X platí f(x)≥f(x∗)+⟨grad f(x∗),x−x∗⟩+ϑ∥x−x∗∥2(2.4.1) f(x) \geq f(x^* ) + \scal {\grad f(x^* )} {x - x^* } + \th \norm{x - x^* }^2 \tag{\T{2.4.1}}

Ve (2.4.1)\tagEq{2.4.1} výraz ⟨grad f(x∗),x−x∗⟩\scal {\grad f(x^* )} {x - x^* } hraje úlohu tečné nadroviny v bodě x∗x^* s normálovým vektorem grad f(x∗)\grad f(x^* ) (tečným jak na nadrovinu, tak na funkci ff v bodě x∗x^* )

Důsledek 2.4.5\D{2.4.5}

Nechť X⊆RnX \subseteq \R^n je konvexní množina splňující int X≠∅\interior X \neq \emptyset. Nechť funkce f:X→Rf: X \to \R je dvakrát spojitě diferencovatelná na otevřené množině U⊇X\mcal U \supseteq X s maticí druhých derivací ∇2 f(x)\hess f(x) (Hessova matice). Pak ff je silně konvexní na XX s konstantou silné konvexnosti ϑ≥0\th \geq 0 právě tehdy, když pro každé x∈Xx \in X a h∈Rnh \in \R^n platí ⟨∇2 f(x),h⟩≥2ϑ∥h∥2,(2.4.3) \scal {\hess f(x)} h \geq 2 \th \norm{h}^2 \tag{\T{2.4.3}}, jinými slovy ∇2 f(x)≥2ϑI\hess f(x) \geq 2 \th I pro všechna x∈Xx \in X.

Z Důsledku 2.4.5\tagDe{2.4.5} plynou následující tři implikace

  • ∇2 f(x)≥0\hess f(x) \geq 0 pro všechna x∈X  ⟹  fx \in X \implies f je konvexní na XX
  • ∇2 f(x)>0\hess f(x) > 0 pro všechna x∈X  ⟹  fx \in X \implies f je ostře konvexní na XX
  • $\intinterior X \neq \emptyseta a fjekonvexnıˊna je konvexní na X \implies \hess f(x) \geq 0provsˇechna pro všechna x \in X$
Back to top