Minimalizacja funkcji jednej lub wielu zmiennych
Wykład 13
Optymalizacja = wyznaczenie minimum funkcji rzeczywistej wielu zmiennych
w danym obszarze (wraz z punktem w którym to minimum występuje).
Jeśli funkcja jest nieliniowa i zawiera wiele minimów lokalnych zadanie jest
trudne do rozwiÄ…zania.
Wynik lokalnych procedur iteracyjnych (które opierają się na linearyzacji
minimalizowanej funkcji w otoczeniu wybranego punktu w przestrzeni n-
wymiarowej) jest silnie uzależniony od wyboru modelu startowego.
Metody eliminacji (złotego podziału,
Rozpoczniemy od metod minimalizacji ciągłej funkcji unimodelnej tj takiej
która w przedziale [a,b] ma tylko jedno minimum lokalne.
Jeżeli zadana funkcja nie posiada tej własności, należy znalez
ć jej przedziały
unimodalności i zastosować opisywaną metodę do każdego z nich.
Jeśli dla a < x* < b zachodzą warunki f(a) > f(x*) i f(x*) < f(b) to:
- funkcja ma w przedziale [a,b] minimum w punkcie x*
- potrzeba trzech punktów do zlokalizowania minimum
Funkcja ciągła f w przedziale [a,b] posiada dokładnie
jedno minimum x*. Minimum to można znalez
ć
Przedziały [a,xR].i
poprzez kolejne podziały zadanego przedziału. W
[xL,b] zachodzÄ… na
tym celu należy obliczyć wartości funkcji w dwóch
siebie. Przedział jest
punktach xL i xR takich, że a < xL < xR < b, a
zawężany w stosunku
następnie zbadać ich wielkości:
k= [a,xR]./ [a,b]
- Jeżeli f(xL) > f(xR), to szukane minimum
znajduje siÄ™ w przedziale [xL,b].
- Jeżeli f(xL) < f(xR), to szukane minimum
znajduje siÄ™ w przedziale [a,xR].
a xL xR b
Metoda złotego podziału
Wielkość otrzymanego w wyniku powyższego postępowania przedziału po n
krokach wynosi: (b(n) - a(n))kn gdzie k jest stałym współczynnikiem o który
zmniejszana jest wielkość przedziałów w kolejnych krokach algorytmu.
Wartość współczynnika k jest dobrana w taki sposób, aby przy kolejnych
iteracjach wykorzystywać obliczoną w poprzednim kroku wartość funkcji
jednej z dwóch próbek (f(xL) lub f(xR)). Obliczmy tę wartość:
b - xL xR - a
k = = czyli b - xR = xL - a
b - a b - a
ponieważ f(xL) > f(x ) zawężamy przedział do [x ,b].
ponieważ f(x ) > f(xR) zawężamy przedział do [xL,b].
a xL xR b
b - xR
a xL
k =
b - xL
b b
b - xR xL - a xL - b - (a - b) 1 1
xL xR
k = = = = -1+ = -1+
b - xL
b - xL b - xL b - xL k
b - a
1
k = -1+
k
5 -1
2
k + k -1 = 0 k = = 0.618
2
Strategię obliczania minimum funkcji można zapisać:
Jeśli:
Jeśli to STOP, w przeciwnym wypadku powtórz
punkt 2.
Metoda interpolacji parabolicznej
1
p(x)= Ax2 - bx + c
2
dp(x) b
0 = = Ax - b Ò! x* =
dx A
Funkcja wystarczająco gładka:
" w pobliżu minimum funkcja
kwadratowa jest dobrym
przybliżeniem
" parabola dopasowana do dowolnych
" parabola dopasowana do dowolnych
trzech punktów powinna wskazać
w jednym kroku minimum albo
przynajmniej w jego bliskie otoczenie.
1 2
Jeśli to p(x)- p* = A(x - x*)
p(x*)= p*
2
RozwijajÄ…c dowolnÄ… funkcjÄ™ f(x) w szereg Taylora otrzymujemy
1
2
2 2 2
p(x)= p(x0)+ p (x0)(x - x0)+ p (x0)(x - x0) +K
2
widać, że dla x0=x* mamy p (x0)=0 i parabola lokalnie przybliża f(x)
p(x)= y = a2x2 + a1x + a0
Dla trzech punktów (xa,ya), (xb,yb) i (xc,yc) parabola
Przechodząca przez te punkty będzie miała postać:
2
y = c2(x - xb) + c1(x - xb)+ c0 gdzie c0 = yb
Ponieważ dla pozostałych dwóch punktów mamy:
2
ya = c2(xa - xb) + c1(xa - xb)+ yb
2
yc = c2(xc - xb) + c1(xc - xb)+ yb
możemy wyznaczyć wartości parametrów c1 i c2:
2 2
c1 = C[(xc - xb) (ya - yb)-(xa - xb) (yc - yb)]
c2 = C[-(xc - xb)(ya - yb)+ (xa - xb)(yc - yb)]
1
C =
gdzie
2 2
(xa - xb)(xc - xb) -(xc - xb)(xa - xb)
c1
oraz wartość paraboli w maksimum p* = xb -
2c2
Metoda Brandta (wykorzystująca metodę złotego podziału i interpolacji
parabolicznej
1. Wyznaczamy przedział [xa,xb].
2. Wyznaczamy metodą złotego podziału punkt xi leżący w jego
wnętrzu będący pierwszym przybliżeniem minimum
3. Ponownie stosujemy  złoty podział by znalez
ć xi+1 i zdefiniować
nowy, zawężony przedział
4. Wyznaczamy parabolÄ™ i wyznaczamy jej minimum x*
5. Jeśli x* leży w ostatnio zdefiniowanym przedziale oraz gdy zmiana
położenia minimum jaka miała miejsce przy wykonaniu ostatniej
położenia minimum jaka miała miejsce przy wykonaniu ostatniej
iteracji była mniejsza od połowy zmiany położenia minimum w
przedostatniej iteracji kończymy procedurę, jeśli któryś z warunków
nie jest spełniony  powrót do punktu 3.
Metody minimalizacji funkcji n zmiennych (minimalizacja w
przestrzeni n-wymiarowej)
Numeryczne metody poszukiwania minimum funkcji wielu zmiennych można
podzielić na następujące klasy:
" metody poszukiwań prostych, takie jak metoda Hooka-Jevesa i metoda
Rosenbrocka
" metody poprawy kierunków, wśród których możemy wyróżnić następujące
grupy:
grupy:
" metody bezgradientowe, w przypadku których do znalezienia minimum
potrzebne jest wyznaczanie jedynie wartości funkcji f(x), np. metoda
Gaussa-Seidela i metoda Powella
" metody gradientowe, dla których w procesie poszukiwania minimum
korzystamy z wyznaczanych wartości minimalizowanej funkcji f(x) oraz
jej gradientu, np. metoda najszybszego spadku i metoda gradientu
sprzężonego;
" metody newtonowskie i quasi-newtonowskie, gdzie poszukiwanie
minimum przeprowadzamy z wyznaczaniem w kolejnych punktach
wartości funkcji, jej gradientu oraz hesjanu
Dla wszystkich typów metod należących do klasy metod poprawy
kierunków wykorzystujemy wspólny schemat prowadzenia obliczeń
iteracyjnych. Polega on na tym, że do punktu odpowiadającego minimum
funkcji f(x), dochodzimy w kolejnych krokach poszukiwania minimum wzdłuż
odpowiednio wyznaczonych kierunków d w przestrzeni n-wymiarowej,
zwanych kierunkami poszukiwań.
Jeżeli po k-1 krokach optymalizacji osiągnięto punkt poszukiwań xk-1 to w
kolejnym k-tym kroku przeprowadza się minimalizację wzdłuż prostej
wyznaczonej przez punkt xk-1 i wektor kierunku d, tj. znajdujemy takÄ…
optymalna wartość ąk, że
optymalna wartość ąk, że
Ä…k : min f (xk -1 +Ä…kd)
Ä…k
a więc rozwiązujemy zagadnienie minimalizacji funkcji jednej zmiennej - tą
zmiennÄ… jest Ä…k
Kierunki te mogą być stałe w trakcie całego iteracyjnego procesu
poszukiwań minimum bądz
też mogą ulegać zmianie na kolejnych etapach
w zależności od wartości minimalizowanej funkcji, jej gradientu lub również
hesjanu.
Iteracyjne algorytmy optymalizacji mają następujące fazy:
" wybór punktu początkowego poszukiwań x0
" wyznaczenie kolejnego punktu xk, stanowiącego przybliżenie minimum x*;
punkt ten wyznaczamy przez poszukiwania wzdłuż kierunku dk, którego
określenie, jak i również odległość przesunięcia w tym kierunku są zależne
od wybranej metody optymalizacji; kolejny punkt, będący nowym (lepszym)
przybliżeniem punktu minimalizującego funkcję f(x) , jest wyznaczany z
zależności:
xk = xk -1 +Ä…kdk
" sprawdzenie warunków zbieżności (kryterium osiągnięcia punktu
" sprawdzenie warunków zbieżności (kryterium osiągnięcia punktu
minimalnego wskaz
nika jakości) i  w zależności od wyniku  kontynuowanie
poszukiwań iteracyjnych albo ich zakończenie.
Ważna uwaga: Punkt początkowy wybierany jest na podstawie posiadanych
informacji dotyczących położenia minimum (często po prostu losowany).
W przypadku minimalizacji funkcji wielu zmiennych dobór punktu
początkowego poszukiwań może w znaczący sposób przyspieszyć lub
opóz
nić znalezienie minimum wskaz
nika jakości albo wręcz zdecydować o
możliwości znalezienia minimum globalnego funkcji.
Minimalizacja wzdłuż kierunków współrzędnych
Wektorom bazy ei, i=1,N przypisujemy kierunki w
których odbywać się będzie minimalizacja (tak jak
e2
dla przypadku 1 zmiennej).
Algorytm:
1. Z punktu startowego x0 minimalizujemy
funkcję wzdłuż prostej wyznaczonej przez e1 i
wyznaczamy minimum w punkcie x1
2. Z punktu x1 minimalizujemy funkcjÄ™ w kierunku
e2 i wyznaczamy kolejny punkt x2
e2 i wyznaczamy kolejny punkt x2
3. Kontynuujemy wzdłuż kolejnych osi i
x2
ostateczne znajdujemy punkt xN
4. Powracamy do minimalizacji wzdłuż kierunku
e1 i powtarzamy procedurÄ™ kolejny raz
x0 x1
e1
5. Minimalizacja kończy się gdy spełniony jest
warunek:
f (xn-1)- f (xn)< µ f (xn) + t
gdzie µ jest dokÅ‚adnoÅ›ciÄ… reprezentacji
maszynowej liczb użytą w obliczeniach a t
parametrem dobieranym indywidualnie.
Metoda kierunków sprzężonych (Powell'a)
Metoda kierunków sprzężonych jest bezgradientową, iteracyjną metodą
optymalizacji bez ograniczeń. Dla form kwadratowych jest ona zbieżna w N
krokach. W metodzie Powell'a baza zmienia siÄ™ w trakcie wykonywania algorytmu.
Modyfikacja bazy polega na stworzeniu i dodaniu do niej nowego sprzężonego
kierunku i równoczesnym usunięciu z niej takiego kierunku, wzdłuż którego
nastąpiło największe przesunięcie.
Metoda kierunków sprzężonych (Powell'a)
Algorytm:
1. xp := x
2. Dla każdego z kierunków k=1, 2, ..., N wybieramy optymalny krok mk
dokonując minimalizacji jednowymiarowej wzdłuż kierunku ek
3. x := x + m1e1 + m2e2 + ... + mNeN
4. Wyznacz kierunek sprzężony i podstawiamy
eN +1 = x - xp x - xp
x := x + mN+1eN+1 , gdzie mN+1 jest optymalnym krokiem uzyskanym w
wyniku minimalizacji funkcji g(mN+1)=f(x+mN+1eN+1)
x - xp < µ
5. Jeżeli (zachodzi warunek stopu) to koniec obliczeń
6. xp := x
6. xp := x
7. wyznaczamy numer kierunku k (1d"kd"N), w którym nastąpiło największe
przesunięcie (kierunek dla którego mk było największe)
mk d x - x e" µ
8. Jeżeli (wyznacznik dla nowej bazy - stopień liniowej
p
niezależności - jest bezpiecznie duży), to zmień bazę:
ek := eN+1 i d := mk d x - x
p
9. przejdz
do pkt. 2