Metody i algorytmy optymalizacji- wykład 6

Nasza ocena:

5
Pobrań: 224
Wyświetleń: 1008
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Metody i algorytmy optymalizacji- wykład 6 - strona 1 Metody i algorytmy optymalizacji- wykład 6 - strona 2 Metody i algorytmy optymalizacji- wykład 6 - strona 3

Fragment notatki:

Metody i algorytmy optymalizacji dr Helena Spyra Wykład 6
Kierunki sprzężone
Niech w pkt X0 będzie ustalony kierunek przemieszczania Y0 i wybrany na nim punkt X1 tak, aby f (X1) = mint f (X0 + t •Y0)
W X1 określamy kierunek Y1 tak, aby prosta generowana przez Y1 przechodziła przez punkt ekstremalny funkcji
X2 określamy tak, aby X2 jest punktem ekstremalnym funkcji f (X) (uzyskaliśmy ekstremum w dwóch iteracjach)
Dla wektorów Y0 i Y1 zachodzi Y0T CY1 = 0
Jeżeli CY1 =W gdzie W jest trans­formacją liniową wektora Y1 to : Y0T W = 0
wektory Y0 i W są ortogonalne
Odwrotnie, przypuśćmy, że zadany jest do­wolny wektor Y0 i na prostej generowanej przez ten wektor określony jest punkt X1 . Przyjmijmy, że udało się znaleźć taki wektor Y1, że Y0TCY1= 0 . Na prostej przechodzącej przez X1 i generowanej przez Y1 znajduje się punkt ekstremalny funkcji. Dla funkcji f (X) = ½ XTCX + PTX X € Rn C - dodatnio określona, symetryczna Zbiór niezerowych wektorów Y0,…,Yn-1 nazywamy zbiorem
wektorów C-sprzężonych ze względu na dodatnio określoną macierz C,
gdy dla dowolnych wskaźników i,j i ≠ j
YiTCYj = 0
Wektory Y0 ,…, Yn-1 C - sprzężone
tworzą zbiór wektorów liniowo niezależnych
Załóżmy, że znamy zbiór Y0 ,…, Yn-1 kierunków sprzężonych. Niech X0 jest dowolnie wybranym punktem. Z punktu X0 prze­mieścimy się optymalnie wzdłuż wektora Y0 do punktu X1 , w którym
Ponieważ w punkcie X1 musi zachodzić równość Y0TG1 = 0 możemy efektywnie wyznaczyć wartość t0* G1= C ( X0 + t0* Y0) + P
Załóżmy, że określiliśmy optymalny ciąg punktów X0,…,Xk i chcemy określić punkt Xk+1 Jeżeli wektory Y0,…, Yn-1 są kierunkami C-sprzężonymi, to jest punktem, w którym f (X) osiąga swoje minimum.
Jeże­li potrafimy określić zbiór kierunków sprzężonych, to poszuki­wanie ekstremum funkcji kwadratowej można sprowadzić do wykona­nia n iteracji
metoda Grama-Schmidta
Przyjmijmy, że znamy macierz C i dowolny zbiór wektorów liniowo niezależnych R0,…,R

(…)

…, to jest punktem, w którym f (X) osiąga swoje minimum.
Jeże­li potrafimy określić zbiór kierunków sprzężonych, to poszuki­wanie ekstremum funkcji kwadratowej można sprowadzić do wykona­nia n iteracji
metoda Grama-Schmidta
Przyjmijmy, że znamy macierz C i dowolny zbiór wektorów liniowo niezależnych R0,…,Rn-1 (mogą to być wektory jednostkowe osi układu współrzędnych)
Przyjmujemy Y0 = R0Y1 = R1 + c10Y0 c10…
… + 4,1623
otrzymujemy: t1* = 1,06 W punkcie X2 , G2 = 0 f (X2) = 0 czyli f (X) ma minimum
Metoda Powella
Niech X0 , X1 są dowolnymi punktami, a Y jest niezerowym wektorem
Niech f (X0*) = mint f (X0 + t ∙Y)
i f (X1*) = mint f (X1 + t ∙Y) Wtedy wektor X1*- X0* jest sprzężony z wektorem Y czyli: YT C (X1* - X0*) = O
Niech X01 jest punkiem startowym, a Ro ,…,Rn-1 kolej­nymi kolumnami macierzy jednostkowej, X01…
... zobacz całą notatkę

Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz