Beiblatt Newton-Verfahren mit BFGS

Prof. Dr. R. Herzog
Nichtlineare Optimierung
Newtonverfahren mit inversem BFGS-Update
Algorithmus 4.35 (Quasi-Newtonverfahren mit inversem BFGS-Update).
Eingabe: Startwert x0 ∈ Rn , s.p.d. B0 ∈ Rn×n
Ausgabe: Approximation eines stationären Punktes x∗
1: setze k := 0
2: while Abbruchkriterium nicht erfüllt do
3:
Setze dk = −Bk ∇f (xk )
4:
Bestimme αk über eine Wolfe-Liniensuche (Algorithmus 4.15) mit αstart = 1
und σ ∈ (0, 1/2)
5:
Setze xk+1 := xk + αk dk
6:
Berechne Bk+1 über (4.42) und setze k := k + 1
7: end while
8: return xk
Algorithmus 4.36 (Auswertung von BkBFGS g).
Eingabe: {(yi , si )}i=0,...,k−1 , Startmatrix B0BFGS und g
Ausgabe: BkBFGS g
1: Setze r := g
2: for i := k − 1, k − 2, . . . , 0 do
3:
Setze αi := γi s>
i r
4:
Setze r := r − αi yi
5: end for
6: Setze d := B0BFGS r
7: for i := 0, 1, . . . , k − 1 do
8:
Setze β := γi yi> d
9:
Setze d := d + (αi − β) si
10: end for
11: return d
http://www.tu-chemnitz.de/mathematik/part_dgl/teaching/WS2015_Nichtlineare_Optimierung/
Prof. Dr. R. Herzog
Newtonverfahren mit inversem LM-BFGS-Update
Algorithmus 4.37 (Auswertung von BkLM-BFGS g).
Eingabe: {(yi , si )}i=k−m,...,k−1 , Startmatrix B LM-BFGS und g
Ausgabe: BkLM-BFGS g
1: Setze r := g
2: for i := k − 1, k − 2, . . . , k − m do
3:
Setze αi := γi s>
i r
4:
Setze r := r − αi yi
5: end for
6: Setze d := B LM-BFGS r
7: for i := k − m, . . . , k − 2, k − 1 do
8:
Setze β := γi yi> d
9:
Setze d := d + (αi − β) si
10: end for
11: return d
Algorithmus 4.38 (Quasi-Newtonverfahren mit inversem LM-BFGS-Update).
Eingabe: Startwert x0 ∈ Rn , s.p.d. B LM-BFGS ∈ Rn×n
Ausgabe: Approximation eines stationären Punktes x∗
1: setze k := 0
2: while Abbruchkriterium nicht erfüllt do
3:
Berechne dk = −BkLM-BFGS ∇f (xk ) mit Algorithmus 4.37
4:
Bestimme αk über eine Wolfe-Liniensuche (Algorithmus 4.15) mit αstart = 1
und σ ∈ (0, 1/2)
5:
Setze xk+1 := xk + αk dk
6:
Speichere sk = xk+1 − xk , yk = ∇f (xk+1 ) − ∇f (xk )
7:
Setze k := k + 1
8: end while
9: return xk
http://www.tu-chemnitz.de/mathematik/part_dgl/teaching/WS2015_Nichtlineare_Optimierung/

Download Report