Prof. Dr. R. Herzog
Nichtlineare Optimierung
Lineares und nichtlineares CG-Verfahren
Algorithmus 4.19 (Vorkonditioniertes CG-Verfahren).
Eingabe: Startwert x0 ∈ Rn , s.p.d. A, M −1 ∈ Rn×n ; b ∈ Rn
Ausgabe: Verbesserte Approximation von x∗ = A−1 b
1: Setze k := 0
2: Setze r0 = A x0 − b, d0 = −M −1 r0
3: while Abbruchkriterium nicht erfüllt do
4:
Setze αk = (rk> M −1 rk )/(d>
k A dk )
5:
Setze xk+1 = xk + αk dk
6:
Setze rk+1 = rk + αk A dk (oder rk+1 = A xk+1 − b)
>
M −1 rk+1 )/(rk> M −1 rk )
7:
Setze βk+1 = (rk+1
−1
8:
Setze dk+1 = −M rk+1 + βk+1 dk
9:
Setze k = k + 1
10: end while
11: return xk
Algorithmus 4.21 (Vorkonditioniertes nichtlineares CG-Verfahren).
Eingabe: Startwert x0 ∈ Rn , s.p.d. M −1 ∈ Rn×n
Ausgabe: Approximation eines stationären Punktes
1: Setze k := 0
2: Setze r0 = ∇f (x0 ), d0 = −M −1 r0
3: while Abbruchkriterium nicht erfüllt do
4:
Bestimme αk über eine Liniensuche
5:
Setze xk+1 = xk + αk dk
6:
Setze rk+1 = ∇f (xk+1 ); yk = rk+1 − rk
7:
Wähle βk+1
8:
Setze dk+1 = −M −1 rk+1 + βk+1 dk
9:
Setze k = k + 1
10: end while
11: return xk
http://www.tu-chemnitz.de/mathematik/part_dgl/teaching/WS2015_Nichtlineare_Optimierung/
Prof. Dr. R. Herzog
Wahl von βk+1
Hestenes–Stiefel (1952)
krk+1 k2 −1
M
=
2
krk kM
−1
HS
βk+1
=
yk> M −1 rk+1
yk> dk
Fletcher–Reeves (1964)
FR
βk+1
PR+
PR
βk+1
= max{0, βk+1
}
PR
βk+1
Powell (1985)
F
βk+1
=−
Polak–Ribière (1969)
Fletcher (1987)
LS
βk+1
y > M −1 rk+1
= k
2
krk kM
−1
Liu–Storey (1991)
2
krk+1 kM
−1
rk> dk
Gilbert–Nocedal (1992)
GN
βk+1
y > M −1 rk+1
=− k >
rk dk

FR
PR
FR

−βk+1 , falls βk+1 < −βk+1
FR
PR
= β PR ,
|
≤
β
falls |βk+1
k+1
 k+1

FR
PR
FR
> βk+1
,
falls βk+1
βk+1
Dai–Yuan (1999)
HZ
βk+1
=
DY
βk+1
2
krk+1 kM
−1
=
yk> dk
>
2
kyk kM
rk+1
−1
M −1 yk − 2 dk
yk> dk
yk> dk
Hager–Zhang (2005)
Bemerkung
:=
starke Wolfe-Bed. (4.9), (4.12) mit 0 < σ < τ <
1/2
PR+
Abstieg nicht garantiert, daher oft βk+1
PR
}
max{0, βk+1
Verfeinerung der starken Wolfe-Bed., siehe Gilbert, Nocedal, 1992, (4.1) und Abschnitt 6
starke Wolfe-Bed. (4.9), (4.12) mit 0 < σ < τ <
1/2
Wolfe-Bed. (4.9), (4.11) mit 0 < σ < τ < 1
Tabelle 4.1: Einige gängige nichtlineare CG-Verfahren
http://www.tu-chemnitz.de/mathematik/part_dgl/teaching/WS2015_Nichtlineare_Optimierung/

Setze die Muster fort!

Setze das Muster fort!

Setze die Muster fort

Setze die Minutenschritte sinnvoll fort!