Gradientenverfahren
Mit dem Gradientenverfahren können Minimierungsprobleme bearbeitet werden.
Dabei geht man von einem Näherungswert aus und schreitet dann in Richtung des negativen
Gradienten, also der Richtung des steilsten Abstiegs, bis man keine Verbesserung mehr erzielt.
Iteration
~ (0)
Startvektor x
(k)
~
x(k+1) = ~
x(k) + ~d ,
~d (k) = −∇f (~
x(k) )
Verbesserung durch Schrittweitensteuerung
~
x(k) + λ(k) ~d
x(k+1) = ~
~
x(0) =
f (x, y) = (x − 3)2 + 2y 2 ,
∇f (~
x) =
(k)
mit λ(k) Minimumstelle von f (λ) = f (~
x(k) + λ ~d )
1
1
2(x − 3)
4y
Abstiegsrichtung:
(k)
~d (0) =
4
,
−4
f (λ) = (1 + 4λ − 3)2 + 2(1 − 4λ)2
~
x
=⇒
(0)
(0)
+ λ ~d =
1 + 4λ
,
1 − 4λ
λ statt λ(0)
1
Minimum an der Stelle λ = 3
(f vereinfachen, 1. und 2. Ableitung, usw.)
~
x(1)
7
1
4
1
3
=
+3
=
1
−4
− 13
nächster Iterationsschritt
~d (1) =
4
3
4
3
usw.
1
Gradientenverfahren für quadratische Funktionen
Diese Funktionen haben immer die Form
1
f (~
x) = 2 ~
x + ~aT ~
xT A~
x + α.
Es ist dann
Mit
∇f (~
x) = A~
x + ~a.
~d (k) = −∇f (~
x(k) )
erhalten wir (nach längerer Rechnung, A wird als symmetrisch vorausgesetzt)
λk =
(k) T
(k)
(~d ) · ~d
(k) T
(k)
(~d ) · A · ~d
f (x, y) = (x −
3)2
+
2y 2
2
0
0
4
∇f (~
x) =
1
= 2 (x, y)
2
0
0
4
x
x
+ (−6, 0)
+ 9,
y
y
~
x
(0)
1
=
1
x
−6
2(x − 3)
+
=
y
0
4y
~d (0) = −∇f (~
x(0) ) =
Abstiegsrichtung:
4
−4
4
(4, −4)
−4
= 1
λ0 =
3
2 0
4
(4, −4)
0 4
−4
~
x(1) = ~
x(0) + λ(0) ~d
( 43 , − 43 )
4
3
− 43
λ1 =
( 43 , − 34 )
~
x
=~
x
=
(1)
7
3
− 13
~d (1) = −∇f (~
x(1) ) =
nächster Iterationsschritt
(2)
(0)
2
0
0
4
(1)
+ λ1 ~d =
!
4
3
− 43
25
9
1
9
4 3
4
3
! = 1
3
,
~
x
(3)
=~
x
c Roolfs
2
(2)
(2)
+ λ2 ~d =
25
9
1
9
1
+3
4
9
4
9
=
79
27
1
− 27
Methode der konjugierten Gradienten
Eine geschickte Anpassung der Richtungen durch konjugierte Gradienten in jedem Schritt bewirkt,
dass das Verfahren nach höchstens n Schritten (A ist eine n × n-Matrix, symmetrisch und positiv definit)
das Minimum erreicht. Der Start des Verfahrens erfolgt mit dem steilsten Abstieg, während bei allen weiteren
Schritten ein Korrekturterm in Abhängigkeit der vorherigen Suchrichtung dazukommt.
1
xT A~
x + ~aT ~
x + α −→ Minimum
f (~
x) = 2 ~
~ (0),
Startvektor sei x
beachte:
1. Iteration vorbereiten:
∇f (~
x) = A~
x + ~a = ~0
⇐⇒
~a = −~b.
(1)
−∇f = −(A~
x(0) + ~a) = ~b − A~
x(0),
~ · ~d(1)
~ (1) = A
u
⇐⇒
~g (0) = ~d
= −∇f
erspart doppelte Berechnung der rechten Seite
T
λ1 =
(~g (0) ) · ~g (0)
(1) T
~ (1)
(~d ) · u
(1)
~
~ (0) + λ1~d
x(1) = x
2. Iteration vorbereiten:
~g (1) = ~g (0) − λ1 u
~ (1) ,
T
β1 =
(~g (1) ) · ~g (1)
(~g
(0) T
) · ~g
,
~d(2) = ~g (1) + β1 ~d (1)
,
(1)
~d(3) = ~g (2) + β2 ~d (2)
(0)
~ · ~d(2)
~ (2) = A
u
T
λ2 =
(~g (1) ) · ~g (1)
(2) T
~ (2)
(~d ) · u
~
~ (1) + λ2~d
x(2) = x
3. Iteration vorbereiten:
(2)
~g (2) = ~g (1) − λ2 u
~ (2) ,
T
β2 =
~ · ~d(3)
~ (3) = A
u
T
λ3 =
(~g (2) ) · ~g (2)
(3) T
~ (3)
(~d ) · u
(3)
~
~ (2) + λ3~d
x(3) = x
3
(~g (2) ) · ~g (2)
(~g
(1) T
) · ~g
A~
x = ~b
Methode der konjugierten Gradienten
~g (k) = ~g (k−1) − λk u
~ (k) ,
(k + 1)te Iteration vorbereiten:
T
βk =
(~g (k) ) · ~g (k)
(~g
(k−1) T
) · ~g
(k−1)
,
~d(k+1) = ~g(k) + βk ~d (k)
~ · ~d(k+1)
~ (k+1) = A
u
T
λk+1 =
(~g (k) ) · ~g (k)
(k+1) T
~ (k+1)
(~d
) ·u
~
~ (k) + λk+1~d
x(k+1) = x
(k+1)
(0)
(1)
(n)
Vektoren ~d , ~d , · · · , ~d , heißen A-konjugiert, wenn gilt
(i)
(j)
(~d )T ·A · ~d = 0
für i, j ∈ {0, 1, . . . , n}.
Die Begriffsbildung ist eine Erweiterung der Orthogonalität, die mit A als Einheitsmatrix vorliegt.
A-konjugierte Vektoren sind linear unabhängig.
4
Methode der konjugierten Gradienten Beispiel
3
1
!
!
1
x
=
1
y
0
−3
!
1
f (~
x) = 2 ~
xT A~
x + ~aT ~
x + α −→ Minimum
~
x(0) =
Startvektor sei
!
0
,
0
1. Iteration vorbereiten:
~ · ~d
~ (1) = A
u
beachte:
−∇f = −(A~
x
(1)
(~g (0) ) · ~g (0)
(~d
(1) T
~
) ·u
~ · ~d
= A
+ ~a) = ~b − A~
x ,
~
x
(2)
(2)
!
3
,
0
+ λ2~d
3. Iteration vorbereiten:
β1 =
!
1
(2)
~g
(2)
3
2
− 92
!
~
− λ2 u
(2)
=
= ~g
(1)
=
!
0
0
Ziel erreicht
3
1
!
!
3
1
2
=
1
− 92
(1)
= ~d
= −∇f =
T
=2
(2) T
~ (2)
(~d ) · u
~
= x
6
0
=
(~g (1) ) · ~g (1)
(1)
~g
(0)
!
0
−3
9
T
λ2 =
!
0
.
−3
(0)
~ (1) =
2. Iteration vorbereiten: ~g (1) = ~g (0) − λ1 u
~
u
A~
x = ~b
= 9 =1
!
0
=
−3
(1)
(1)
~
~ (0) + λ1~d
x(1) = x
(2)
⇐⇒
!
−3
−3
=
T
λ1 =
(0)
~b =
∇f (~
x) = A~
x + ~a = ~0
⇐⇒
!
0
−3
5
(~g (1) ) · ~g (1)
T
(~g (0) ) · ~g (0)
= 1,
(2)
~d
= ~g (1) + β1 ~d
(1)
=
!
3
−3
Methode der konjugierten Gradienten 2. Beispiel
1
f (~
x) = 2 ~
xT A~
x + ~aT ~
x + α −→ Minimum
2
0
1
f (x, y) = (x − 3)2 + 2y 2 = 2 (x, y)
~
x(0) =
Startvektor sei
!
1
,
1
1. Iteration vorbereiten:
~
u
(1)
~ · ~d
= A
−∇f = −(A~
x
(1)
(~d
~
) ·u
2. Iteration vorbereiten: ~g
~
u
(2)
~ · ~d(2)
= A
= ~g
(0)
~
x
(2)
(2) T
~ (2)
(~d ) · u
~
= x
(1)
+ λ2~d
3. Iteration vorbereiten:
(2)
(0)
~
− λ1 u
(1)
32
9
32
9
=
(~g (1) ) · ~g (1)
~a = −~b =
7
3
− 13
=
T
λ2 =
x
+ (−6, 0)
y
! !
0
3
=
4
0
+9
!
−6
.
0
(0)
+ ~a) = ~b − A~
x ,
~g
(0)
(1)
= ~d
= −∇f =
!
4
−4
!
!
=
4
3
4
3
!
T
,
β1 =
!
3
=8
=
3
0
!
~g (2) = ~g (1) − λ2 u
~ (2) =
!
0
0
Ziel erreicht
2
0
!
A~
x = ~b
1
(1)
(1)
!
⇐⇒
=3
(1)
~
~ (0) + λ1~d
x(1) = x
x
y
8
−16
=
(~g (0) ) · ~g (0)
(1) T
!
beachte:
T
λ1 =
0
4
∇f (~
x) = A~
x + ~a = ~0
⇐⇒
!
6
0
6
(~g (1) ) · ~g (1)
T
(~g (0) ) · ~g (0)
=
1
,
9
~d
(2)
= ~g
(1)
+ β1 ~d
(1)
=
16
9
8
9
!
© Copyright 2024 ExpyDoc
