Subgradient a subdiferenciál a Fenchelova transformace
Subgradient a subdiferenciál
Definice 2.5.1 (Subgradient a subdiferenciál)
Nechť X⊆Rn je konvexní množina. Vektor a∈Rn se nazývá subgradient funkce f:X→R v bodě x∗∈X, jestliže
f(x)−f(x∗)≥⟨a,x−x∗⟩(2.5.1)
pro každé x∈X. Množina všech subgradientů funkce f v bodě x∗ se nazývá subdiferenciál funkce f v bodě x∗ a značí se ∂f(x∗). Funkce f se nazývá subdiferencovatelná v bodě x∗, jestliže ∂f(x∗)=∅.
Jistě platí podle Věty 2.4.2 i gradf(x∗)∈∂f(x∗)
Speciálně, je-li f:X⊆R→R konvexní a x∗∈riX, pak podle Věty 2.4.7 existují jednostranné derivace f+′(x∗),f−′(x∗), přičemž platí f−′(x∗)≤f+′(x∗). V tomto případě pak máme
∂f(x∗)=[f−′(x∗),f+′(x∗)]
Věta 2.5.4
Nechť X⊆Rn je konvexní množina a f:X→R
- Je-li funkce f konvexní a x∗∈riX, pak ∂f(x∗) je neprázdná, uzavřená a konvexní množina
- Je-li ∂f(x) neprázdná pro každé x∈X, pak f je konvexní na X
Fenchelova transformace je transformace, která k funkci f:X⊆Rn→R přiřadí konvexní funkci f∗:Rn→R. Této přidružené funkci f∗ se v řeči optimalizace/matematického programování říká duální úloha (viz. TODO duální úloha).
Definice 2.6.1 (Fenchelova transformace)
Nechť f:Rn→R. Funkce
f∗(y):=x∈Rnsup[⟨x,y⟩−f(x)]
se nazývá Fenchelova transformace funkce f (nebo také (konvexně) konjugovanou funkcí funkce f).
Jistě f:Rn→R∪{∞} a proto definujeme ještě efektivní definiční obor D∗(f)={x∈D(f)∣f(x)<∞}
Lemma 2.6.3
Nechť je dána funkce f:X⊆Rn→R a f∗ je její Fenchelova transformace. Pak následující tvrzení jsou pravdivá:
- Funkce f∗ je konvexní na množině Y:={y∈Rn∣f∗(y)<∞}
- Pro každé x∈X a y∈Rn platí tzv. Fenchelova(-Youngova) nerovnost
f(x)+f∗(y)≥⟨x,y⟩
přičemž rovnost nastane právě tehdy, když y∈∂f(x).
- Je-li f(x)≥g(x) na X, pak f∗(y)≤g∗(y) pro všechna y∈Rn.
Věta 2.6.6 (Fenchel & Moreau)
Nechť X⊆Rn je konvexní množina a funkce f:X→R konvexní na X. Pak v každém bodě spojitosti funkce f platí tzv. Fenchelova rovnost
f∗∗=f
Jinak řečeno, druhá Fenchelova transformace ke konvexní funkci je s touto funkcí totožná, tj. f∗∗≡f pro f konvenxí. 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∗
Definice 2.6.7 (Obálka funkce)
Nechť X⊆Rn je konvexní množina a f:X→R. Potom funkce
g(x):=sup{h(x)∣h je konvexnıˊ a h(x)≤f(x)∀x∈X}
se nazývá konvexní obálka (obal) funkce f a značí se cof.
Jinak řečeno, cof je největší konvexní funkce, která je majorizována funkcí f
Jistě platí D(cof)=conv(D(f)), z čehož plyne conv(epif)⊆epi(cof)
