Technika optymalizacji
1
Nieliniowe zadanie optymalizacji
statycznej bez ograniczeń -
nieliniowe algorytmy optymalizacji
lokalnej
Wykład 9
dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek: Elektronika i Telekomunikacja III r.
Potok: Elektronika
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Nieliniowe zadanie optymalizacji bez ograniczeń
– metody iteracyjne optymalizacji
Algorytmy poszukiwania minimum lokalnego zadania programowania
nieliniowego:
•
Bez ograniczeń
•
Z ograniczeniami
Algorytmy zbieżne do minimum lokalnego x*, jeżeli taki punkt istnieje.
( )
=
∧
∈
x
x
x
f
f
n
R
min
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Warunek stacjonarności:
poprawić gradient i hesjan A
TWIERDZENIE. Jeśli funkcja f(x) jest dwukrotnie różniczkowalna, to w
każdym jej minimum lokalnym bez ograniczeń spełnione są
następujące warunki konieczne optymalności zadania ZPN bez
ograniczeń.
n
T
R
d
Ad
d
x
f
∈
∀
≥
=
∇
∧
,
0
0
warunek I rzędu
warunek II rzędu
•Warunek I rzędu jest często nazywamy warunkiem stacjonarności,
ponieważ oznacza zerowanie się pierwszej pochodnej.
•Warunek II rzędu dla funkcji dwukrotnie różniczkowalnych
implikuje lokalną wypukłość minimalizowanej funkcji celu.
)
(x
f
∇
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
I. Techniki optymalizacji lokalnej
Ad.I Iteracyjne algorytmy optymalizacji
Algorytmy optymalizacji w kierunku
Algorytmy optymalizacji bez ograniczeń
Algorytmy optymalizacji z ograniczeniami
Algorytmy poszukiwania minimum lokalnego zadania programowania
nieliniowego:
•
Bez ograniczeń
•
Z ograniczeniami
Algorytmy zbieżne do minimum lokalnego x*, jeżeli taki punkt istnieje.
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
II. Techniki optymalizacji globalnej
Ad.II Algorytmy optymalizacji globalnej
Algorytmy optymalizacji ewolucyjne
Algorytmy optymalizacji genetyczne
Algorytmy optymalizacji – symulowanego wyżarzania
Algorytmy optymalizacji TABU Search
Algorytmy optymalizacji- Harmony Search
Algorytmy optymalizacji rojem cząstek
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Kryteria zbieżności:
1. Test teoretyczny
2
1
ˆ
,
)
(
ˆ
)
(
ε
ε
≤
−
≤
−
∧
x
x
x
f
x
f
k
k
2. Przybliżona stacjonarność rozwiązania
ε
≤
⇒
=
∇
k
k
k
g
g
x
f
)
(
3. Testy praktyczne:
lub
n
i
x
x
i
k
i
k
i
,...,
1
,
1
=
∀
≤
−
+
ε
1
1
)
(
)
(
ε
≤
−
+
k
k
x
f
x
f
Technika optymalizacji
2
Do minimalizacji w kierunku można użyć kilku algorytmów takich
jak np.:
Algorytmy bez-gradientowe:
złotego podziału,
aproksymacji kwadratowej,
Algorytmy gradientowe:
ekspansji i kontrakcji geometrycznej z testem
jednoskośnym,
logarytmiczny złoty podział odcinka ze wstępną ekspansją
i kontrakcją geometryczną,
aproksymacji parabolicznej z testem jednoskośnym,
bisekcji z testem dwuskośnym Goldstein’a,
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Iteracja metody poszukiwania minimum w kierunku
Przebieg typowej k-tej iteracji dowolnej metody realizującej
ideę poszukiwania wzdłuż kierunku jest następujący:
1. Określ kierunek poszukiwań
2. Znajdź
minimalizujące
ze względu na
3. Podstaw
.
k
d
)
(
)
(
~
k
k
d
x
f
f
α
α
+
=
.
α
.
1
k
k
k
d
x
x
α
+
=
+
α
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Metoda najszybszego spadku NS
jest to metoda gradientowa, która pozwala szukać minimum różniczkowalnej funkcji
nieliniowej f(x).
Koncepcja metody wynika z lematu, w którym wykazano, że jeśli istnieje kierunek d w
przestrzeni taki, że
0
),
(
<
∇
d
x
f
to
)
(
)
(
x
f
d
x
f
<
+
τ
n
R
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Algorytm obliczeń – metoda NS
(1) Wybierz punkt startowy x
o
=x
k
. Oblicz wartość
funkcji f(x
k
) oraz jej gradient
∇
∇
∇
∇ f(x
k
)
(2) Zbadaj kryterium zbieżności:
ε
≤
∇
∇
=
∇
∇
)
(
),
(
0
)
(
),
(
k
k
k
k
x
f
x
f
czyli
x
f
x
f
Jeśli tak, to koniec, jeśli nie, to przejdź do (3)
6
10
:
.
]
,
0
[
−
=
∈
ε
δ
ε
np
gdzie
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
(3) Wyznacz kierunek poszukiwań :
)
(
k
k
x
f
d
−∇
=
(4) Wykonaj minimalizację kierunkową
wybraną metodą:
)
,
(
1
k
k
k
d
x
T
x
∈
+
(5) Podstaw
)
1
(
1
1
powtórz
i
k
k
oraz
x
x
k
k
+
⇐
⇐
+
Do minimalizacji w kierunku zastosowano
gradientowy algorytm bisekcji z testem dwuskośnym
Goldstein’a :
Iteracyjny algorytm gradientowy
Technika optymalizacji
3
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Algorytm bisekcji z testem dwuskośnym Golstein’a – algorytm
gradientowy
Praktycznie do wyszukania punktów spełniających test dwuskośny
Goldsteina stosuje się następujący algorytm bisekcji:
(1) Oblicz pochodną w kierunku oraz współczynnik
kroku
d
x
f
p
T
o
)
(
∇
=
)
(
)
(
,
0
0
0
x
f
d
x
f
że
taki
R
R
<
+
>
τ
τ
(2) Wyznacz
).
(
).
(
2
1
0
d
x
f
Oblicz
R
L
τ
τ
τ
τ
+
+
=
(3) Jeśli to podstaw
i przejdź do kroku (2), w przeciwnym razie przejdź do kroku (4)
τ
β
τ
p
x
f
d
x
f
)
1
(
)
(
)
(
0
0
−
+
<
+
τ
τ
⇒
L
(4) Jeśli to podstaw
i przejdź do kroku (2), w przeciwnym przypadku koniec.
τ
β
τ
p
x
f
d
x
f
+
>
+
)
(
)
(
0
0
τ
τ
⇒
R
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
f(x
1
, x
2
) = (x
1
)
2
+ 2(x
2
)
2
– 6x
1
+ x
1
x
2
punkt początkowy x
0
= [0, 0]
T
kierunek d = [1, 0]
T
współczynnik testu β =
początkowa wartość współczynnika kroku τ
R
= 9
dokładność dla testu
5
2
5
10−
=
′
ε
Działanie algorytmu bisekcji z testem dwuskośnym Goldstein'a
dla funkcji:
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Pochodna w kierunku
zatem mamy:
dla x = x
0
= [0, 0]
T
Otrzymujemy wartość pochodnej p:
d
x
f
p
T
o
)
(
∇
=
+
+
−
=
∂
∂
∂
∂
=
∇
1
2
4
,
2
6
1
2
2
)
(
,
1
)
(
)
(
x
x
x
x
x
x
f
x
x
f
x
f
[
]
0
,
6
)
(
0
−
=
∇ x
f
6
0
1
]
0
6
[
)
(
−
=
⋅
−
=
∇
=
d
x
f
p
T
o
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
(2) Obliczamy
Przechodzimy do kroku (3)
).
(
oraz
)
(
2
1
0
d
x
f
R
L
τ
τ
τ
τ
+
+
=
5
,
4
)
9
(
2
1
)
(
2
1
=
=
=
R
τ
τ
6,75
-
27
-
20,25
)
0
,
5
,
4
(
)
0
,
0
(
)
(
0
=
=
+
=
+
f
d
x
f
τ
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
(3) Jeżeli
to podstaw
i przejdź do kroku (2). W przeciwnym wypadku przejdź do
kroku (4)
sprawdzamy: -6,75 <
?
NIE
Przechodzimy do kroku (4)
τ
β
τ
p
x
f
d
x
f
)
1
(
)
0
(
)
0
(
−
+
<
+
τ
τ
⇒
L
( )
2
,
16
)
5
,
4
(
6
,
0
)
6
(
0
−
=
⋅
⋅
−
+
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
(4) Jeżeli
to podstaw
i przejdź do kroku (2). W przeciwnym wypadku KONIEC
sprawdzamy: -6,75 >
?
TAK
i przechodzimy do kroku (2)
DRUGA ITERACJA
(...)
Po trzeciej iteracji otrzymujemy wynik
τ
β
τ
p
x
f
d
x
f
+
>
+
)
(
)
(
0
0
τ
τ
⇒
R
( )
8
,
10
)
5
,
4
(
4
,
0
)
6
(
0
−
=
⋅
⋅
−
+
375
,
3
=
τ
Technika optymalizacji
4
Działanie algorytmu najszybszego spadku dla funkcji:
f(x
1
, x
2
) = 2(x
1
)
2
+ (x
2
)
2
– 2 x
1
x
2
punkt początkowy x
0
= [2, 3]
T
współczynnik testu β =
początkowa wartość współczynnika kroku τ
R
= 1
4
1
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Obliczamy
Ponieważ pierwsza stosowana wartość współczynnika kroku
τ
R
= 1 spełnia test dwuskośny Goldsteina, więc:
x
1
= x
0
+
τ
0
d
0
= [0 1]
T
W drugiej iteracji mamy:
Otrzymujemy:
T
x
f
d
]
2
,
2
[
)
0
(
0
−
−
=
−∇
=
T
x
f
d
]
2
2
[
)
1
(
1
−
=
−∇
=
1
8
2
20
)
1
1
(
+
−
=
+
τ
τ
τ
d
x
f
8
]
2
2
[
2
2
)
(
1
1
−
=
−
⋅
−
=
∇
=
d
x
f
p
T
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Zatem test dwuskośny ma postać
-6
≤ 20τ
2
- 8
τ ≤ -2
Za pomocą algorytmu bisekcji (test dwuskośny Goldsteina) w
trzeciej próbie znajdujemy wartość współczynnika
τ
1
= 0,25
Stąd
x
2
= x
1
+
τ
1
d
1
= [
]
T
Postępując zgodnie z algorytmem otrzymujemy kolejne
wartości punktów optymalizowanej funkcji.
2
1
2
1
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
Kolejno podane są punkty wyznaczone za pomocą
algorytmu najszybszego spadku dla funkcji:
f(x
1
, x
2
) = 2(x
1
)
2
+ (x
2
)
2
– 2 x
1
x
2
x
0
= [2 3]
x
1
= [0 1]
x
2
= [
]
x
3
= [
]
x
4
= [
] itd....
I tak kolejno, aż do momentu gdy zostanie spełniony
warunek
2
1
2
1
2
1
4
1
4
1
4
1
3
^
^
10
)
(
),
(
−
=
≤
∇
∇
ε
x
f
x
f
TAK OTRZYMUJEMY PUNKT MIN (0,0)
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
M
Funkcja celu f(x)
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kierunek EiT III r Potok: Elektronika.
M
x
4
x
0
x
1
x
2
x
3
x
^
x
5
Kolejne iteracje metody najszybszego spadku NS
Wyszukiwarka
Podobne podstrony:
9w to optym lokalna bez ogran 2011
9w to optym lokalna bez ogran
10w to optym globalna bez ogran 2011
10w to optym globalna bez ogran 2011
10w to optym globalna bez ogran
8w to pn bez ogran 2011
8w to pn bez ogran
11w pn z ogran 2011
002 To nie bajka piosenka13 04 2011
Nie wyszły naciski, to może faktury Nasz Dziennik, 2011 03 09
Kosaczow Smoleńsk to temat drażliwy Nasz Dziennik, 2011 02 22
Do 100 metrów, ale to nie koniec Nasz Dziennik, 2011 03 02
więcej podobnych podstron