Subdiferenciály a jejich role v optimalizaci
Milan Hladík
Katedra aplikované matematiky, Matematicko-fyzikální fakulta,
Univerzita Karlova, Praha, https://kam.mff.cuni.cz/~hladik
4. listopadu 2020
Motivace
Konvexní funkce hladká a nehladká.
Subgradient a subdiferenciál
Definice
Buď f :Rn→Rkonvexní. Subgradientemfunkce f(x) v bodě x0 ∈Rnje vektorg ∈Rn splňující
f(x)≥f(x0) +gT(x−x0), ∀x ∈Rn. Subdiferenciál ∂f(x0) je množina všech subgradientů.
◮ subgradient je normálou tečné nadroviny ke grafu f(x) v x0
◮ pro hladkou funkci pojem gradientu a subgradientu splývají a subdiferenciál je jednobodová množina
◮ Pro řadu metod nehladké konvexní optimalizace stačí najít subgradient, což lze většinou snadno. Pokud chceme ale vyjádřit podmínky optimality, potřebujeme celý subdiferenciál, a ten bývá obecně obtížné spočítat.
Příklad
Pro f(x) =|x|je∂f(0) = [−1,1].
Vlastnosti
f(x)≥f(x0) +gT(x−x0)∀xPozorování
Subdiferenciál konvexní funkce f:Rn→Rv bodě x0∈Rnje uzavřená konvexní množina.
Důkaz.
Je to průnik poloprostorů.
Subdiferenciál splňuje základní řetízková pravidla:
∂(αf(x)) =α∂f(x), α >0,
∂(f(x) +g(x)) =∂f(x) +∂g(x),
∂(f(Ax+b)) =AT(∂f)(Ax+b).
Vlastnosti
f(x)≥f(x0) +gT(x−x0)∀xTvrzení
Pro konvexní funkce f1, . . . ,fm:Rn→Rv boděx0 ∈Rn je
∂max{f1(x0), . . . ,fm(x0)}=conv ∪k∈I(x0)∂fk(x0), kde množina aktivních podmínek I(x0) = arg maxk=1,...,m{fk(x0)}. Důkaz (jen “⊇” ).
Buď λk ≥0,P
k∈I(x0)λk =1,gk ∈∂fk(x0). Pak fk(x)≥fk(x0) +gkT(x−x0), ∀x∈Rn, z čehož váženým součtem
maxk {fk(x)} ≥ X
k∈I(x0)
λkfk(x)≥max
k {fk(x0)}+ X
k∈I(x0)
λkgkT(x−x0), ∀x
Příklad
Funkce f(x) = maxk=1,...,m(aTkx+bk) v boděx0 má subdiferenciál
∂f(x0) =conv{ak;∈I(x0)}.
Vlastnosti
f(x)≥f(x0) +gT(x−x0)∀xTvrzení
Buď h:Rm→Rkonvexní a v každé složce neklesající funkce a g1, . . . ,gm:Rn→Rkonvexní funkce. Pak pro subdiferenciál složené funkce f(x) =h(g(x)) boděx0 ∈Rn platí
∂h(g(x0))T ⊇∂h(y0)T∂g(x0)T, kde y0 :=g(x0).
Důkaz.
Buď vgk ∈∂gk(x0) ∀k avh∈∂h(y0). Pak f(x) =h(g1(x), . . . ,gm(x))
≥h g1(x0) +vgT1(x−x0), . . . ,gm(x0) +vgTm(x−x0)
≥h(g1(x0), . . . ,gm(x0)) +vhT vgT1(x−x0), . . . ,vgTm(x−x0)T
=f(x0) +
m
X
k=1
(vh)kvgT
k(x−x0) Tudíž (vg1 | · · · |vgk)vh∈∂f(x0).
Vlastnosti
f(x)≥f(x0) +gT(x−x0)∀xPříklady funkcí f:R+→R, které nemají subdiferenciál v bodě x0 =0:
◮ f(x) =1 pro x=0 a f(x) =0 prox >0,
◮ f(x) =−√x.
Na druhou stranu, pokud x0 náleží do topologického vnitřku definičního oboru funkce f(x), pak subdiferenciál v boděx0 je neprázdný.
Subdiferenciál normy
f(x)≥f(x0) +gT(x−x0)∀xDefinice
Buď k · k:Rn→Rnorma. Pak k ní duální normak · k∗ je definovaná předpisem
kxk∗ = max{xTy;kyk ≤1}.
◮ kxkp je duální kkxkq pro p1 +q1 =1.
◮ Speciálně, eukleidovská norma je samo-duální.
◮ Jako limitní případ, součtová norma kxk1 je duální k maximovékxk∞ a naopak.
Tvrzení (Subdiferenciál normy)
∂kx0k={y ∈Rn;yTx0 =kx0k, kyk∗ ≤1}.
Subdiferenciál normy
f(x)≥f(x0) +gT(x−x0)∀xTvrzení (Subdiferenciál normy)
∂kx0k={y ∈Rn;yTx0 =kx0k, kyk∗ ≤1}.
Důkaz.
Podle definice, g ∈Rn je subgradientem normy v boděx0, pokud kxk ≥ kx0k+gT(x−x0), ∀x ∈Rn.
Dosazením x =0 a x=2x0 dostaneme kx0k=gTx0, tudíž kxk ≥gTx, ∀x∈Rn
a z positivní homogenity se stačí omezit na kxk=1, tedy 1≥gTx, ∀x :kxk=1.
To je ale ekvivalentní s kgk∗ ≤1.
Subdiferenciál normy
f(x)≥f(x0) +gT(x−x0)∀xTvrzení (Subdiferenciál normy)
∂kx0k={y ∈Rn;yTx0 =kx0k, kyk∗ ≤1}.
Například:
◮ v počátkux0 =0 je subgradientem jednotková koule v duální normě
∂kx0k={y ∈Rn;kyk∗ ≤1}.
◮ Eukleidovská norma je v každém nenulovém bodě hladká, a tedy subdiferenciál splývá s gradientem∂kx0k= kx10k2x0.
◮ Pro součtovou normu podmínka yTx0 =kx0k1, kyk∞=1 platí jen pro taková y, pro kteráyi = sgn(xi0), pokud xi06=0, ayi = [−1,1], pokudxi0 =0.
Subdiferenciál vlastního čísla
f(x)≥f(x0) +gT(x−x0)∀xTvrzení (Subdiferenciál maximálního vlastního čísla)
Uvažujme funkci f(X) =λmax(X) na prostoru symetrických matic.
Buď X ∈Rn×n symetrická av,kvk2 =1, příslušný vlastní vektor k λmax(X). Pak
v vT ∈∂f(X).
Důkaz.
Pro každou symetrickou matici Y ∈Rn×n platí λmax(Y) = max{uTYu;kuk2 =1}
≥vTYv
=vTXv+vT(Y −X)v
=λmax(X) + tr(vT(Y −X)v)
=λmax(X) + tr(vvT(Y −X))
=λmax(X) +hvvT,Y −Xi
Subdiferenciál v optimalizaci
f(x)≥f(x0) +gT(x−x0)∀xVěta
Bod x0∈Rn je minimem konvexní funkce f:Rn→Rprávě tehdy, když 0∈∂f(x0).
Důkaz.
Pokud 0∈∂f(x0), pak podmínka z definice subgradientu má tvar f(x)≥f(x0), ∀x∈Rn,
čili x0 je minimem. Naopak, pokud jex0 minimem, pak 0∈∂f(x0).
Subdiferenciál v optimalizaci
f(x)≥f(x0) +gT(x−x0)∀xPříklad
Uvažujme úlohu
xmin∈Rn max
k=1,...,m(aTkx+bk).
Podle věty je bod x0 ∈Rn optimem právě tehdy, když existuje y ≥0 takové, žeeTy =1,Pm
k=1ykak =0 ayk =0 prok 6∈I(x0).
Pro srovnání, přepíšeme úlohu jako lineární program min z subject to aTkx+bk ≤z ∀k.
Duální úloha má tvar
max bTy subject to
m
X
k=1
ykak =0, y ≥0, eTy =1.
Podmínky optimality dají stejné vyjádření, tj. existuje duální přípustné řešení y takové, žeyk =0 pokudaTkx0+bk <z0, kde z0 = maxk(akTx0+bk).
Subdiferenciál v optimalizaci
f(x)≥f(x0) +gT(x−x0)∀xPříklad (LASSO) Uvažujme úlohu LASSO
min 1
2kAx−bk2+λkxk1 subject to x∈Rn, kde λ >0 je parametr. Podmínky optimality pro bodx0 ∈Rn
0∈∂12kAx0−bk2+λkx0k1 =∂12kAx0−bk2+∂λkx0k1 0∈AT(Ax0−b) +λ∂kx0k1.
Víme, že je v ∈∂kx0k1 právě tehdy, kdyžvi = sgn(xi0) pro xi06=0 a vi ∈[−1,1]pro xi0 =0. Tedy podmínky optimality jsou
(ATi∗(b−Ax0) =λsgn(xi0) pokud xi06=0,
|ATi∗(b−Ax0)| ≤λ pokud xi0=0.
◮ Umožňují ověřit, zda danéx0 je optimem (ale ne ho najít).
◮ Vlastnosti optima, jako například |AT(b−Ax0)| ≤λe.
Subdiferenciál v optimalizaci
f(x)≥f(x0) +gT(x−x0)∀xTvrzení
Platí pro směrovou derivaci ve směruv konvexní funkcef :Rn→R: fv′(x0) = sup{gTv;g ∈∂f(x0)}.
Důkaz.
“≥” Buď g ∈∂f(x0). Podle definice
fv′(x0) = min
α→0+
f(x0+αv)−f(x0)
α ≥ min
α→0+
f(x0) +αgTv−f(x0)
α =gTv.
“≤” Idea: Ukaž, že fv′(x)je konvexní a její subgradient je subgradientem f(x). Pak uvažv →αv proα→0+.
◮ Optimalizační metody jsou často iterační ve směru klesání.
◮ Subgradient přímočaře použít nelze, např. funkce f(x) =|x| má v bodě x0=0 subgradient g =1, ale funkce ve směru−1 neklesá.
