3. Přednáška: Line search Úloha: min f (x),
x∈Rn
kde x ∈ Rn , n ≥ 1 a f : Rn → R je dvakrát spojitě diferencovatelná. Iterační algoritmy: • Začínám v x0 a vytvářím posloupnost iterací {xk }∞ k=0 , tak, aby minimum bylo aproximováno s dostatečnou přesností, ideálně končila v přesném řešení. • K posunutí z xk do xk+1 , aby f (xk+1 ) < f (xk ) mohu použít informace o x0 , . . . , xk−1 a jejich funkčních hodnotách. • 2 základní strategie, jak se posunout z xk do xk+1 : Line search, trust region. Line search algoritmus: Dáno x0 , interval (a, b), ε atd. a pro k = 0, 1, 2, . . . : 1) najdi směr pk ∈ Rn - spádový směr, 2) najdi αk tak, aby xk + αk pk bylo ”lepší” než xk (ideálně minimální - exaktní line search, dostatečně malé - aproximace), 3) polož xk+1 = xk + αk pk . Priklad3.m ad 1) viz další přednášky, ad 2) hledání minima jednodimenzionální funkce φ(α) = f (xk + αpk ), tj. řeším úlohu: min φ(α). α>0
Jednodimenzionální minimalizace: Definice: Unimodální funkce Funkce φ : R → R je unimodální na intervalu ha, bi, jestliže existuje c ∈ (a, b) takové, že φ je klesající na ha, ci a rostoucí na hc, bi. Věta: Pozice minima Nechť φ je unimodální v ha, bi a nabývá svého minima v α∗ ∈ ha, bi. Pak pro libovolné x a y, kde a ≤ x < y ≤ b platí následující tvrzení: 1
• Je-li φ(x) < φ(y), pak α∗ < y. • Je-li φ(x) > φ(y), pak α∗ > x. • Je-li φ(x) = φ(y), pak x < α∗ < y. Algoritmus: Za předpokladu unimodální funkce φ a pomocí výše uvedené věty generuji posloupnost zmenšujících se intervalů obsahujících řešení α∗ (intervaly neurčitosti): ha, bi = I0 ⊃ I1 ⊃ . . . Ik−1 ⊃ Ik = hak , bk i, ∆k ≡ bk − ak značí délku k-tého intervalu. Požaduji co nejmenší vyhodnocování funkce φ, co největší redukci intervalů, jednoduchost. Metody: • Metoda bisekce (krácení na poloviny, jednoduché, drahé - hodně vyhodnocování φ). Priklady3 bisekce.m • Fibonacciho metoda (optimální, krácení v poměru fibonacciho čísel, když chceme zpřesnit musíme začít od začátku). Fibonacciho posloupnost: F0 = F1 = 1, Fk = Fk−1 + Fk−2 , k = 2. . . . , N . Priklady3 fibonacci.m • Metoda zlatého řezu (optimální). Zafixujeme zkracování intervalu na jedné hodnotě: √ FN −1 5−1 ξ = lim FN , platí ξ = 2 - zlatý řez. N →∞ Priklady3 zlatyrez.m • Newtonova metoda: funkce φ musí být navíc hladká, aproximace kvadratickou funkcí. Priklady3 newton.m • Testování dostatečného poklesu. Dostatečný pokles: Dilema přesnost x výpočetní čas • Použití minimalizační metody (viz výše), ale zastavím hledání řešení, pokud interval neurčitosti splňuje podmínku: |α∗ − α ¯ | ≤ c¯ α, kde α∗ je přesné řešení, α ¯ je aktuální řešení, |α∗ − α ¯ | délka intervalu neurčitosti. • Spokojím se s dostatečným poklesem.
2
Přímka udávající pokles: • xk , pk spádový směr φ0 (0) = gradT f (xk )pk < 0. • Chci zvolit α tak, aby φ(α) ≡ f (xk + αpk ) dostatečně pokleslo a α nebylo ani malé ani velké. • Přímka udávající pokles: pro dané ε ∈ (0, 1): l(α) ≡ φ(0) + εφ0 (0)α. • Pro všechna α taková, že φ(α) < l(α) platí f (xk + αpk ) = φ(α) < φ(0) = f (xk ). Armijův test (podmínka): • Pokud bude α malé i pokles může být malý. • Volba tak, aby například dvojnásobné (desetinásobné) α už nesplnilo podmínku φ(α) < l(α), tj. zvol η (η = 2) a najdi α tak, aby φ(α) ≤ φ(0) + εφ0 (0)α
(1)
∧ φ(ηα) > φ(0) + εφ0 (0)α.
(2)
• Pseudo-algoritmus: – Start: volím ε (v praxi volíme malé, 10−4 ), η, α. . . – Pokud je splněna (1), prováděj α = ηα dokud není splněna (2). – Pokud není splněna (1), prováděj α = αη , dokud není splněna (1). • Interval přípustných hodnot α nemusí obsahovat minimum funkce φ(α). • Priklad3 pokles.m Goldsteinův test (podmínka): • Zvolím ε ∈ 0, 21 tak, aby φ(α) ≤ φ(0) + εφ0 (0)α.
(3)
• Aby α nebylo příliš malé, musí ležet nad jinou přímkou, tj. φ(α) ≥ φ(0) + (1 − ε)φ0 (0)α. • Interval přípustných hodnot α nemusí obsahovat minimum funkce φ(α). • Priklad3 goldstein.m
3
(4)
Wolfeho test (podmínka): • Zvolím ε ∈ 0, 21 tak, aby φ(α) ≤ φ(0) + εφ0 (0)α.
(5)
• Dám požadavek na sklon: pokud jsem blízko minima φ0 (α) < φ0 (0). • Wolfeho podmínka: (5) a φ(α)0 ≥ (1 − ε)φ0 (0).
(6)
|φ(α)0 | ≤ (1 − ε)|φ0 (0)|.
(7)
• Silná Wolfeho podmínka: (5) a
• Nemusím se omezovat jen jedním ε. • Alternativa: pro 0 < c1 < c2 < 1 φ(α) ≤ φ(0) + c1 φ0 (0)α, φ0 (α) ≥ c2 φ0 (0), |φ(α)| ≤ c2 |φ0 (0)|. • Wolfeho test zaručí jak dostatečný pokles φ(α), tak dostatečný nárůst φ0 (α) vzhledem k α = 0. • Priklad3 wolfe.m Konvergence algoritmů typu Line-search: • Body xk nalezené Line-search algoritmem obecně nemusí konvergovat k přesnému řešení x∗ . • Konvergenci lze chápat v různém smyslu: lim xk = x∗ nebo lim ||∇f (xk )|| = 0. k→∞
• Označme cos θk = většího spádu.
k→∞
−pk ∇fk , ||∇fk || ||pk ||
θk . . . úhel svírající zvolený spádový směr a směr nej-
• Lipchitzovská spojitost ∇f (x) na Ω: existuje konstanta L > 0 taková, že ||∇f (x) − ∇f (y)|| ≤ L||x − y||, • Vrstevnicová oblast Γf (x0 ) ≡ {x : f (x) ≤ f (x0 )}. 4
∀x, y ∈ Ω.
Věta: Nechť x0 ∈ Rn je počáteční přiblížení a nechť f ∈ C1 (Ω), kde Ω je otevřená množina obsahující vrstevnicovou oblast Γf (x0 ) . Dále nechť ∇f je Lipschitzovsky spojitý na Ω. Uvažujme algoritmus Line-search, tj. iterace xk+1 = xk + αk pk , kde pk je spádový směr a αk splňuje Wolfeho podmínky. Potom X cos2 (θk )||∇f (xk )||2 < ∞ k≥0
a tato podmínka implikuje cos2 (θk )||∇f (xk )||2 → 0 pro k → ∞. Definice: Řekneme, že konvergentní posloupnost {xk } konverguje k x∗ rychlostí řádu p, pokud existují čísla 0 < c < 1 a k0 > 0 taková, že platí ||k+1 || ≤ c, ||k ||p
∀k ≥ k0 .
Kde k ≡ xk − x∗ . Pro p = 1 mluvíme o lineární rychlosti konvergence, pro p = 2 mluvíme o kvadratické rychlosti konvergence. Pokud platí ||k+1 || ≤ ak , ||k || kde {ak } je posloupnost nezáporných čísel, ak → 0+ pro k → ∞, hovoříme o superlineární konvergenci.
5
