J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 1
PROGRAMOWANIE NIELINIOWE METODY NUMERYCZNE
Powody, dla których podczas rozwiązywania zadania będziemy musieli zastosowad metodę
numeryczną i zadowolid się rozwiązaniem przybliżonym:
I. Funkcja celu i/lub funkcje ograniczające są złożonej postaci.
II. Funkcja celu i/lub funkcje ograniczające nie są dane w postaci jawnych funkcji zmiennych
decyzyjnych.
III. Funkcja celu i/lub funkcje ograniczające nie spełniają założeo o ciągłości i różniczkowalno-
ści.
Idea algorytmu iteracyjnego:
w kolejnych iteracjach (krokach) znajduje się przybliżone rozwiązania zadania xk , przy
czym jeśli algorytm ma byd skuteczny, kolejne przybliżenia powinny byd lepsze od po-
(xk )>Q (xk+1)>K>Q Ć
(x),
przednich: Q
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 2
w większości algorytmów przejście pomiędzy kolejnymi punktami xk i xk+1 odbywa się w
ustalonym wg przyjętej strategii kierunku.
Ogólny schemat postępowania:
1 wybierz punkt startowy x0, przyjmij k =0,
(wyboru punktu dokonuje się w z góry ustalony sposób lub losowo),
2 znajdz kierunek dk , w którym należy podążad, aby poprawid (zmniejszyd) wartośd funkcji
(x),
Q
(x) i/lub
(strategie wyboru kierunku poszukiwao wynikają ze znajomości wartości funkcji Q
jej pochodnych),
3 znajdz długośd kroku (odległośd wyrażoną za pomocą liczby lk ) od punktu xk w kierunku
dk do punktu xk+1 będącego kolejnym poprawionym rozwiązaniem zadania,
Ć
(zadanie do rozwiązania: Q xk +lkdk min Q lk min lk =lk )
( )
( )
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 3
Ć
4 wyznacz kolejne poprawione rozwiązania zdania xk+1 =xk +lkdk ,
5 sprawdz kryterium zbieżności: czy rozwiązanie xk+1 jest zadawalająco dobrym przybliże-
Ć
niem rozwiązania optymalnego xk+1 @x. W przeciwnym przypadku wykonaj kolejną itera-
k =k +1
cję przyjmując i powród do punktu 2.
Cechy, które należy wziąd pod uwagę dobierając odpowiedni do rozwiązywanego zadania al-
gorytm:
ż zbieżnośd algorytmu,
Algorytm jest zbieżny, jeśli istnieje granica ciągu rozwiązao przybliżonych xk otrzymanych w
kolejnych iteracjach algorytmu:
Ć
lim xk =x (4.1)
kĄ
Jeśli przy tym k jest skooczone, to jest to algorytm o skooczonej zbieżności.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 4
Jeżeli algorytm jest zbieżny, to liczbę q ł1, dla której istnieje i jest skooczona granica:
Ć
xk+1-x
lim =r (4.2)
q
kĄ
Ć
xk -x
gdzie: promieo zbieżności,
r
nazywamy rzędem zbieżności.
W szczególności dla q =1 zbieżnośd algorytmu jest liniowa a dla q =2 kwadratowa.
ż wybór punktu startowego x0,
(x) ma wiele minimów lokal-
Efektywnośd zależy od wyboru punktu startowego x0. Jeśli Q
nych, algorytm doprowadzi nas do minimum lokalnego leżącego najbliżej punktu startowego.
Rada: wielokrotnie powtórz algorytm z różnych punktów startowych a następnie przeglądnij
otrzymany zbiór rozwiązao w celu wybrania minimum globalnego. Wykonaj szereg testów
(x) lub losowo wybieraj punkty startowe.
zgrubnie sprawdzających charakter funkcji Q
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 5
ż kryterium zatrzymania algorytmu,
(xk ) otrzymane w kolejnych iteracjach.
Zbadaj zmiany wektora xk i/lub wartości funkcji Q
Jeżeli zmiany te są mniejsze od założonej dokładności , to zakoocz algorytm.
e
Wniosek: czas realizacji algorytmu jest dodatkową cechą, która obok dokładności rozwiązania
charakteryzuje jego jakośd.
(x):
Klasyfikacja z uwagi na stopieo pochodnych funkcji celu Q
ż algorytmy rzędu zerowego (bezgradientowe),
(x).
Korzystają tylko z obliczonych wartości funkcji Q
ż algorytmy rzędu pierwszego (gradientowe),
(x); (kierunek -ŃTQ (x)(przeciwny do gra-
Korzystają z pierwszych pochodnych funkcji Q
dientu funkcji) jest kierunkiem jej najszybszego spadku).
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 6
ż algorytmy rzędu drugiego,
ł
(x) lub jej hesjanu ęHś.
Korzystają z drugich pochodnych funkcji Q
MINIMALIZACJA FUNKCJI JEDNEJ ZMIENNEJ
Po ustaleniu kierunku poszukiwao dk , problem znajdowania kolejnego punktu xk+1 sprowa-
dza się do minimalizacji funkcji jednej zmiennej:
Ć
(xk+1)=Q xk +lkdk =Q lk min
znajdz lk =lk takie, że Q (4.3)
( ) ( )
Ć
lub po podstawieniu lk =x , Q x min x =x
( )
ALGORYTMY BEZGRADIENTOWE PODZIAAU I REDUKCJI ORAZ INTERPOLACJI
Założenia:
(x) ma ona jedno minimum w punkcie x a,b ,
Q
Ć
(x) jest jednomodalna w przedziale x a,b .
Q
Ć
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 7
Def.
(x), taką że w punktach x1,x2,x a,b :
Funkcję Q Ć
Ć
1 dla x1
( ) ( )
Ć
2 dla x2 >x1 >x zachodzi Q x1 ( ) ( )
(x),
Ć jest minimum Q
gdzie: x
nazywamy jednomodalną w przedziale a,b .
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 8
ALGORYTM DYCHOTOMII
(x) jest jednomodalna w przedziale a,b i ma minimum w punkcie x a,b .
Q Ć
Początkowy przedział nieokreślono-
ści rozwiązania D0 =b-a .
1
x1 =a +
D0 -d
( )
2
(4.4)
1
x2 =a +
D0 +d
( )
2
d>0 mała wartośd dobrana
gdzie:
w taki sposób, aby punkty x1 i x2
różniły się znacząco.
ć
x + d ,b ,
a) jeśli Q x1 ŁQ x2 odrzucamy przedział
( ) ( )
0
Ł
2
d
.
b) Q x1 >Q x2 odrzucamy przedział
( ) ( )
a,x0 -
ł
2
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 9
Po kolejnych iteracjach k przedział nieokreśloności redukuje się następująco:
ćD0 +d d
1 1
+ , D3 = 1 ćD0 +d d d ,K,
D1 = , D2 =
D0 +d
( ) +
+
2 2 Ł ł 2 2 Ł
2 4 2ł 2
(4.6)
ć
D0
1- 1
Dk = +d
Łł
2k
2k
Ostatecznie po K iteracjach redukcja przedziału nieokreśloności wyniesie:
ćŁe
DK
1 d
1- 1
= + (4.7)
Łł
D0
D0 2K
2K
gdzie: e żądana dokładnośd rozwiązania.
Rozwiązując równanie (4.7) można wyznaczyd liczbę iteracji K gwarantującą uzyskanie wyni-
ku z dokładnością e. Np. dla d =0, 001D0 , e=0,1 , K ł4.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 10
ALGORYTM FIBONACCIEGO1)
Ciąg liczb Fibonacciego tworzą liczby:
Fk
{ }
F0 =F1 =1
(4.8)
Fk =Fk-1 +Fk-2 dla k =2, 3K
tj. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.
W przedziale a,b umieścimy punkty x1 i x2 w równych odległościach a2D0 od jego koo-
ców:
x1 =a +a2D0 , x2 =b-a2D0 =a + D0 (4.9)
1-a2
( )
FK-2
gdzie: a2 = .
FK
1)
Algorytm znany jest w literaturze także jako algorytm Kiefera.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 11
a) jeśli Q x1 ŁQ x2 , to odrzucamy przedział przyjmując:
( ) ( ) a + 1-a2 D0,b
( )
(
a2 =a , b2 =a + D0,
1-a2
( )
b) jeśli Q x1 >Q x2 , to odrzucamy przedział przyjmując:
( ) ( ) a,a +a2D0
)
a2 =a +a2D0 , b2 =b.
Długośd przedziału nieokreśloności wyniesie wtedy:
D2 = 1-a2 D0 (4.10)
( )
W kolejnych iteracjach dla k =3,4KK postępujemy podobnie obliczając:
FK-k
kk
ak = , x1 =ak-1 +akDk-1 , x2 =ak-1 + 1-ak Dk-1
( )
FK-(k-2)
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 12
ALGORYTM ZAOTEGO PODZIAAU
Nazwa złoty podział wywodzi się ze starożytnej Grecji, której architekci uważali, że właściwa
harmonia wymiarów (złota proporcja wysokości do podstawy) budynku, otworu drzwiowego,
okiennego itp. to taka, jaka wynika z podziału odcinka na dwie nierówne części w sposób po-
kazany na rysunku.
a2
Oznaczając: b = , prowadzi to do równania kwadratowego postaci:
a
b2 -3b +1=0
którego dodatni pierwiastek mniejszy od jedności jest równy:
a1
1 1
b =@0,382, oczywiście: =1-b = @0,618.
(3- 5) ( )
5-1
a 2
2
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 13
Algorytm złotego podziału przebiega tak samo jak algorytm Fibonacciego, przy czym
ak =b @0,382.
ALGORYTM INTERPOLACJI KWADRATOWEJ POWELLA
Bezgradientowe algorytmy podziału i redukcji wymagały znajomości początkowego przedziału
(x) posiadała minimum.
nieokreśloności, w którym funkcja Q
(x), którą będziemy przybliżad odcinkami parabolą
Rozpatrzymy wypukłą funkcję Q
(x)=a +bx +cx2 przechodzącą przez trzy punkty x1,x2,x3. Prawdziwy jest układ rów-
F
nao:
2
a +bx1 +cx1 =Q x1
( )
2
a +bx2 +cx2 =Q x2
a,b,c (4.11)
( )
2
a +bx3 +cx3 =Q x3
( )
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 14
Jeżeli punkty x1,x2,x3 rozmieścimy tak, aby: x1 =0, x2 =t, x3 =2t , to
a =QA
4QB -3QA -QC
b = , gdzie Q =QA, Q =QB , Q =QC (4.12)
x1 x2 x3
( ) ( ) ( )
2t
QC +QA -2QB
c =
2t2
(t) ma minimum w punkcie t*
Parabola F , w którym:
(t*)=0 t* =- b t t* = 4QB -3QA-QC t
ó
F (4.13)
2c 4QB -2QC -2QA
(t) miała mi-
Warunek (4.13) jest warunkiem koniecznym. Na to aby w punkcie t*funkcja F
nimum musi dodatkowo zachodzid:
(t*)>0 c =QC +QA -2QB >0 QA +QC >QB
óó
F (4.14)
2
2t2
Warunek (4.14) oznacza, że punkt B musi leżed poniżej prostej łączącej punkty A i C . Jest
(x).
spełniony zawsze dla wypukłej funkcji Q
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 15
Algorytm Powella:
1 dla k =0 przyjmij tk =0 oraz krok t ,
(tk ) i Q (tk+1),
2 oblicz tk+1 =tk +t oraz Q
(tk+1)>Q (tk ) dla k =0 to odwród
3 jeżeli Q
kierunek poszukiwao,
(tk+1)ŁQ (tk ) to podstaw t =2t i
4 jeżeli Q
powtórz krok 2dlak =k +1,
(tk+1)>Q (tk ) i k ł1 to podstaw
jeżeli Q
(tk+1 ).
t =0,5t i oblicz Q -t
Otrzymamy trzy punkty A,B,C w równych
t
odległościach od siebie.
5 przez punkty A,B,C poprowadz parabolę interpolującą i wyznacz jej minimum ze wzoru
(4.13).
F -Q
(t*) (t*)
Ć
6 jeżeli Łe, to przyjmij x @x1 +t* ,
Q
(t*)
w przeciwnym przypadku powtórz obliczenia z punktu B z krokiem o połowę mniejszym.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 16
ALGORYTMY GRADIENTOWE
Wykorzystują znajomośd pierwszej pochodnej funkcji Q x , która musi byd różniczkowalna i
( )
jej pochodną powinno dad się wyznaczyd w sposób jawny.
Wykorzystują dwie strategie:
a) szukanie miejsca zerowego pochodnej,
b) interpolowanie funkcji wielomianami wyższego stopnia, np. interpolacja sześcienna.
ALGORYTM SIECZNYCH
(x) jest wypukła klasy
Niech Q
1
C i ma minimum wewnątrz
przedziału a,b .
Algorytm:
k
1 dla k =0 podstaw x1 =a,
k
x2 =b,
k k
ó ó
2 oblicz Q x1 i Q x2 ,
( ) ( )
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 17
AB
3 znajdz współrzędną punktu przecięcia odcinka z osią :
x
k k k k k k k
ó ó ó ó ó
Q x2 -Q x1 Q x2 Q x1 x2 -Q x2 x1
( ) ( ), xm =x2 - ( ) ( ) ( )
kk
tga= = (4.15)
kk
kk
tga
x2 -x1 óó
Q x1 -Q x2
( ) ( )
k k
ó ó
4 oblicz Q xm i sprawdz, czy Q xm Łe, jeśli tak to zakoocz algorytm,
( ) ( )
kk kk k+1 k
óó óó
5 jeżeli Q xm Q x2 <0 to podstaw: x1+1 =xm, Q x1 =Q xm (rys.a).
( ) ( ) ( ) ( )
kk kk
óó
W przeciwnym przypadku podstaw: x2+1 =xm, Q x2+1 =Q xm , (rys.b),
( ) ( )
6 przyjmij k =k +1 i powród do punktu 2.
ALGORYTM INTERPOLACJI SZEŚCIENNEJ DAVIDONA
(x) przybliżamy przedziałami wielomianem trzeciego stopnia (krzywą sześcienną):
Funkcję Q
(x)=a +bx +cx2 +dx 3. Mamy zatem cztery warunki brzegowe (po dwa w każdym węz-
F
le interpolacji), które pozwolą zachowad ciągłośd interpolowanej funkcji oraz jej pochodnej.
óó óó
Oznaczając: Q x1 =QA, Q x2 =QB , Q x1 =QA, Q x2 =QB , otrzymamy:
( ) ( ) ( ) ( )
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 18
23
a +bx1 +cx1 +dx1 =QA
23
a +bx2 +cx2 +dx2 =QB
a,b,c,d (4.16)
2
ó
b+2cx1 +3dx1 =QA
2
ó
b+2cx2 +3dx2 =QB
Jeśli punkty x1 i x2 rozmieścimy tak, że x1 =0, x2 =t , to rozwiązując układ (4.16) wyzna-
(t)=a +bt +ct2 +dt3, która ma minimum wtedy, gdy
czymy krzywą interpolującą F
(t)=0 i F (t)>0.
ó óó
F
ALGORYTMY DRUGIEGO RZDU
Wykorzystują znajomośd funkcji, jej pierwszej pochodnej i drugiej pochodnej. Praktyka wyka-
zuje, że można w ten sposób przyspieszyd algorytm. Warto dodad, że w praktyce analityczne
obliczenie drugiej pochodnej może byd utrudnione.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 19
ALGORYTM NEWTONA2)
(x)jest jednomodalna i klasy C 2.
Q
(x)za pomocą szeregu Taylora z dokładnością do wyrazu z
W otoczeniu xk przybliżymy Q
drugą pochodną (aproksymacja kwadratowa):
(x)@Fk (x)=Q (xk )+Q (xk )(x -xk )+1Q (xk )(x -xk )2
ó óó
Q (4.17)
2
(x), którą potraktujemy jako przybliżenie funkcji
Równanie (4.17) przedstawia parabolę Fk
k
(x). Ma ona minimum w wierzchołku xm , którym przyjmiemy za przybliżenie punktu x
Q Ć bę-
(x).
dącego minimum funkcji Q
(xk )
ó
Q
k k k
(xk )+Q (xk )
ó ó óó
F xm =Q xm -xk =0 xm =xk - (4.18)
( ) ( )
(xk )
óó
Q
2)
Algorytm znany jest również w literaturze jako algorytm Newtona-Raphsona.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 20
(xk )0 (zbieżnośd kwadratowa).
óó
Algorytm osiąga największą zbieżnośd dla Q
(x) (x)
{ } { ó }
Przenosząc zadanie z płaszczyzny x,Q na płaszczyznę x,Q , zamiast szukad mi-
(x), możemy poszukiwad miejsca zerowego pochodnej Q (x) za pomocą stycz-
ó
nimum Q
nych do jej wykresu (rys. b).
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 21
Algorytm Newtona (metoda stycznych).
1 przyjmij k =0 i wybierz punkt startowy xk ,
(xk ), Q (xk ) i Q (xk ),
ó óó
2 oblicz Q
k
(x) w punkcie xk wg wzoru (4.18) i
3 znajdz minimum xm paraboli aproksymującej Q
przyjmij go za bieżące przybliżone rozwiązanie,
k
k
Ć
4 jeżeli xm -xk
k
podstaw k =k +1, xk =xm i powród do punktu 2.
(x) i Q (x) nie mogą byd wyrażone w sposób jawny lub jest to trudne,
ó óó
Jeżeli pochodne Q
to operator różniczkowania możemy zastąpid przybliżonym operatorem różnicowym (metoda
quasi-newtonowska).
k
-Q
)
(x +d)
-d
(xk )=Q (xk
ó
Q
2d
(4.19)
k
-2Q +Q
(xk ) (xk )
(x +d)
-d
(xk )=Q
óó
Q
d2
gdzie: d>0 krok o małej wartości.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 22
MINIMALIZACJA FUNKCJI WIELU ZMIENNYCH
ALGORYTMY MINIMALIZACJI W NIEZALEŻNYCH KIERUNKACH
Kierunek poszukiwania rozwiązania przybliżonego w iteracji k +1 nie zależy od kierunku w ite-
racji k
ALGORYTM GAUSSA-SEIDELA (RELAKSACYJNY)
Za kierunki dk wzdłuż których poszukuje się rozwiązania, przyjmuje się wersory ei układu
współrzędnych x1 Kxi Kxn . Wersory tworzą bazę kierunków poszukiwao:
[1K0K0]T
e1 =
M
[0K1K0]T
ei = ,
M
[0K0K1]T
en =
która jest niezmienna.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 23
Algorytm:
1 wybierz punkt startowy x0,przyjmij k =0, i =1,
2 podstaw xk =xk ,
i
3 jeżeli iŁn, przejdz do punktu 4, w przeciwnym przypadku przejdz do punktu 5,
Ć
4 w kierunku wersora ei znajdz odległośd lik od punktu xk , w jakiej funkcja Q
xk +likei
( )
i
i
Ć
3)
ma minimum , wyznacz punkt xk+1 =xk +likei i przyjmij go za punkt początkowy kolejnej
i i
i =i +1
minimalizacji podstawiając xk =xk+1, podstaw i powród do punktu 3,
i+1 i
5 przyjmij punkt xk+1 =xk za nowy punkt startowy,
i
Ć
6 jeżeli
xk -xk-1 w przeciwnym przypadku podstaw k =k +1, i =1 i powród do punktu 2.
3)
k
Zadanie sprowadza się do minimalizacji funkcji jednej zmiennej i może być rozwiązane za pomocą jednej z opisanych poprzednio metod po przyjęciu żądanej do-
q
i
kładności rozwiązania zadania dla kierunku .
ei
i
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 24
ALGORYTM NAJSZYBSZEGO SPADKU
Kierunek przeciwny do gradientu jest
kierunkiem najszybszego spadku funkcji
i ten właśnie kierunek przyjmowany jest
za kierunek poszukiwao w kolejnych
iteracjach algorytmu.
Algorytm:
1 wybierz punkt startowy x0, przyjmij
k =0,
(xk ) i przyjmij
2 oblicz gradient ŃQ
za kierunek poszukiwao wektor
(xk ),
dk =-ŃQ
xk dk
3 znajdz odległośd od punktu w kierunku w jakiej funkcja Q xk +lkdk ma mini-
( )
mum,
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 25
Ć
4 wyznacz punkt xk+1 =xk +lkdk ,
4)
Ć
5 jeżeli xk+1-xk W przeciwnym przypadku podstaw k =k +1 i powród do punktu 2.
ALGORYTMY MINIMALIZACJI W KIERUNKACH SPRZŻONYCH
Kierunki poszukiwao w bieżącej iteracji są zależne od kierunków zastosowanych poprzednio.
Nazwiemy je kierunkami sprzężonymi (zależnymi).
Konsekwencje:
ż kierunek sprzężony uwzględnia informację o wszystkich przyjętych dotąd kierunkach poszu-
kiwao uwzględni globalny charakter minimalizowanej funkcji. Inaczej, ma pamięd .
Jest to niewątpliwie korzystna cecha algorytmu.
ż wyznaczenie kierunku sprzężonego zwiększa nakład obliczeo potrzebnych na wykonanie ko-
lejnej iteracji. To z kolei pogarsza efektywnośd algorytmu.
4)
Za kryterium zakończenia obliczeń przyjmuje się także .
Q xk
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 26
W większości zastosowao praktycznych algorytmy kierunków sprzężonych są efektywniejsze
od algorytmów poszukiwao w ustalonych (niezależnych) kierunkach.
Def.
[A]nn
Niech będzie dodatnio określoną macierzą symetryczną. Zbiór K wektorów (kierun-
{dk }nazywamy zbiorem wektorów (kierunków) sprzężonych względem macierzy [A],
ków)
jeżeli:
[A]dl =0 dla k ąl, k =1KK, l =1KK
dkT (4.20)
[A]=[I], to kierunki sprzężone są kierunkami ortogonalnymi
Uwaga: jeśli
[I]dl =dkTdl =0
dkT
%
Rozważymy funkcję Q x , która jest wypukła w otoczeniu punktu x i może byd w tym oto-
( )
czeniu aproksymowana funkcją kwadratową:
%
(x)@ 1 xT [A]x+bTx+c=Q (x)
Q (4.21)
2
oraz kierunek określony przez wektord.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 27
Tw.
Jeżeli dla dwóch różnych punktów startowych xA i xB minima funkcji Q x w kierunku d
( )
(x1 ) są sprzężone względem macierzy
znajdują się w punktach x1 i x2, to wektory d i -x2
(x1 )=0 (1.22)
[A], czyli:dT [A]
-x2
Tw.
Jeżeli poszukiwania minimum funkcji
(x) będą prowadzone w kolej-
Q
nych iteracjach z wykorzystaniem
kierunków sprzężonych względem
[A], to zostanie ono osią-
macierzy
gnięte co najwyżej po K iteracjach
niezależnie od wyboru punktu star-
towego.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 28
ALGORYTM KIERUNKÓW SPRZŻONYCH POWELLA
Jest rozszerzeniem algorytmu Gaussa- Seidela.
Baza kierunków poszukiwao jest w każdej iteracji modyfikowana o kierunek sprzężony, który
w następnej iteracji zastępuje jeden z przyjętych dotąd kierunków poszukiwao.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 29
Algorytm:
)
5
1 wybierz punkt startowy x0, przyjmij k =0 oraz początkową bazę kierunków poszukiwao -
k
wersory kartezjaoskiego układu współrzędnych e1 Kek Kek ,
in
(x) w kierunku ek a otrzymane w wyniku minimum
2 z punktu xk dokonaj minimalizacji Q
i
xk przyjmij za pośredni punkt startowy następnej minimalizacji. Postępowanie powtórz dla
i
kolejnych kierunków i =n,1,2,K,n-1,n.
3 ostatni z punktów xk przyjmij za nowy punkt startowy xk+1.
n+1
Ć
Jeżeli xk+1-xk k
xk -x1
n+1
4 wyznacz kierunek sprzężony: ek = .
n+1
k
xk -x1
n+1
Dokonaj modyfikacji kierunków bazy przyjmując: ek+1 =ek dla i =1,2Kn
ii+1
5)
wersory tworzące bazę muszą być liniowo niezależne. Jeśli punkt startowy wybierze się tak, że funkcja ma minimum wzdłuż jednego z kierunków , to w bazie są
eik x0 eik
kierunki liniowo zależne. Wtedy należy dokonać modyfikacji kierunków bazy tak, aby były liniowo niezależne.
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 30
Jeżeli wersory wyznaczające zmodyfikowaną bazę kierunków poszukiwao są liniowo nieza-
)
6
leżne , powród do punktu 2. W przeciwnym przypadku przywród początkową bazę kierun-
ków poszukiwao i powród do punktu 2.
ALGORYTM SPRZŻONEGO GRADIENTU FLETCHERA-REEVSA
W algorytmie najszybszego spadku w kolejnych iteracjach wyznaczymy kierunki sprzężone do
gradientu i wykorzystamy je jako kierunki poszukiwao.
(xk ) i dk-1, przy czym wek-
Kierunek dk wyrazimy jako liniową kombinację wektorów -ŃQ
tor dk-1 był poprzednio przyjętym kierunkiem poszukiwao:
(xk )+bkdk-1
dk =-ŃQ (4.23)
Współczynnik bk dobierzemy tak, aby każdy następny wektor dk był sprzężony względem po-
przednich wektorów d1 Kdk-1.
6)
k k
wersory tworzące bazę kierunków poszukiwań są liniowo niezależne, jeśli wyznacznik
e1 Keik Ken 0
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 31
Można wykazad, że zachodzi o wtedy, gdy
2
(xk+1)
ŃQ
bk+1 = (4.24)
2
(xk )
ŃQ
J.Stadnicki Optymalizacja- wykład dla Informatyki, częśd4: PROGRAMOWANIE NIELINIOWE metody numeryczne 32
Algorytm:
(xk ) i wyznacz kierunek
1 wybierz punkt startowy x0, przyjmij k =0, oblicz gradient ŃQ
(xk ).
poszukiwao dk =-ŃQ
(x) wychodząc z punktu xk w kierunku dk wyznaczając
2 dokonaj minimalizacji funkcji Q
Ć
punkt xk+1 =xk +lkdk ,
(xk+1),
3 oblicz gradient ŃQ
(xk+1)
Ć
4 jeżeli ŃQ ku:
(xk+1)+bk+1dk ,
k 41. jeśli wyznacz kierunek sprzężony dk+1 =-ŃQ
przyjmij go za nowy kierunek poszukiwao. Podstaw k =k +1 i powród do punktu 2.
(xk+1) i powród do
42. w przeciwnym przypadku podstaw k =0, x0 =xk+1, d0 =-ŃQ
punktu 2.
Wyszukiwarka
Podobne podstrony:
Wykad
wykad 10 2
wykad wywazanie 2
wykad 3
Wykad 3 PLC
wykad 9
Zakaenia szpitalne wykad
wykad 09
wykad 4
Gospodarka a rodowisko wykad 2
zdrowie publiczne wykad 23
Wykad 1
wykad 2
Wykad 05
Wykad 4
wykad 11 waiwoci optyczne
wykad 10
więcej podobnych podstron