Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Nieliniowe zadanie optymalizacji bez ograniczeń
– numeryczne 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
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
I. Techniki optymalizacji lokalnej
Ad.I Iteracyjne algorytmy optymalizacji
Algorytmy optymalizacji w kierunku
Algorytmy optymalizacji bez ograniczeń
Algorytmy optymalizacji z ograniczeniami
Algorytmy zbieżne do minimum lokalnego x*, jeżeli taki punkt istnieje.
Algorytm optymalizacji lokalnej - przemierzanie obszaru rozwiązań
dopuszczalnych w poszukiwaniu ekstremum funkcji celu według
iteracyjnego schematu.
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Schemat algorytmu optymalizacji lokalnej bez ograniczeń
(1) Wybierz punkt startowy xo=xk.
(2) Oblicz wartość funkcji f(x
k
) oraz jeżeli jest to wymagane to jej gradient
∇
∇
∇
∇
f(x
k
)
(3) Zbadaj przyjęte kryterium zbieżności.
•Jeśli kryterium jest spełnione to koniec algorytmu – uzyskano
rozwiązanie optymalne x
k
i optymalną wartość funkcji celu f(x
k
)
•Jeżeli nie, to przejdź do (4)
(4) Wyznacz ustalony kierunek poszukiwań :
k
d
(5) Wykonaj minimalizację kierunkową wybraną metodą:
)
,
(
1
k
k
k
d
x
T
x
∈
+
(6) Podstaw
i przejdź do (2)
1
1
+
⇐
⇐
+
k
k
oraz
x
x
k
k
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,
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Iteracja metody poszukiwania minimum w kierunku
Przebieg typowej k-tej iteracji dowolnej metody realizującej
ideę poszukiwania wzdłuż kierunku:
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
α
+
=
+
α
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Zbieżność ciągu punktów
Definicja. Mówimy, że ciąg punktów
jest zbieżny do
punktu x jeżeli ciąg różnic k-tych przybliżeń i punktu
optymalnego (punktu minimum)
zbiega do zera, co w
przestrzeni oznacza, że
{ }
1
=
∞
k
x
k
n
R
0
→
k
h
x
x
h
k
k
−
=
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Kryteria zbieżności:
1. Test teoretyczny
2
1
ˆ
,
ˆ
ε
ε
≤
−
≤
−
x
x
f
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
f
f
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Algorytmy optymalizacji lokalnej
Algorytmy bezgradientowe
Algorytm Hooke’a-Jeeves’a
Algorytm Nelder’-Meade’a
Algorytm Gauss’a-Seidla
Algorytm Powella
Algorytm Zangwilla
Algorytmy gradientowe
Algorytm największego spadku
Zmodyfikowany algorytm Newtona
Algorytm Fletchera-Reeves’a
Algorytm Polaka-Ribiery
Algorytm Fletchera-Powella-Davidona
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Algorytm Gauss’a-Seidela
Istotą metody jest minimalizacja funkcji f(x) wzdłuż kolejnych kierunków
ortogonalnej bazy , która utworzona jest z wersorów układu współrzędnych
kartezjańskich.
Algorytm Gaussa-Seidela polega na cyklicznym stosowaniu odwzorowania T
do kierunków . Wykonanie jednego takiego cyklu nazywa się k-tą iterację.
Odwzorowanie T:
{
}
i
i
k
i
k
i
i
i
k
i
k
i
k
i
i
d
x
x
d
x
f
x
f
x
d
x
T
τ
τ
σ
τ
+
=
+
=
=
+
∈
+
+
1
1
1
),
(
min
(
:
)
,
(
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Algorytm obliczeń – metoda Gauss’a-Seidla
(1) Wybierz punkt startowy x
o
=x
k
. Oblicz wartość
funkcji f(x
k
)
(2) Zbadaj kryterium zbieżności:
Jeśli tak, to koniec, jeśli nie, to przejdź do (3)
6
10
:
.
]
,
0
[
−
=
∈
ε
δ
ε
np
gdzie
n
i
x
x
i
k
i
k
i
,...,
1
,
1
=
∀
≤
−
+
ε
oraz
1
1
ε
≤
−
+
k
k
f
f
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
(3) Wyznacz kierunek poszukiwań : są to kolejne kierunki ortogonalnej bazy
k
k
e
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
+
⇐
⇐
+
Np.
]
0
,...,
0
,
1
[
1
=
e
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Metoda największego 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
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
(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 :
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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:
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
(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
τ
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
(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
−
=
⋅
⋅
−
+
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
(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
=
τ
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
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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 uzyskano rozwiązanie optymalne x
k
=[0,0] i f(
x
k
)=0.
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
M
Funkcja celu f(x)
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
M
x
4
x
0
x
1
x
2
x
3
x
^
x
5
Kolejne iteracje metody największego spadku NS
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Algorytmy optymalizacji z ograniczeniami
Przykłady transformacji zmiennych dla
typowych ograniczeń:
1.
2.
3.
0
≥
i
x
( )
i
i
i
i
i
i
u
x
u
x
u
x
=
=
=
exp
2
1
0
≤
≤
i
x
W celu uwzględnienia ograniczeń można postąpić w poniższy sposób:
• dokonać transformacji zmiennych decyzyjnych
• dokonać transformacji funkcji celu wprowadzając funkcje kary.
)
exp(
)
exp(
)
exp(
sin
2
i
i
i
i
i
i
u
u
u
x
u
x
−
+
=
=
i
i
i
b
x
a
≤
≤
(
)
)
(
sin
2
i
i
i
i
i
u
a
b
a
x
−
+
=
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Algorytmy optymalizacji z ograniczeniami cd.
)
)
(
(
)
)
(
(
)
(
)
,
,
(
1
i
i
i
i
m
i
i
x
g
H
x
g
x
f
x
P
θ
θ
ϕ
σ
θ
σ
+
+
+
=
∑
=
]
,...,
,
[
,
0
2
1
m
i
σ
σ
σ
σ
σ
=
>
]
,...,
,
[
,
0
2
1
m
i
θ
θ
θ
θ
θ
=
>
Transformacja funkcji kryterialnej:
Funkcja kary charakteryzuje się tym, że w zbiorze rozwiązań dopuszczalnych
X przyjmuje wartość równą zeru lub bliską zeru, a poza tym obszarem
przyjmuje bardzo duże wartości.
Gdzie: jest wektorem współczynników kary
jest wektorem przesunięć kary
φ( ) funkcja kary
)
)
(
(
lub
)
)
(
(
.
:
)
)
(
(
1
2
i
i
i
i
i
i
x
g
x
g
np
x
g
θ
θ
θ
ϕ
+
−
+
+
−
Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Algorytmy optymalizacji z ograniczeniami cd.
Funkcja H ma poniższą własność:
≤
+
>
+
=
+
0
)
(
0
0
)
(
1
)
)
(
(
i
i
i
i
i
i
x
g
dla
x
g
dla
x
g
H
θ
θ
θ
1.
Metody zewnętrznej funkcji kary (metoda Couranta, metoda
Schmita i Foxa)
2.
Metody wewnętrznej funkcji kary (metoda Rosenbrocka,
metoda Carolla)
3.
Metody przesuwanej funkcji kary (metoda Powella).
Wyszukiwarka
Podobne podstrony:
2w timo 2011
więcej podobnych podstron