Obsah přednášky
• Nederivační metody
• Metody 1D optimalizace
• Derivační metody
Optimalizace
– Metody první derivace
• Spádové metody
• Metody sdružených směrů
Metoda konjugovaných gradientů
– Metoda konjugovaných gradientů
– Metody druhé derivace
2
Mgr. Květuše Sýkorová
KI PřF UJEP Ústí nad Labem
základní pojmy
základní pojmy
• definice:
• definice:
– matice A je pozitivně definitní ⇔ je čtvercová, hermitovská, její
všechna vlastní čísla λi > 0
– matice A je negativně definitní ⇔ je čtvercová, hermitovská, její
všechna vlastní čísla λi < 0
– matice A je hermitovsky sdružená ⇔ A = (A T )
– matice A je indefinitní v ostatních případech
• A = AT (transponovaná) ⇒ A je symetrická
• A = A (komplexně sdružená) ⇒ A ∈ R2
• A ∈ R2 ⇒ hermitovská = symetrická
•
⇒ pro každý nenulový vektor x je x T ⋅ A ⋅ x > 0
3
4
základní pojmy
Metoda konjugovaných gradientů
= conjugate gradient method
• definice:
– speciální případ metod sdružených směrů
– matice A je pozitivně definitní ⇔ všechny hlavní minory jsou > 0
 3 − 1

A = 
1 2 
det (3) = 3 > 0
• řešení systému lineárních rovnic s pozitivně definitní maticí
 3 − 1
 = 7 > 0
det 
1 2 
– matice A je negativně definitní ⇔ všechny hlavní minory jsou < 0
 − 2 − 1

A = 
3 
 1
 − 2 − 1
 = −5 < 0
det(− 2) = −2 < 0 det
3 
 1
– matice A je indefinitní v ostatních případech
 3 −1 

A = 
1 − 2
det(3) = 3 > 0
• princip:
– pro určení směru přesunu z bodu x(k) do bodu x(k+1) se využívá
nejen hodnota g(k), ale i hodnota g(k-1)
• obecně – využívají se hodnoty g(k), g(k-1), g(k-2), …, g(0)
– informace o současném a předchozím sklonu funkce umožňuje
rychlejší sestup do minima
– konverguje po konečném počtu kroků
 3 −1 
 = −4 < 0
det
 2 − 2
5
• za určitých podmínek
6
1
Metoda konjugovaných gradientů
Metoda konjugovaných gradientů
• popis problému:
• základní pojmy:
– vektory s(1), s(2),…, s(p) jsou konjugované k
symetrické matici M ↔
T
s (i ) ⋅ M ⋅ s ( j ) = 0
– Předpoklad:
• F(x) je kvadratická funkce
F (x) =
1 T
⋅ x ⋅ A ⋅ x − bT ⋅ x
2
• s(k) směr přesunu z bodu x(k)
• α(k) koeficient délky přesunu
)
(
α
– tj. hledáme minimum funkce F(x) na polopřímce, která
má počátek v bodě x(k) a směrnici s(k).
Nechť vektory s(0), s(1),…, s(n-1) jsou konjugované k matici A
∀x (0 ) ∈ R n x (k +1) = x ( k ) + α (k ) ⋅ s (k )
platí
kde α ( k ) = arg min F x ( k ) + α ⋅ s ( k )
α
Potom metoda konverguje po n krocích
(
α (k ) = arg min F (x (k ) + α ⋅ s (k ) )
• koeficient α(k) tak, aby platilo:
– Věta:
•
•
•
•
x (k +1) = x (k ) + α (k ) ⋅ s (k )
• Hledáme pro rovnici:
(∀i ≠ j )
(
f (α ) = F x (k ) + α ⋅ s (k )
• tuto polopřímku popisuje funkce:
)
– f(α) je funkce jedné proměnné α
)
– tj. x(n) = x*
7
8
Metoda konjugovaných gradientů
Metoda konjugovaných gradientů
• popis problému:
• výpočet
• popis problému:
s(k+1):
s (k +1) = − g (k +1) + β (k ) ⋅ s (k )
• výpočet s(0):
β
– existuje více variant pro výpočet
• g(k+1) gradient v bodě x(k+1)
• β(k) koeficient určující míru vlivu směru s(k) na směr s(k+1)
• s(k) směr přesunu z bodu x(k)
s ( 0 ) = − g (0 )
• g(0) gradient v bodě x(0)
β (k ) = arg min F (x (k +1) + α (k ) ⋅ (− g (k +1) + β ⋅ s (k ) ))
• výpočet β(k):
• g(k+1) gradient v bodě x(k+1)
• β(k) koeficient určující míru vlivu směru s(k) na směr s(k+1)
• s(k) směr přesunu z bodu x(k)
• výpočet s(0):
• g(0) gradient v bodě x(0)
9
10
Metoda konjugovaných gradientů
Metoda konjugovaných gradientů
• Důkaz: (konstruktivní) 1.část
• Věta:
• Nechť vektory s(0), s(1),…, s(n-1) jsou konjugované k matici A
• kde matice A je pozitivně definitní Hessova matice kvadratické
funkce F(x)
∀x (0 ) ∈ R n x (k +1) = x ( k ) + α (k ) ⋅ s (k )
• platí
• kde
α ( k ) = arg min F x ( k ) + α ⋅ s ( k )
α
• Potom metoda konverguje po n krocích
(
)
(
(
x ( n ) = x* = x (0 ) + α (0 ) ⋅ s (0 ) + α (1) ⋅ s (1) + K + α ( n −1) ⋅ s (n −1)
n −1
x * − x ( 0 ) = ∑ α (i ) ⋅ s (i )
)
T
zleva vynásobit výrazem: s ( k ) ⋅ A
– tj. x(n) = x*
(
)
i =0
n −1
s ( k ) ⋅ A ⋅ x * − x (0 ) = ∑ s ( k ) ⋅ A ⋅ α (i ) ⋅ s (i )
T
• Důkaz:
)
x ( n ) = x* = x (n −1) + α ( n −1) ⋅ s (n −1) = x (n −2 ) + α (n − 2 ) ⋅ s ( n −2 ) + α ( n −1) ⋅ s (n −1) = K
(konstruktivní)
T
konjugované směry
i =0
T
(
)
T
T
T
s ( k ) ⋅ A ⋅ x * − x (0 ) = α (0 ) ⋅ s ( k ) ⋅ A ⋅ s (0 ) + K + α (k ) ⋅ s (k ) ⋅ A ⋅ s ( k ) + K + α (n −1) ⋅ s ( k ) ⋅ A ⋅ s ( n −1)
• platí předpoklady Věty
s
( k )T
⋅ A ⋅ (x * − x ( ) ) = 0 + K + 0 + α ( ) ⋅ s ( ) ⋅ A ⋅ s ( ) + 0 + K + 0
s ( ) ⋅ A ⋅ (x * − x ( ) )
α( ) =
0
k
k T
k T
11
k
0
k
T
s (k ) ⋅ A ⋅ s ( k )
12
2
Metoda konjugovaných gradientů
Metoda konjugovaných gradientů
• Důkaz: (konstruktivní) 2.část
• Důkaz: (konstruktivní) 3.část
pro libovolné k platí:
funkce F(x) je kvadratická:
F( x ) =
x ( k ) = x (0 ) + α (0 ) ⋅ s (0 ) + α (1) ⋅ s (1) + K + α (k −1) ⋅ s (k −1)
k −1
x ( k ) − x (0 ) = ∑ α (i ) ⋅ s (i )
k −1
konjugované směry
T
s
(
)
⋅ A ⋅ x (k ) − x (0 ) = α (0 ) ⋅ s
⋅ A ⋅ s ( 0 ) + K + α ( k −1) ⋅ s
(
T
(k )T
α (k ) =
)
s ( k ) ⋅ A ⋅ x (k ) − x (0 ) = 0 + K + 0
T
(
T
T
s ( k ) ⋅ A ⋅ x ( k ) = s ( k ) ⋅ A ⋅ x (0 ) ⇒
α (k ) =
s (k ) ⋅ A ⋅ x * − x (k )
T
s (k ) ⋅ A ⋅ s (k )
)
s (k +1) = − g (k +1) + β ( k ) ⋅ s (k )
pro i = k :
T
• nový gradient
+β
⋅s
⋅A⋅s
β
g ( k +1) ⋅ A ⋅ s ( k )
T
s (k ) ⋅ A ⋅ s (k )
s (k +1) = − g (k +1) + β ( k ) ⋅ s (k )
T
s (k ) ⋅ A ⋅ s (k )
16
Metoda konjugovaných gradientů
• funkce F(x) není kvadratická:
• vylepšení výpočtu β(k):
nutné počítat v každém kroku gradient a Hessovu matici
algoritmus není obecně konvergentní
nutná reinicializace po n krocích
různé způsoby výpočtu β(k)
– metoda Hestenes & Stiefel (1952):
T
g (k +1) ⋅ g ( k +1) − g ( k )
• počítáme
(k )
β HS
=
T
(
(
s ( k ) ⋅ g ( k +1) − g (k )
– metoda Fletcher & Reeves (1963):
T
• počítáme
g (k +1) ⋅ g (k +1)
(k )
β FR
=
T
(k )
β HS
• Hestenes & Stiefel
(k )
• Fletcher & Reeves
β FR
(
k)
• Polak & Ribier
β PR
– metoda Polak & Ribier (1969):
• počítáme
• funkce F(x) je kvadratická:
– pro kvadratickou funkci platí:
=
g ( k +1) ⋅ A ⋅ s ( k )
15
Metoda konjugovaných gradientů
–
–
–
–
))
T
(k )
T
β (k ) =
x ( k +1) = x (k ) + α (k ) ⋅ s (k )
T
((
• nový směr
(k )
s (k ) ⋅ g (k )
s (k ) ⋅ A ⋅ s (k )
g (k +1) = grad F x ( k +1)
T
⋅A⋅s
14
( ( ))
α (k ) = −
0 = − g (k +1) ⋅ A ⋅ s (i ) + 0
0 = −g
)
T
s (k ) ⋅ A ⋅ s ( k )
s (0 ) = − g (0 ) = − grad F x (0 )
T
(k )T
(
s (k ) ⋅ − g (k )
x (0 ) ∈ R n
• spočteme
i≤k
(k )
))
• v kroku k = 0,…,n-1:
s (k +1) ⋅ A ⋅ s (i ) = − g (k +1) ⋅ A ⋅ s (i ) + β (k ) ⋅ s (k ) ⋅ A ⋅ s (i )
(k )
(
T
s (k ) ⋅ A ⋅ s ( k )
α (k ) =
– pro libovolné
• spočteme
β
(k +1)T
(
⋅ ( g ( x *) + b ) − g (k ) + b
• Algoritmus:
• start:
– nový směr počítáme:
pro i < k :
s (k ) ⋅ A ⋅ s ( k )
Metoda konjugovaných gradientů
β (k ) = arg min F (x ( k +1) + α (k ) ⋅ (− g (k +1) + β ⋅ s ( k ) ))
T
)
T
( k )T
T
• odvození výpočtu β(k):
T
s
13
Metoda konjugovaných gradientů
zprava vynásobit výrazem: A ⋅ s (i )
(
T
⋅ A ⋅ s (k −1)
)
T
s (k ) ⋅ A ⋅ s (k )
s (k ) ⋅ A ⋅ x * − A ⋅ x (k )
α (k ) =
i =0
( k )T
s (k ) ⋅ A ⋅ x * − x (k )
(k )
dosadíme do vzorce: α =
s ( k ) ⋅ A ⋅ (x (k ) − x (0 ) ) = ∑ s (k ) ⋅ A ⋅ α (i ) ⋅ s (i )
( k )T
(
T
i =0
T
zleva vynásobit výrazem: s ( k ) ⋅ A
T
1 T
(k )
(k )
⋅ x ⋅ A ⋅ x − b T ⋅ x ⇒ g (k ) = A ⋅ x (k ) − b ⇒ A ⋅ x = g + b
2
g ( x *) = A ⋅ x * −b = 0 ⇒ A ⋅ x* = g ( x *) + b
(k )
β PR
=
(k )
(k )
(k )
β HS = β PR = β FR
)
)
g ( k ) ⋅ g (k )
(g (
k +1)
)
T
− g ( k ) ⋅ g ( k +1)
T
g (k ) ⋅ g ( k )
při testování dosahuje nejlepší výsledky
17
18
3
Metoda konjugovaných gradientů
Metoda konjugovaných gradientů
• příklad:
• příklad:
– využijte uvedenou metodu pro nalezení minima kvadratické funkce
F(x)
F( x ) = 2 ⋅ x1 − x1 ⋅ x2 + x2 − 2 ⋅ x1 − 3 ⋅ x2 + 5
2
2
0
x (0 ) =  
0
– pro výpočet β(k) využijte některou z uvedených metod
– využijte uvedenou metodu pro nalezení minima kvadratické funkce
F(x) tak, aby platilo:
 2 −1 0 


A =  − 1 2 − 1
 0 −1 2 


A⋅x = b
1
 
b = 0
1
 
0
 
x (0 ) =  0 
0
 
– pro výpočet β(k) využijte některou z uvedených metod
2 body
19
3 body
20
4
Download

Optimalizace