1
9.05.2013
Szczecin
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
Z OGRANICZENIAMI
1
9.05.2013
Szczecin
Metody optymalizacji
Ekstremum funkcji wielu zmiennych
Z OGRANICZENIAMI
2
9.05.2013
Szczecin
Metody optymalizacji
Metody poszukiwania ekstremum funkcji
wielu zmiennych z ograniczeniami
metody graficzne
metoda systematycznego przeszukiwania,
metody losowe,
metoda mnożników Lagrange'a,
warunki Kuhna-Tuckera,
metoda funkcji kary,
Ekstremum funkcji wielu zmiennych z ograniczeniami
3
9.05.2013
Szczecin
Metody optymalizacji
Metoda mnożników Lagrange'a
Znaleźć min f(x)
x=[ x
1,
x
2,
... , x
n
]
T
Przy ograniczeniach
h
k
(
x)=g
k
k =1,2 ,... , m
m<n
λ=[λ
1,
λ
2,
... , λ
m
]
Wprowadzamy wektor
L( x , λ)= f (x)+
∑
k=1
m
λ
k
h
k
(
x)
Budujemy funkcję Lagrange'a
Nieokreślone
mnożniki Lagrange'a
Punkty stacjonarne funkcji Lagrange'a
znajdziemy rozwiązując układ równań:
∂
L( x , λ)
∂
x
j
=
0 j=1,2 ,... , n
∂
L( x , λ)
∂ λ
k
=
h
k
(
x)=0 k=1,2 ,... , m
4
9.05.2013
Szczecin
Metody optymalizacji
Metoda mnożników Lagrange'a – ograniczenia równościowe
Znaleźć
Przy ograniczeniu
min f ( x)=x
1
2
+
x
2
2
h( x)=x
1
+
x
2
=
1
1−x
1
−
x
2
=
0
L( x
1,
x
2,
λ)=
x
1
2
+
x
2
2
+λ (
1− x
1
−
x
2
)
Budujemy funkcję Lagrange'a
∂
L
∂
x
1
=
2x
1
−λ=
0
∂
L
∂
x
2
=
2x
2
−λ=
0
∂
L
∂ λ
=
1−x
1
−
x
2
=
0
Rozwiązanie:
x
1
=
1
2
x
2
=
1
2
λ=
1
5
9.05.2013
Szczecin
Metody optymalizacji
Metoda mnożników Lagrange'a – ograniczenia równościowe
Znaleźć
Przy ograniczeniu
min f ( x)=x
1
2
+
x
2
2
h( x)=x
1
+
x
2
=
1
1−x
1
−
x
2
=
0
x
1
x
2
1
1
2
2
6
9.05.2013
Szczecin
Metody optymalizacji
Metoda mnożników Lagrange'a – ograniczenia równościowe
Znaleźć
Przy ograniczeniach:
min f ( x)=x
1
2
+
x
2
2
+
x
3
2
h
1
(
x)=x
1
+
x
2
=
1
h
2
(
x)=x
2
+
x
3
=
1
Rozwiązanie:
x
1
=
1
3
x
2
=
2
3
x
3
=
1
3
λ
1
=
2
3
λ
2
=
2
3
7
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – ograniczenia nierównościowe
Znaleźć max f(x)
x=[ x
1,
x
2,
... , x
n
]
T
Przy ograniczeniach:
b
i
−
g
i
(
x)⩾0 i=1,... , u
b
i
−
g
i
(
x)⩽0 i=u+1,... , v
b
i
−
g
i
(
x)=0 i=v+1,... , m
oraz:
x
j
⩾
0
j=1,... , s
x
j
⩽
0
j=s+1,... t
x
j
nieograniczonego znaku
j=t+1, ... , n
L( x , λ)= f ( x)+
∑
i=1
m
λ
i
[
b
i
−
g
i
(
x)]
Budujemy funkcję Lagrange'a
8
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – ograniczenia nierównościowe
Funkcja ma punkt siodłowy jeśli istnieje takie otoczenie
że dla wszystkich ,
oraz dla wszystkich obowiązuje:
Punkt siodłowy
L(x ,λ)
[
x
✷
, λ
✷
]
ε>
0
x
∣
x− x
✷
∣<ε
λ
∣λ−λ
✷
∣<ε
L( x , λ
✷
)⩽
L( x
✷
, λ
✷
)⩽
L( x
✷
, λ)
Poszukiwanie punktu siodłowego można uważać za poszukiwanie:
min
λ
max
x
L(x , λ)
9
9.05.2013
Szczecin
Metody optymalizacji
Funkcja siodłowa
Warunki Kuhna – Tuckera – ograniczenia nierównościowe
10
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – ograniczenia nierównościowe
Warunki konieczne istnienia punktu siodłowego dla funkcji L(x,
λ
):
x
j
⩾
0
x
j
⩽
0
x
j
nieograniczonego znaku
∂
L
∂
x
j
⩽
0,
j=1,... , s
∂
L
∂
x
j
⩾
0,
j=s+1,... t
∂
L
∂
x
j
=
0,
j=t+1,... , n
x
j
∂
L
∂
x
j
=
0
j=1,... , n
11
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – ograniczenia nierównościowe
Warunki konieczne istnienia punktu siodłowego dla funkcji L(x,
λ
) c.d.
λ
i
∂
L
∂ λ
i
=
0
i=1,... , m
∂
L
∂ λ
i
⩾
0 i=1,... , u
∂
L
∂ λ
i
⩽
0 i=u+1,... , v
∂
L
∂ λ
i
=
0 i=v+1,... , m
λ
i
⩾
0
λ
i
⩽
0
λ
i
nieograniczonego znaku
12
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – zadanie 1
Znaleźć
Przy ograniczeniach
max f ( x)=−( x
1
−
2)
2
−(
x
2
−
4)
2
x
1
+
x
2
⩽
4
Bez ograniczenia znaku
x
1,
x
2
L( x , λ)=−( x
1
−
2)
2
−(
x
2
−
4)
2
+λ (
4−x
1
−
x
2
)
4−x
1
−
x
2
⩾
0
13
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – zadanie 1
Warunki konieczne istnienia punktu siodłowego dla funkcji L(x,
λ
):
L( x , λ)=−( x
1
−
2)
2
−(
x
2
−
4)
2
+λ (
4−x
1
−
x
2
)
∂
L
∂
x
1
=
0
∂
L
∂
x
2
=
0
x
1
∂
L
∂
x
1
=
0
x
2
∂
L
∂
x
2
=
0
∂
L
∂ λ
⩾
0
λ⩾
0
λ
∂
L
∂ λ
=
0
Ostatecznie otrzymamy:
∂
L
∂
x
1
=
0
∂
L
∂
x
2
=
0
λ
∂
L
∂ λ
=
0
∂
L
∂ λ
⩾
0
λ⩾
0
14
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – zadanie 1
L( x , λ)=−( x
1
−
2)
2
−(
x
2
−
4)
2
+λ (
4−x
1
−
x
2
)
∂
L
∂
x
1
=−
2( x
1
−
2)−λ=0
∂
L
∂
x
2
=−
2( x
2
−
4)−λ=0
λ
∂
L
∂ λ
=λ (
4−x
1
−
x
2
)=
0
∂
L
∂ λ
=
4−x
1
−
x
2
⩾
0
λ⩾
0
15
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – zadanie 1
−
2 x
1
+
4−λ=0
λ (
4−x
1
−
x
2
)=
0
4−x
1
−
x
2
⩾
0
wyznaczamy
λ
z I równania i wstawiamy do pozostałych:
−
2 x
2
+
8−λ=0
−
2 x
2
+
8+2 x
1
−
4=0
λ=−
2 x
1
+
4
2 x
2
=
2 x
1
+
4/: 2
x
2
=
x
1
+
2
(−
2 x
1
+
4)⋅(4−x
1
−
x
2
)=
0
(−
2 x
1
+
4)⋅(4−x
1
−
x
1
−
2)=0
(−
2 x
1
+
4)=0 lub (4−x
1
−
x
1
−
2)=0
x
1
=
2
x
2
=
4
λ=
0
x
1
=
1
x
1
=
3
λ=
2
16
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – zadanie 1
I
II
x
1
2
1
x
2
4
3
λ
0
2
λ⩾
0
TAK TAK
4−x
1
−
x
2
⩾
0 NIE TAK
x
1
=
1
x
1
=
3
λ=
2
Rozwiązaniem jest:
17
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – zadanie 2
Znaleźć
Przy ograniczeniach
max f ( x , y)=( x−3)
2
+(
2 y−2)
2
x+2 y⩾2
Bez ograniczenia znaku
x , y
L( x , y , λ)=( x−3)
2
+(
2 y−2)
2
+λ (
2−x−2 y)
2−x−2 y⩽0
18
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – zadanie 2
Warunki konieczne istnienia punktu siodłowego dla funkcji L(x,
λ
):
∂
L
∂
x
=
0
∂
L
∂
y
=
0
x
∂
L
∂
x
=
0
y
∂
L
∂
y
=
0
∂
L
∂ λ
⩽
0
λ⩽
0
λ
∂
L
∂ λ
=
0
Ostatecznie otrzymamy:
∂
L
∂
x
=
0
∂
L
∂
y
=
0
λ
∂
L
∂ λ
=
0
∂
L
∂ λ
⩽
0
λ⩽
0
L( x , y , λ)=( x−3)
2
+(
2 y−2)
2
+λ (
2−x−2 y)
19
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – zadanie 2
∂
L
∂
x
=
2 x−6−λ=0
∂
L
∂
y
=
8 y−8−2 λ=0
λ
∂
L
∂ λ
=λ (
2−x−2 y)=0
λ⩾
0
L( x , y , λ)=( x−3)
2
+(
2 y−2)
2
+λ (
2−x−2 y)
20
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – zadanie 2
2 x−6−λ=0
λ (
2−x−2 y)=0
2−x−2 y⩽0
na podstawie III równania
8 y−8−2 λ=0
2 x=6/: 2
λ=
0
x=2
y=1
8 y=8/:8
2−x−2 y=0
x=2−2 y
2(2−2 y)−6−λ=0
−
4 y−2−λ=0
λ=−
4 y−2
λ=−
4⋅
1
4
−
2=−3
8 y−8−2(−4 y−2)=0
8 y−8+8 y+4=0
y=
1
4
x=2−2⋅
1
4
=
3
2
16 y−4=0
21
9.05.2013
Szczecin
Metody optymalizacji
Warunki Kuhna – Tuckera – zadanie 2
I
II
x
3
3
2
y
1
1
4
λ
0
−
3
λ⩽
0
TAK TAK
2−x−2 y⩽0 TAK TAK
f (3,1)=0
Aby znaleźć rozwiązanie, trzeba obliczyć f(x,y)
f
(
3
2
,
1
4
)
=
4.5
22
9.05.2013
Szczecin
Metody optymalizacji
Metoda funkcji kary
minimalizujemy f(x) przy ograniczeniach
g
i
(
x)⩾0, i=1,… , I
h
k
(
x)=0, k=1,… , K
przekształcamy to zadanie do postaci zadania optymalizacji bezwarunkowej
albo do sekwencji takich zadań równoważnych. W tym celu wprowadza się
funkcję kary:
P(x , R)= f (x)+Ω( R , g (x) , h( x))
Ω−
kara
Kara może mieć różną postać. Najczęściej – kara kwadratowa:
Ω=
R(h( x))
2
23
9.05.2013
Szczecin
Metody optymalizacji
Metoda funkcji kary – zadanie 1
Znaleźć
Przy ograniczeniu
min f ( x)=( x
1
−
4)
2
+(
x
2
−
4)
2
h( x)=x
1
+
x
2
−
5=0
Wprowadzamy funkcję kary
P( x , R)=( x
1
−
4)
2
+(
x
2
−
4)
2
+
R( x
1
+
x
2
−
5)
2
dalej rozwiązujemy jak zadanie bezwarunkowej minimalizacji dla funkcji P(x,R)
24
9.05.2013
Szczecin
Metody optymalizacji
Metoda funkcji kary – zadanie 1
P( x , R)=( x
1
−
4)
2
+(
x
2
−
4)
2
+
R( x
1
+
x
2
−
5)
2
dalej rozwiązujemy jak zadanie bezwarunkowej minimalizacji dla funkcji P(x,R)
∂
P( x , R)
∂
x
j
=
0
(
x
1
−
4)+R( x
1
+
x
2
−
5)=0
(
x
2
−
4)+R( x
1
+
x
2
−
5)=0
x
1
=
x
2
x
j
=
4+5 R
1+2 R
,
j=1,2
25
9.05.2013
Szczecin
Metody optymalizacji
Metoda funkcji kary – zadanie 1
po przejściu do granicy przy
x
j
=
4+5 R
1+2 R
,
j=1,2
R →∞
lim
R →∞
x
j
=
2.5 ,
j=1,2
Rozwiązanie zbiega się do punktu (2.5, 2.5), f(2.5,2.5)=4.5
26
9.05.2013
Szczecin
Metody optymalizacji
Metoda funkcji kary
Przy rozwiązywaniu zadań z ograniczeniami w postaci nierówności należy
przekształcić je do postaci równości. Zadanie ma postać:
min f ( x),
x=[ x
1,
x
2,
…
, x
n
]
T
przy ograniczeniach
g
i
(
x)−u
i
2
=
0, i=1,…, I
h
k
(
x)=0, k=1,…, K
funkcja Lagrange'a
L( x ,φ ,ψ ,u)= f ( x)+∑
i=1
I
φ[
g
i
(
x)−u
i
2
]+∑
k=1
K
ψ
k
h
k
(
x)
27
9.05.2013
Szczecin
Metody optymalizacji
Metoda funkcji kary
nieujemne i niezależne od x współczynniki, określa się je z warunków:
φ
i
, ψ
k
∂
L( x ,φ , ψ,u)
∂
x
j
=
0, ∀ j(1,n)
L( x ,φ ,ψ ,u)= f ( x)+∑
i=1
I
φ[
g
i
(
x)−u
i
2
]+∑
k=1
K
ψ
k
h
k
(
x)
∂
L( x ,φ , ψ,u)
∂ φ
i
=
0, ∀i(1, I )
∂
L( x ,φ , ψ,u)
∂ ψ
=
0, ∀k (1, K )
∂
L( x ,φ , ψ,u)
∂
u
i
=
0, ∀i(1, I )