Beiblatt Liniensuchen

Prof. Dr. R. Herzog
Nichtlineare Optimierung
Algorithmen zur Liniensuche
Algorithmus 4.11 (Armijo-Liniensuche mit Backtracking).
Eingabe: Iterierte xk und Abstiegsrichtung dk ; Parameter β ∈ (0, 1), σ ∈ (0, 1)
Ausgabe: Schrittweite αk , die (4.9) erfüllt
1: Setze ` := 0
2: while Armijo-Bedingung (4.9) für α = β ` verletzt do
3:
` := ` + 1
4: end while
5: return αk = β `
Algorithmus 4.15 (Wolfe-Liniensuche).
Eingabe: Iterierte xk und Abstiegsrichtung dk ; Parameter γ > 1, γ1,2 ∈ (0, 1/2],
0 < σ < τ < 1, αstart > 0
Ausgabe: Schrittweite αk , die (4.9) und (4.12) erfüllt
1: Setze a := 0 und b := αstart
2: while b erfüllt nicht [(4.9) und (4.12)]; und b erfüllt nicht (4.13b) do
3:
Setze a := b und b := γ b
4: end while
5: if b erfüllt (4.9) und (4.12) then
6:
return αk = b
7: end if
8: loop
9:
Wähle t ∈ [a + γ1 (b − a), b − γ2 (b − a)].
10:
if t erfüllt (4.9) then
11:
if t erfüllt (4.12) then
12:
return αk = t
13:
else if ψ 0 (t) ≤ 0 then
14:
Setze a := t
15:
else
16:
Setze b := t
17:
end if
18:
else
19:
Setze b := t.
20:
end if
21: end loop
Verwendet man in Algorithmus 4.15 statt (4.12) die Bedingung (4.11), erhält man
Schrittweiten, die die (nicht-strenge) Wolfe-Bedingungen erfüllen.
http://www.tu-chemnitz.de/mathematik/part_dgl/teaching/WS2015_Nichtlineare_Optimierung/

Download Report