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 transformacją liniową wektora Y1 to : Y0T W = 0
wektory Y0 i W są ortogonalne
Odwrotnie, przypuśćmy, że zadany jest dowolny 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 przemieś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żeli potrafimy określić zbiór kierunków sprzężonych, to poszukiwanie ekstremum funkcji kwadratowej można sprowadzić do wykonania 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żeli potrafimy określić zbiór kierunków sprzężonych, to poszukiwanie ekstremum funkcji kwadratowej można sprowadzić do wykonania 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 kolejnymi kolumnami macierzy jednostkowej, X01…
... zobacz całą notatkę
Komentarze użytkowników (0)