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.

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 znaleźć 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

Metody eliminacji (złotego podziału,

Funkcja ciągła f w przedziale [a,b] posiada dokładnie
jedno minimum x*. Minimum to można znaleźć
poprzez kolejne podziały zadanego przedziału. W
tym celu należy obliczyć wartości funkcji w dwóch
punktach x

L

i x

R

takich, że a < x

L

< x

R

< b, a

następnie zbadać ich wielkości:
- Jeżeli f(x

L

) > f(x

R

), to szukane minimum

znajduje się w przedziale [x

L

,b].

- Jeżeli f(x

L

) < f(x

R

), to szukane minimum

znajduje się w przedziale [a,x

R

].

a

b

x

L

x

R

Przedziały [a,x

R

].i

[x

L

,b] zachodzą na

siebie. Przedział jest
zawężany w stosunku
k= [a,x

R

]./ [a,b]

Wielkość otrzymanego w wyniku powyższego postępowania przedziału po n
krokach wynosi: (b

(n)

− a

(n)

)k

n

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(x

L

) lub f(x

R

)). Obliczmy tę wartość:

a

b

a

x

a

b

x

b

k

R

L

−

−

=

−

−

=

a

x

x

b

L

R

−

=

−

czyli

ponieważ f(x ) > f(x ) zawężamy przedział do [x ,b].

Metoda złotego podziału

a

b

x

L

x

R

ponieważ f(x

L

) > f(x

R

) zawężamy przedział do [x

L

,b].

a → x

L

b → b
x

L

→

x

R

L

R

x

b

x

b

k

−

−

=

k

a

b

x

b

x

b

b

a

b

x

x

b

a

x

x

b

x

b

k

L

L

L

L

L

L

R

1

1

1

1

)

(

+

−

=

−

−

+

−

=

−

−

−

−

=

−

−

=

−

−

=

618

.

0

2

1

5

0

1

1

1

2

=

−

=

=

−

+

+

−

=

k

k

k

k

k

Strategię obliczania minimum funkcji można zapisać:
Jeśli:

Jeśli

to STOP, w przeciwnym wypadku powtórz

punkt 2.

Funkcja wystarczająco gładka:
•w pobliżu minimum funkcja
kwadratowa jest dobrym
przybliżeniem
•parabola dopasowana do dowolnych

Metoda interpolacji parabolicznej

( )

c

bx

Ax

x

p

+

−

=

2

2

1

( )

A

b

x

b

Ax

dx

x

dp

=

⇒

−

=

=

*

0

•parabola dopasowana do dowolnych
trzech punktów powinna wskazać
w jednym kroku minimum albo
przynajmniej w jego bliskie otoczenie.

( )

*

*

p

x

p

=

Jeśli

to

( )

(

)

2

*

*

2

1

x

x

A

p

x

p

−

=

−

Rozwijając dowolną funkcję f(x) w szereg Taylora otrzymujemy

( )

( )

( )(

)

( )(

)

K

+

−

′′

+

−

′

+

=

2

0

0

0

0

0

2

1

x

x

x

p

x

x

x

p

x

p

x

p

widać, że dla x

0

=x*

mamy p’(x

0

)=0 i parabola lokalnie przybliża f(x)

( )

0

1

2

2

a

x

a

x

a

y

x

p

+

+

=

=

Dla trzech punktów (x

a

,y

a

), (x

b

,y

b

) i (x

c

,y

c

) parabola

Przechodząca przez te punkty będzie miała postać:

(

)

(

)

0

1

2

2

c

x

x

c

x

x

c

y

b

b

+

−

+

−

=

gdzie

b

y

c =

0

Ponieważ dla pozostałych dwóch punktów mamy:

(

)

(

)

b

b

a

b

a

a

y

x

x

c

x

x

c

y

+

−

+

−

=

1

2

2

(

)

(

)

b

b

c

b

c

c

y

x

x

c

x

x

c

y

+

−

+

−

=

1

2

2

możemy wyznaczyć wartości parametrów c

1

i c

2

:

(

) (

) (

) (

)

[

]

b

c

b

a

b

a

b

c

y

y

x

x

y

y

x

x

C

c

−

−

−

−

−

=

2

2

1

(

)(

) (

)(

)

[

]

b

c

b

a

b

a

b

c

y

y

x

x

y

y

x

x

C

c

−

−

+

−

−

−

=

2

(

)(

)

(

)(

)

2

2

1

b

a

b

c

b

c

b

a

x

x

x

x

x

x

x

x

C

−

−

−

−

−

=

gdzie

2

1

*

2c

c

x

p

b

−

=

oraz wartość paraboli w maksimum

Metoda Brandta (wykorzystująca metodę złotego podziału i interpolacji
parabolicznej

1. Wyznaczamy przedział [x

a

,x

b

].

2. Wyznaczamy metodą złotego podziału punkt x

i

leżący w jego

wnętrzu będący pierwszym przybliżeniem minimum

3. Ponownie stosujemy „złoty podział” by znaleźć x

i+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ń x

k-1

to w

kolejnym k-tym kroku przeprowadza się minimalizację wzdłuż prostej
wyznaczonej przez punkt x

k-1

i wektor kierunku

d, tj. znajdujemy taką

optymalna wartość α

k

, że

optymalna wartość α

k

, że

(

)

d

min

:

1

k

k

k

x

f

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ądź 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ń x

0

•

wyznaczenie kolejnego punktu x

k

, stanowiącego przybliżenie minimum x*;

punkt ten wyznaczamy przez poszukiwania wzdłuż kierunku d

k

, 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:

• sprawdzenie warunków zbieżności (kryterium osiągnięcia punktu

k

1

d

k

k

k

x

x

α

+

=

−

• sprawdzenie warunków zbieżności (kryterium osiągnięcia punktu
minimalnego wskaź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óźnić znalezienie minimum wskaźnika jakości albo wręcz zdecydować o
możliwości znalezienia minimum globalnego funkcji.

Minimalizacja wzdłuż kierunków współrzędnych

e

2

Wektorom bazy

e

i

, i=1,N przypisujemy kierunki w

których odbywać się będzie minimalizacja (tak jak
dla przypadku 1 zmiennej).

Algorytm:
1. Z punktu startowego x

0

minimalizujemy

funkcję wzdłuż prostej wyznaczonej przez

e

1

i

wyznaczamy minimum w punkcie x

1

2. Z punktu x

1

minimalizujemy funkcję w kierunku

e

2

i wyznaczamy kolejny punkt x

2

x

0

e

1

x

1

x

2

e

2

i wyznaczamy kolejny punkt x

2

3. Kontynuujemy wzdłuż kolejnych osi i

ostateczne znajdujemy punkt x

N

4. Powracamy do minimalizacji wzdłuż kierunku

e

1

i powtarzamy procedurę kolejny raz

5. Minimalizacja kończy się gdy spełniony jest

warunek:

gdzie ε jest dokładnością reprezentacji
maszynowej liczb użytą w obliczeniach a t
parametrem dobieranym indywidualnie.

(

)

( )

( )

t

x

f

x

f

x

f

n

n

n

+

<

−

−

ε

1

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. x

p

:= x

2. Dla każdego z kierunków k=1, 2, ..., N wybieramy optymalny krok m

k

dokonując minimalizacji jednowymiarowej wzdłuż kierunku e

k

3. x := x + m

1

e

1

+ m

2

e

2

+ ... + m

N

e

N

4. Wyznacz kierunek sprzężony i podstawiamy

x := x + m

N+1

e

N+1

, gdzie m

N+1

jest optymalnym krokiem uzyskanym w

wyniku minimalizacji funkcji g(m

N+1

)=f(x+m

N+1

e

N+1

)

5. Jeżeli (zachodzi warunek stopu) to koniec obliczeń
6. x

p

:= x

p

p

N

x

x

x

x

e

−

−

=

+1

ε

<

−

p

x

x

6. x

p

:= x

7. wyznaczamy numer kierunku k (1≤k≤N), w którym nastąpiło największe

przesunięcie (kierunek dla którego m

k

było największe)

8. Jeżeli

(wyznacznik dla nowej bazy - stopień liniowej

niezależności - jest bezpiecznie duży), to zmień bazę:

e

k

:= e

N+1

i

9. przejdź do pkt. 2

ε

≥

−

p

k

x

x

d

m

p

k

x

x

d

m

d

−

=

: