426 2

426

10. Optymalizacja

cowych

(10.5.7)

Niech wielomian ()(/.) osiąga ekstremum w punkcie A’. W symbolice ilorazów różni vych z § 7.3.3 2' wyraża się wzorami

ii/Za, 6]-v/[ó.c] i((n + ó)(l-0)+(fc + c)Ą

(zob. zadanie 3 z § 10.5). Jeśli y[a, b, c]<0, to Q nie ma minimum w A'. Jeśli tak się z^iar^ lub jeśli A'>m, to ten z punktów a, b, c, który leży najdalej od m, zmienia się na m i _pov/. tarza się interpolację. Jeśli a, b lub c już było równe m, to przyjmuje się, że i kończy się poszukiwanie wzdłuż prostej.

Przypuśćmy teraz, że ip[a,b,c]>d i A' <m. Wtedy Q w punkcie A' ma minimum. Oblicza się y/QJ) i jeśli

|^(A)-min{^(a),^(b), ^(e)}|«$e lub ('-')-<>

to uznaje się, że X_V=A'. Jeśli żadna z tych nierówności nie jest spełniona, to powtarza się interpolację kwadratową po zmianie a, b lub c na A'. Odrzuca się zwykle punkt, gdzie wartość funkcji jest największa, ale nie robi się tak, gdy tylko usunięcie mniejszej wartości dałoby obramowanie minimum. Jeśli punkty są uporządkowane, tak że a<b<c> to „obramowanie minimum’⁵ oznacza, że y{b)<y{a) i i/(ó) <iy(e).

W wielu zastosowaniach obliczanie funkcji jest bardzo kosztowne. Trzeba więc być ostrożnym i nie wybierać zbyt małego c. Niektórzy zalecają przerywać poszukiwanie wzdłuż prostej, gdy tylko obramowano minimum. Wolfe rozważa ten problem w SIAM Reeiew II (1969), str. 226 - 235.

Gdy gradient g(x_%) jest znany, początek poszukiwań można uprościć. Niech będzie a=b-0. c=k. Z § 7.3.7 wynika, że

(10.5.8)    v [0.0] = ^(0)= -dlg{x_v),

co pozwala zastosować wzory (10.5.7).

10.53. Algorytmy optymalizacji bezwarunkowej

Metoda najszybszego spadku (Cauchy, 1847). Przyjmuje się tu, że

d_t=§(Xy)>    A_v>0.

Zauważmy, że 0^T(x_r) </,= ||g(x_r)||²>0. Kierunek gradientu jest kierunkiem spadku. todę zaleca się stosować, gdy jest się daleko od ic. Zaletą metody jest to, że hesjan stąj® się zbędny. Lokalnie metoda ma wymienioną w jej nazwie własność optymalną; zadanie 2 do § 10.5. Na przestrzeni wielu iteracji zbieżność może być jednak wolna; too-rys. 10.5.2.    jM

Spowolniona metoda Newtona (modyfikacja algorytmu Biggsa i Dixona, 1970). _

/<9^r9)    ^

(10.5.9) d_v

G~\xj)g{x,)_t jeśli G~^l istnieje i g^JG~¹g>m*x f—_T—, Cy < g(x_v) w przeciwnym razie.