W11

Wyk lad 10 - sem II 2012/2013

Metody iteracyjne dla zadań

optymalizacji bezwarunkowej

Zadanie minimalizacji bezwarunkowej

(P )

infx∈Rn

f (x)

gdzie f : Rn → R jest dwukrotnie różniczkowalna w sposób ciag ly

Metody iteracyjne polegaja na konstrukcji ciagu

{xk} zbieżnego do rozwiazania problemu (P )

metody spadku - f (xk+1) ≤ f (xk)

Rozważamy iteracyjne metody postaci

xk+1 = xk + tkdk

dk - kierunek poprawy

tk - d lugość kroku

Rzad zbieżności: x

k → ¯

• zbie żność xk → ¯

x jest liniowa jeśli

kxk

lim sup

+1 − ¯

xk < 1

k→∞

kxk − ¯

• zbie żność xk → ¯

x jest superliniowa jeśli

kxk

lim sup

+1 − ¯

xk = 0

k→∞

kxk − ¯

• zbie żność xk → ¯

x jest kwadratowa jeśli

kxk

lim sup

+1 − ¯

xk < +∞

k→∞

kxk − ¯

xk2

Metoda Newtona dla uk ladu równań

(P om) g : Rn → Rn znaleźć ¯x : g(¯x) = 0

Jeśli g różniczkowalna w sposób ciag ly i x

przybliżenie rozwiazania to ze wzoru Taylora

0 = g(¯

x) = g(x0) + g′(x0)(¯

x − x0) + o(k¯

x − x0k)

rozwiazanie uk ladu (jeśli istnieje)

0 = g(x0) + g′(x0)(x − x0)

daje lepsze przybliżenie niż x0

uk lad ma rozwiazanie gdy : jakobian g′(x

0) nieosobliwy

: [g′(x0)]−1 istnieje

Schemat iteracyjny metody Newtona dla (P om): xk+1 := xk − [g′(xk)]−1g(xk)

(1)

kierunek dk = −[g′(xk)]−1g(xk) nazywamy kierunkiem Newtona

Jeśli zamiast [g′(xk)]−1 w tym schemacie wystepuje

aproksymacja Jk to otrzymujemy metode ’typu

Newtona’ dla (P om):

xk+1 := xk − Jkg(xk)

(2)

Twierdzenie o zbieżności metod ’typu Newtona’

Twierdzenie 1.1 Niech g : Rn → Rn różniczkowalna, x0 ∈ Rn, J0 ∈ Rn×n, ε > 0. Za lóżmy, ze: 1. ¯

x rozwiazanie: g(¯

x) = 0, kx

0 − ¯

xk < ε

2. g′(x)−1 istnieje dla x ∈ B(¯

x, ε) = {kx − ¯

xk < ε}

oraz sup{kg′(x)−1k : x ∈ B(¯

x, ε)} ≤ M1(sta la)

3. g′ spe lnia warunek Lipschitza na clB(¯

x, ε) ze

sta la L

4. θ0 := LM1 kx

0 − ¯

xk + M0K < 1 gdzie

K sta la: k(g′(x0)−1−J0)y0k ≤ K, y0 := g(x0)/kg(x0)k M0 sta la: M0 := max{kg′(x)k : x ∈ B(¯

x, ε)}.

Niech (2) realizowany jest z poczatkowym x

0 i Jk

spe lniajacym jeden z warunków:

(i) k(g′(xk)−1 − Jk)ykk ≤ K

(ii) k(g′(xk)−1 − Jk)ykk ≤ θkK, θ

1 ∈ (0, 1),

(iii) k(g′(xk)−1 − Jk)ykk ≤ min{M2kg(xk)k, K}, M2 > 0.

Wtedy:

Jeśli (i), to xk → ¯

x z rzedem liniowym.

Jeśli (ii), to xk → ¯

x z rzedem superliniowym.

Jeśli (iii), to xk → ¯

x z rzedem 2.

UWAGA: warunki (i) − (iii) nie gwarantuja , że

Jk → g′(¯

x)−1

Metoda Newtona dla zadania minimal-

izacji

(P )

infx∈Rn

f (x)

gdzie f : Rn → R jest dwukrotnie różniczkowalna w sposób ciag ly

Twierdzenie 1.5(tw. Fermata) (wyk lad 12): jeśli f : Rn → R jest różniczkowalna i ¯

x jest ekstremum

(min lub max) lokalnym f , to ∇f (¯

x) = 0

x jest punktem krytycznym f jeśli ∇f (˜

x) = 0

w ogólności ˜

x nie musi być ekstremum lokalnym

Stosujemy metode Newtona do ∇f (x) = 0

Metoda Newtona dla (P ):

xk+1 := xk − [∇2f (xk)]−1∇f (xk)

(3)

kierunek dk = −[∇2f (xk)]−1∇f (xk) - kierunek Newtona

Metoda ’typu Newtona’ dla (P )

xk+1 := xk − Hk∇f (xk)

(4)

Hk - aproksymacja odwrotności hesjanu [∇2f (xk)]−1

Interpretacje

Ze wzoru Taylora: funkcja

fk(x) := f (xk)+∇f (xk)T (xk−x)+ (x−xk)T ∇2f (xk)(x−xk) 2

jest funkcja kwadratowa aproksymujaca f w punkcie

jako nastepny element ciagu x

k+1

wybieramy

minimum funkcji kwadratowej fk(x) ( o ile istnieje)

Jeśli fk(x) posiada minimum y∗ to jest to jej punkt krytyczny:

0 = ∇fk(y∗) = ∇f (xk) + ∇2f (xk)(y∗ − xk)

czyli schemat (3):

xk+1 = y∗ = xk − [∇2f (xk)]−1∇f (xk)

majac dany x

k+1 wybieramy xk+1 jako punkt kry-

tyczny funkcji kwadratowej fk(x) ktora najlepiej aproksymuje f w punkcie xk

Twierdzenie 2.1 Niech A bedzie macierza dodat-

nio określona n × n, b ∈

Rn, x0 ∈ Rn, a ∈ R.Wtedy

funkcja kwadratowa

f (x) = a + bT x + xT Ax

jest ściśle wypuk la i posiada dok ladnie jedno minimum x∗,

Ax∗ = −b

Metoda Newtona startujac z punktu x

ga x∗

0 osia֒

w jednej iteracji

x1 = x∗

Metoda Newtona jest metoda spadku

Twierdzenie 2.2 Niech {xk} ciag konstruowany metoda

Newtona. Jeśli

1. ∇2f (xk) jest dodatnio określony

2. ∇f (xk) 6= 0

to kierunek

dk = −[∇2f (xk)]−1∇f (xk)

jest kierunkiem spadku, tzn istnieje ε > 0 t.że f (xk + tdk) < f (xk)

dla 0 < t < ε.

Dowód. Określmy

ϕ(t) := f (xk + tdk).

ϕ(t) jest ograniczeniem f do prostej przechodzacej

przez xk i kierunku dk.

ϕ′(t) = ∇f (xk + tdk)dk

ϕ′(0) = ∇f (xk)dk = −∇f (xk)∇2f (xk)∇f (xk) < 0

bo ∇2f (xk) jest dodatnio określony i ∇f (xk) 6= 0.

Istnieje ε > 0 taki, że ϕ(t) < ϕ(0) dla 0 < t < ε

f (xk + tdk) < f (xk)

⊓

⊔

Twierdzenie o zbieżności schematu (4)

Twierdzenie 2.3 f : Rn → R dwukrotnie różniczkowalna, x0 ∈ Rn, H0 ∈ Rn×n, ε > 0. Za lóżmy, że: 1. istnieje ¯

x, kx0 − ¯

xk < ε t.że f (¯

x) ≤ f (x) dla

kx − ¯

xk < ε

2. istnieje δ > 0 t.że δkzk2 ≤ zT ∇2f (x)z dla x ∈

B(¯

x, ε)

3. ∇2f spe lnia warunek Lipschitza na clB(¯

x, ε)

ze sta la L

4. θ0 := L kx

2δ

0 − ¯

xk + M0K < 1 gdzie

K sta la: k(∇2f (x0)−1−H0)y0k ≤ K, y0 := ∇f (x0)/k∇f (x0)k M0 sta la: zT ∇2f (x)z ≥ M0kzk2 dla x ∈ B(¯

x, ε)}.

Niech (4) realizowany jest z poczatkowym x

Hk spe lniajacym jeden z warunków:

(i) k(∇2f (xk)−1 − Hk)ykk ≤ K

(ii) k(∇2f (xk)−1 − Hk)ykk ≤ θkK, θ

1 ∈ (0, 1),

(iii) k(∇2(xk)−1−Hk)ykk ≤ min{M2k∇f (xk)k, K}, M2 > 0.

Wtedy:

Jeśli (i), to xk → ¯

x z rzedem liniowym.

Jeśli (ii), to xk → ¯

x z rzedem superliniowym.

Jeśli (iii), to xk → ¯

x z rzedem 2.

Metody najszybszego spadku

f : Rn → R różniczkowalna w sposób ciag ly

Startujac z poczatkowego x

xk+1 := xk − tk∇f (xk)

(5)

gdzie tk ≥ 0 minimalizuje funkcje֒

ϕ(t) := f (xk − t∇f (xk)) t ≥ 0

Twierdzenie 3.1 W danym punkcie x0, wektor v := −∇f (x0)

jest kierunkiem najszybszego spadku wartości f Dowód

ϕu(t) := f (x0 + tu) t ≥ 0

ϕ′ (t) = ∇f (x

0 + tu)u,

ϕ′(0) = ∇f (x0)u

Dla jakiego kierunku u, kuk = 1, pochodna kierunk-owa ∇f (x0)u jest najmniejsza?

Jaki kierunek u w punkcie x0 zapewnia najwiekszy

spadek wartości f

Nierówność Cauchy-Schwartza

−k∇f (x0)k ≤ ∇f (x0)u ≤ k∇f (x0)k

∇f (x

u = −

k∇f (x0)k

⊓

⊔

Geometria metod najszybszego spadku Twierdzenie 3.2 Jeśli {xk} jesr ciagiem generowanym

przez metode najszybszego spadku, to dla każdego

k ∈ N

(xk+1 − xk)T (xk+2 − xk+1) = 0

wektory xk+1 − xk i xk+2 − xk+1 sa ortogonalne

Dowód

(xk+1 − xk)T (xk+2 − xk+1) = tk+1tk∇f (xk)T ∇f (xk+1) Ponieważ xk+1 = xk − tk∇f (xk), gdzie tk minimalizuje

ϕk(t) = f (xk − t∇f (xk))

t ≥ 0

0 = ϕk(tk) = −∇f (xk−tk∇f (xk))T ∇f (xk) = ∇f (xk+1)T ∇f (xk)

⊓

⊔

Twierdzenie 3.3 Ciag {x

k} generowany w metodzie

najszybszego spadku ma w lasność:

f (xk+1) < f (xk) o ile ∇f (xk) 6= 0

Dowó d

ϕk(t) = f (xk − t∇f (xk))

f (xk+1) = ϕ(tk) ≤ ϕk(t) t ≥ 0

ϕ′ (0) = −∇f (x

k − 0∇f (xk))T ∇f (xk)

= −∇f (xk)T ∇f (xk)

= −k∇f (xk)k2 < 0

ϕ′ (0) < 0 oznacza, że ϕ

ca, tzn

k jest lokalnie maleja֒

istnieje ¯

t > 0 t.że

ϕk(0) > ϕk(t) dla 0 < t < ¯t

f (xk+1) = ϕk(tk) ≤ ϕk(¯

t) < ϕk(0) = f (xk)

⊓

⊔

Twierdzenie 3.4 Niech f bedzie koercytywna, klasy

C1. Jeśli {xk} jest ciagiem generowanym przez

metode najszybszego spadku z dowolnego punktu

x0 ∈ Rn, to {xk} zawiera podciag zbieżny. Granica

każdego podciagu zbieżnego jest punktem kryty-

cznym f

Wniosek 3.1 Jeśli f jest ściśle wypuk la koercytywna klasy C1, to dla dowolnego punktu star-towego x0 ∈ Rn ciag generowany w metodzie na-

jszybszego spadku jest zbieżny do minimum