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