PROGRAMOWANIE WYPUKŁE I KWADRATOWE Tadeusz Trzaskalik Wprowadzenie do badań operacyjnych z komputerem 6.Programowaniewypukłeikwadratowe T.Trzaskalik: ...
10 downloads
35 Views
526KB Size
PROGRAMOWANIE WYPUKŁE I KWADRATOWE
Tadeusz Trzaskalik Wprowadzenie do badań operacyjnych z komputerem
6.1. Wprowadzenie
6. Programowanie wypukłe i kwadratowe
Słowa kluczowe
• Zadanie programowania nieliniowego • Ekstrema globalne i lokalne • Zbiory wypukłe • Funkcje wklęsłe i wypukłe • Zadanie programowania wypukłego • Funkcja Lagrange’a • Warunki Kuhna - Tuckera • Zadanie programowania kwadratowego • Zadanie zastępcze • Zmienne sztuczne typu w i u • Algorytm Wolfe’a • Optymalny portfel akcji • Zadanie Markowitza T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
2
6.2. Zadanie programowania wypukłego 6.2.1. Zbiory wypukłe i funkcje wypukle (1/5)
6. Programowanie wypukłe i kwadratowe
Ekstrema globalne i lokalne
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
3
6.2. Zadanie programowania wypukłego 6.2.1. Zbiory wypukłe i funkcje wypukle (2/5)
6. Programowanie wypukłe i kwadratowe
Przykłady zbiorów wypukłych i niewypukłych
"x , y Î C
"l Î [0,1]
Zbiory wypukłe
lx + (1 - l ) y Î C
Zbiór niewypukły
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
4
6.2. Zadanie programowania wypukłego 6.2.1. Zbiory wypukłe i funkcje wypukle (3/5)
6. Programowanie wypukłe i kwadratowe
Funkcje wypukłe a kształty wypukle
funkcja wypukła
kształt wklęsły
funkcja wklęsła
kształt wypukły
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
5
6.2. Zadanie programowania wypukłego 6.2.1. Zbiory wypukłe i funkcje wypukle (4/5)
6. Programowanie wypukłe i kwadratowe
Definicje
Funkcja wypukła:
"x, y Î W, "l Î [0,1] f (lx + (1 - l )y ) £ lf (x) + (1 - l ) f (y ) Funkcja wklęsła: f wklęsła Û –f wypukła Funkcja liniowa:
n
a ( x) = p x + q = å p j x j + q T
j =1
Forma kwadratowa:
n
n
b (x) = x Cx = åå cij xi x j T
Funkcja kwadratowa:
i =1 j =1
H (x) = pT x - xT Cx T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
6
6.2. Zadanie programowania wypukłego 6.2.1. Zbiory wypukłe i funkcje wypukle (5/5)
6. Programowanie wypukłe i kwadratowe
Twierdzenia
Twierdzenie 6.1: Funkcja liniowa jest jednocześnie funkcją wypukłą i wklęsłą. Twierdzenie 6.2: Forma kwadratowa jest funkcja wypukłą (wklęsłą) wtedy i tylko wtedy, gdy macierz formy C jest nieujemnie (niedodatnio) określona.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
7
6.2. Zadanie programowania wypukłego 6.2.2. Sformułowanie zadania programowania wypukłego (1/3)
6. Programowanie wypukłe i kwadratowe
Sformułowanie zadania
f (x) ® max g1 ( x) ³ 0 ............... gm ( x) ³ 0
é g1 ( x) ù ê ú = g ( x) ê..........ú êëgm ( x) úû
f ( x) ® max g ( x) ³ 0 Powyższe zadanie jest zadaniem programowania wypukłego jeżeli f i wszystkie gi są funkcjami wklęsłymi. T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
8
6.2. Zadanie programowania wypukłego 6.2.2. Sformułowanie zadania programowania wypukłego (2/3)
6. Programowanie wypukłe i kwadratowe
Przykład 6.1
x2
f ( x) = x1 + x2 A (0, 2 2 ) P (2, 2)
g1 ( x) = 8 - x - x ³ 0 2 1
2 2
g2 ( x) = x1 ³ 0 g3 ( x) = x2 ³ 0
O
B ( 2 2 , 0)
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
x1
9
6.2. Zadanie programowania wypukłego 6.2.2. Sformułowanie zadania programowania wypukłego (3/3)
6. Programowanie wypukłe i kwadratowe
Zadanie programowania kwadratowego
T p x x Cx ® max Ax £ b x ³0 T
C - macierz nieujemnie określona
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
10
6.2. Zadanie programowania wypukłego 6.2.3. Warunki Kuhna-Tuckera (1/2)
6. Programowanie wypukłe i kwadratowe
Funkcja Lagrange’a
f ( x) ® max g ( x) ³ 0 L ( x , y ) = f ( x) + yg ( x ) y = [ y1 ,..., ym ] L ( x1 ,..., xn , y1 ,..., ym ) = f ( x 1 ,..., xn ) +
m
å y g ( x ,..., x i =1
i
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
i
1
n
)
11
6.2. Zadanie programowania wypukłego 6.2.3. Warunki Kuhna-Tuckera (2/2)
6. Programowanie wypukłe i kwadratowe
Sformułowanie warunków
Warunek 1
Ñ x L ( x, y ) = 0
Warunek 2
yg ( x ) = 0
Warunek 3
g ( x) ³ 0
Warunek 4
y³0
é ¶L( x, y ) ¶L( x, y ) ù ,..., Ñ x L( x, y ) = ê ú x x ¶ ¶ 1 n ë û
Warunek Slatera Twierdzenie 6.3: Problem programowania wypukłego i problem Kuhna-Tuckera opisane warunkami 1 - 4 są sobie równoważne. T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
12
6.2. Zadanie programowania wypukłego 6.2.4. Wykorzystanie warunków K-T do rozwiązywania zadań programowania wypukłego (1/5)
6. Programowanie wypukłe i kwadratowe
Przykład 6.1 (c.d.)
f ( x) = x1 + x2 g1 ( x) = 8 - x12 - x22 ³ 0 g 2 ( x ) = x1 ³ 0 g 3 ( x ) = x2 ³ 0 L( x1 , x2 , y1 , y2 , y3 ) = x1 + x2 + y1 (8 - x12 - x22 ) + y2 x1 + y3 x2
Warunek 1:
Warunek 3:
¶L = 1 - 2 y1 x1 + y 2 = 0 ¶x1
g1 ( x) = 8 - x12 - x22 ³ 0
¶L = 1 - 2 y1 x2 + y3 = 0 ¶x2
g 3 ( x ) = x2 ³ 0
Warunek 2: y1 (8 - x12 - x22 ) + y2 x1 + y3 x2 = 0
g 2 ( x ) = x1 ³ 0
Warunek 4: y1 ³ 0, y2 ³ 0, y3 ³ 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
13
6.2. Zadanie programowania wypukłego 6.2.4. Wykorzystanie warunków K-T do rozwiązywania zadań programowania wypukłego (2/5)
6. Programowanie wypukłe i kwadratowe
Podział zbioru rozwiązań dopuszczalnych na podzbiory
Podzbiór 1
Podzbiór 2 x2
g1 > 0
x2
g1 = 0
A
g2 > 0
g2 > 0
g3 > 0
g3 > 0 B
O
Podzbiór 3 g1 > 0 g2 = 0
x1
A
O
B
x1
B
x1
Podzbiór 4
x2
x2
g1 > 0
A
A
g2 > 0
g3 > 0
g3 = 0 O
B
x1
O
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
14
6.2. Zadanie programowania wypukłego 6.2.4. Wykorzystanie warunków K-T do rozwiązywania zadań programowania wypukłego (3/5)
6. Programowanie wypukłe i kwadratowe
Podział zbioru rozwiązań dopuszczalnych na podzbiory (c.d.)
Podzbiór 5
Podzbiór 6 x2
g1 = 0
x2
g1 = 0
A
g2 = 0
g2 > 0
g3 > 0
g3 = 0 B
O
Podzbiór 7 g1 > 0 g2 = 0
x1
A
B
O
x1
Podzbiór 8
x2
g1 = 0
A
g2 = 0
g3 = 0
Zbiór pusty
g3 = 0 O
B
x1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
15
6.2. Zadanie programowania wypukłego 6.2.4. Wykorzystanie warunków K-T do rozwiązywania zadań programowania wypukłego (4/5)
6. Programowanie wypukłe i kwadratowe
Podzbiór 1
Warunek 1 ¶L = 1 - 2 y1 x1 + y 2 = 0 ¶ x1 ¶L = 1 - 2 y1 x 2 + y 3 = 0 ¶x 2
Warunek 2 y1 (8 - x12 - x 22 ) + y 2 x1 + y 3 x 2 = 0
Warunek 3
Podzbiór 1 g1 > 0, g 2 > 0, g 3 > 0
z warunku 2 wynika, że y1 = 0, y2 = 0, y3 = 0 Wstawiamy te wartości do warunku 1
g 1 ( x ) = 4 - x12 - x 22 ³ 0 g 2 ( x ) = x1 ³ 0 g 3 ( x ) = x2 ³ 0
Warunek 4
1 - 2 × 0 × x1 + 0 = 0 1 - 2 × 0 × x2 + 0 = 0
czyli: 1 = 0 - sprzeczność
y1 ³ 0 , y 2 ³ 0 , y 3 ³ 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
16
6.2. Zadanie programowania wypukłego 6.2.4. Wykorzystanie warunków K-T do rozwiązywania zadań programowania wypukłego (5/5)
6. Programowanie wypukłe i kwadratowe
Podzbiór 2
Podzbiór 2
Warunek 1 ¶L = 1 - 2 y1 x1 + y 2 = 0 ¶ x1 ¶L = 1 - 2 y1 x 2 + y 3 = 0 ¶x 2
g1 = 0, g 2 > 0, g 3 > 0
z warunku 2 wynika, że y2 = 0, y3 = 0 Wstawiamy te wartości do warunku 1
Warunek 2 y1 (8 - x12 - x 22 ) + y 2 x1 + y 3 x 2 = 0
Warunek 3
1 - 2 y 1 x1 + 0 = 0 1 - 2 y1 x2 + 0 = 0
g 1 ( x ) = 4 - x12 - x 22 g 2 ( x ) = x1 ³ 0 g 3 ( x ) = x2 ³ 0
Warunek 4 y1 ³ 0 , y 2 ³ 0 , y 3 ³ 0
1 1 , x2 = 2 y1 2 y1 1 1 8=0 2 2 (2 y1 ) (2 y1 ) x1 =
x1 = 2, x2 = 2, y1 = 0,25, y2 = 0, y3 = 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
17
6.3. Metoda Wolfe’a 6.3.1. Warunki Kuhna-Tuckera dla zadania programowania kwadratowego (1/3)
6. Programowanie wypukłe i kwadratowe
Przykład 6.2
f ( x 1 , x 2 ) = 10 x 1 + 25 x 2 - 10 x12 - x 22 - 4 x 1 x 2 ® max x1 + 2 x 2 £ 10 x1 + x2 £9 x1 , x 2 ³ 0 p T x - x T Cx ® Ax £ b
max
x ³ 0 C
-
é10 ù p = ê ú, ë 25 û
macierz é10 C = ê ë2
nieujemnie 2ù , 1 úû
określona
é10 ù b = ê ú, ë9û
éx ù x = ê 1ú ë x2 û
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
18
6.3. Metoda Wolfe’a 6.3.1. Warunki Kuhna-Tuckera dla zadania programowania kwadratowego (2/3)
6. Programowanie wypukłe i kwadratowe
Przekształcenia warunków ograniczających
f ( x) = 10x1 + 25x2 -10x12 - x22 - 4x1x2 ® max x1 + 2x2 £ 10 ®
g1(x) = 10 – x1 – 2x2 ³ 0
x1 + x2 £ 9 ®
g2(x) = 9 – x1 – x2 ³ 0
x1
³ 0 ®
g3(x) =
x2 ³ 0 ®
g4(x) =
[
y = y1 , y2 , y1d , y2d
x1
³0 x2 ³ 0
]
L( x1 , x2 , y1, y2 , y1d , y2d ) = 10x1 + 25x2 -10x12 - 4x1 x2 - x22 + + y1 (10 - x1 - 2x2 ) + y2 (9 - x1 - x2 ) + y1d x1 + y2d x2 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
19
6.3. Metoda Wolfe’a 6.3.1. Warunki Kuhna-Tuckera dla zadania programowania kwadratowego (3/3)
6. Programowanie wypukłe i kwadratowe
Sformułowanie warunków K-T
Warunek 1
20 x1 + 4 x2 + y1 + y2 - y1d = 10 4 x1 + 2 x2 + 2 y1 + y2 - y 2d = 25
Warunek 2
y1x1d + y2x2d + y1dx1 + y2dx2 = 0
Warunek 3
x1 + 2x2 + x1d = 10 x1 + x2 + x2d = 9 x1 ³ 0 x2 ³ 0
Warunek 4
y1 ³ 0,
y2 ³ 0,
y1d ³ 0,
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
y2d ³ 0
20
6.3. Metoda Wolfe’a 6.3.2. Sformułowanie zadania zastępczego (1/1)
6. Programowanie wypukłe i kwadratowe
Zadanie zastępcze
w1 + w2 ® min
x1 + 2x2 + x1d = 10 x1 + x2 + x2d = 9 20x1+ 4x2 + y1 + y2 – y1d +w1 = 10 4x1+ 2x2 + 2y1 + y2 – y2d + w2 = 25 x1, x2, x1d, x2d, y1, y2, y1d, y2d, w1, w2 ³ 0 Pominięty warunek: y1x1d + y2x2d + y1dx1 + y2d x2 = 0 Pary zmiennych komplementarnych: y1 i x1d y1d i x1
y2 i x2d y2d i x2
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
21
6.3. Metoda Wolfe’a 6.3.3. Rozwiązanie zadania zastępczego (1/5)
6. Programowanie wypukłe i kwadratowe
Przebieg obliczeń
cx®min
0
0
0
0
0
0
0
0
1
1
b
Baza
cB
x1
x2
x1
x2
y1
y2
y1
y2
w1
w2
x1d
0
1
2
1
0
0
0
0
0
0
0
10
x2d
0
1
1
0
1
0
0
0
0
0
0
9
w1
1
20
4
0
0
1
1
-1
0
1
0
10
w2
1
4
2
0
0
2
1
0
-1
0
1
25
-24
-6
0
0
-3
-2
1
1
0
0
cj -zj
d
d
d
d
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
22
6.3. Metoda Wolfe’a 6.3.3. Rozwiązanie zadania zastępczego (2/5)
6. Programowanie wypukłe i kwadratowe
Przebieg obliczeń (c.d.)
cx®min
0
0
0
0
0
0
0
0
1
1
x2
y1
y2
y1
y2
w1
w2
b
Baza
cB
x1
x2
x1
x1d
0
0
1,8
1
0 -0,05 -0,05 0,05
0 -0,05 0
9,5
x2d
0
0
0,8
0
1 -0,05 -0,05 0,05
0 -0,05 0
8,5
x1
0
1
0,2
0
0
0,05 0,05 -0,05 0
0,05
0
0,5
w2
1
0
1,2
0
0
1,8
0,2
-1
-0,2
1
23
0
-1,2
0
0
-1,8 -0,8 -0,2
1
1,2
0
cj -zj
d
d
0,8
d
d
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
23
6.3. Metoda Wolfe’a 6.3.3. Rozwiązanie zadania zastępczego (3/5)
6. Programowanie wypukłe i kwadratowe
Przebieg obliczeń (c.d.)
cx®min
0
0
0
0
0
0
0
0
1
1
y1
y2
y1
y2
w1
w2
b
Baza
cB
x1
x2
x1
x2
x1d
0
-9
0
1
0
-0,5 -0,5 0,5
0 -0,25 0
5
x2d
0
-4
0
0
1 -0,25 -0,25 0,25
0 -0,25 0
6,5
x2
0
5
1
0
0
0,25 0,25 -0,25 0
0,25
0
2,5
w2
1
-6
0
0
0
1,5
0,5
-1
-0,5
1
20
6
0
0
0
-1,5 -0,5 -0,5
1
1,5
0
cj -zj
d
d
0,5
d
d
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
24
6.3. Metoda Wolfe’a 6.3.3. Rozwiązanie zadania zastępczego (4/5)
6. Programowanie wypukłe i kwadratowe
Przebieg obliczeń (c.d.)
cx®min
0
0
0
0
0
0
0
0
1
1
b
Baza
cB
x1
x2
x1
x2
y1
y2
y1
y2
w1
w2
y1d
0
-18
0
2
0
-1
-1
1
0
-1
0
10
x2d
0
0,5
0
-0,5
1
0
0
0
0
0
0
4
x2
0
0,5
1
0
0
0
0
0
0
0
0
5
w2
1
3
0
-1
0
2
1
0
-1
0
1
15
-3
0
1
0
-2
-1
0
1
1
0
cj -zj
d
d
d
d
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
25
6.3. Metoda Wolfe’a 6.3.3. Rozwiązanie zadania zastępczego (5/5)
6. Programowanie wypukłe i kwadratowe
Przebieg obliczeń (c.d.)
cx®min
0
0
0
0
0
0
0
0
1
1
d
b
Baza
cB
x1
x2
x1
x2
y1
y2
y1
y2
w1
w2
y1d
0
-16,5
0
1,5
0
0
-0,5
1
-0,5
-1
0,5 17,5
x2d
0
0,5
0
-0,5
1
0
0
0
0
0
0
4
x2
0
0,5
1
0,5
0
0
0
0
0
0
0
5
y2
1
1,5
0
-0,5
0
1
0,5
0
-0,5
0
0,5
7,5
0
0
0
0
0
0
0
0
1
1
cj -zj
d
d
d
Z twierdzenia Kuhna-Tuckera: x1 = 0, x2 = 5 - rozwiązanie optymalne wyjściowego zadania programowania kwadratowego T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
26
6.3. Metoda Wolfe’a 6.3.4. Przypadek ogólny (1/5)
6. Programowanie wypukłe i kwadratowe
Przykład 6.3
f(x1,x2) = 10x1 + 25x2 – 10x12 – x22 – 4x1x2 ® max x1 + 2x2 £ 10 –x1 – x2 £ –9 x1 ³0 x2 ³ 0 Zadanie zastępcze v1 + w1 + w2 ® min x1 + 2x2 + x1d = 10 x1 + x2 – x2d + v1 = 9 20x1 + 4x2 + y1 - y2 - y1d + w1 = 10 4x1 + 2x2 + 2y1 - y2 - y2d + w2 = 25 x1, x2, x1d, x2d, y1, y2, y1d, y2d, v1, w1, w2 ³0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
27
6.3. Metoda Wolfe’a 6.3.4. Przypadek ogólny (2/5)
6. Programowanie wypukłe i kwadratowe
Iteracja 5
cx®min
0
0
0
0
0
0
0
0
1
1
1
d
b
Baza
cB
x1
x2
x1
x2
y1
y2
y1
y2
v1
w1
w2
x2
0
0,5
1
0,5
0
0
0
0
0
0
0
0
5
y1
0
1,5
0
-0,5
0
1
-0,5
0
-0,5
0
0
0,5
7,5
y1d
0
-16,5
0
1,5
0
0
0,5
1
-0,5
0
-1
0,5 17,5
v1
1
0,5
0
-0,5 -1
0
0
0
0
1
0
0
-0,5
0
0,5
0
0
0
0
0
1
1
cj -zj
d
1
d
d
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
4
28
6.3. Metoda Wolfe’a 6.3.4. Przypadek ogólny (3/5)
6. Programowanie wypukłe i kwadratowe
Iteracja 6
cx®min
0
0
0
0
0
0
0
0
1
1
1
d
b
Baza
cB
x1
x2
x1
x2
y1
y2
y1
y2
v1
w1
w2
x2
0
0,5
1
0,5
0
0
0
0
0
0
0
0
5
y1
0
-15
0
1
0
1
0
1
-1
0
-1
1
25
y2
0
-33
0
3
0
0
1
2
-1
0
-2
1
35
v1
1
0,5
0
-0,5 -1
0
0
0
0
1
0
0
4
-0,5
0
0,5
0
0
0
0
0
1
1
cj -zj
d
1
d
d
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
29
6.3. Metoda Wolfe’a 6.3.4. Przypadek ogólny (4/5)
6. Programowanie wypukłe i kwadratowe
Iteracja 7
cx®min
0
0
0
0
0
0
0
0
1
1
1
b
Baza
cB
x1
x2
x1
x2
y1
y2
y1
y2
v1
w1
w2
x2
0
0
1
1
1
0
0
0
0
-1
0
0
1
y1
0
0
0
-14 -30
1
0
1
-1
30
-1
1
145
y2
0
0
0
-30 -66
0
1
2
-1
66
-2
1
299
x1
0
1
0
-1
-2
0
0
0
0
2
0
0
8
0
0
0
0
0
0
0
0
0
1
1
cj -zj
d
d
d
d
Z twierdzenia Kuhna-Tuckera: x1 = 8, x2 = 1 - rozwiązanie optymalne wyjściowego zadania programowania kwadratowego T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
30
6.3. Metoda Wolfe’a 6.3.4. Przypadek ogólny (5/5)
6. Programowanie wypukłe i kwadratowe
Przykład 6.4
f(x1,x2) = 10x1 – 25x2 – 10x12 – x22 – 4x1x2 ® max x1 + 2x2 £ 10 –x1 – x2 £ –9 x1 ³0 x2 ³ 0 Zadanie zastępcze v1 + w1 ® min x1 + 2x2 + x1d = 10 x1 + x2 – x2d + v1 = 9 20x1 + 4x2 + y1 - y2 - y1d + w1 = 10 -4x1 - 2x2 - 2y1 + y2 + y2d = 25 x1, x2, x1d, x2d, y1, y2, y1d, y2d, v1, w1³0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
31
6.3. Metoda Wolfe’a 6.3.5. Reguły postępowania w metodzie Wolfe’a (1/1)
6. Programowanie wypukłe i kwadratowe
Algorytm
1.
Zapisanie warunków Kuhna-Tuckera
2.
Zapisanie zadania zastępczego: a) zmienne sztuczne typu w, b) zmienne sztuczne typu v,
3.
Rozwiązanie zadania zastępczego: a) wybór zmiennej kandydującej do bazy, b) sprawdzenie, czy wybór zmiennej kandydującej był właściwy, c) wybór zmiennej usuwanej z bazy, d) badanie niesprzeczności zadania.
4.
Odczytanie rozwiązania zadania wyjściowego. T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
32
6.4. Optymalny portfel akcji 6.4.1. Oczekiwana stopa zysku i ryzyko portfela (1/2)
6. Programowanie wypukłe i kwadratowe
Podstawowe pojęcia
Określić taki skład portfela, złożonego z akcji n spółek, by zminimalizować ryzyko portfela, przy założonym z góry poziomie oczekiwanego zysku. Stopa zysku z i-tej akcji w okresie t (t = 1, ..., T) Oczekiwana stopa zysku z i-tej akcji
Pi (t ) - Pi (t -1) Ri (t ) = Pi (t -1) 1 T Ri = å Ri (t ) T t =2 n
Udziały akcji w portfelu
åx i =1
Oczekiwana stopa zysku portfela akcji
i
=1,
xi ³ 0
n
R p = å Ri xi i =1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
33
6.4. Optymalny portfel akcji 6.4.1. Oczekiwana stopa zysku i ryzyko portfela (2/2)
6. Programowanie wypukłe i kwadratowe
Podstawowe pojęcia (c.d.) n
Ryzyko (wariancja) portfela
n
v p = åå xi x j S i S j rij i =1 j =1
Odchylenie standardowe stopy zysku
1 T Si = (Ri (t ) - Ri )2 å T t =1
Współczynnik korelacji
1 T å (Ri (t ) - Ri )(R j (t ) - R j ) cov(Ri , R j ) T t =1 rij = = Si S j Si S j
Zmodyfikowany wzór na wariancję portfela
n
n
v p = åå xi x j cov(Ri , R j ) i =1 j =1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
34
6.4. Optymalny portfel akcji 6.4.2. Optymalizacja portfela akcji jako zadanie programowania kwadratowego (1/7)
6. Programowanie wypukłe i kwadratowe
Sformułowanie zadania n
n
åå x x v i
i =1 j =1 n
j ij
® min
åR x ³R i i
OTx – xTVx ® max Rx ³ RO
0
i =1
1 Tx = 1
n
å x =1 i =1
i
x³ 0
xi ³ 0 dla i = 1, ..., n V – macierz wariancji i kowariancji (V = [cov(Ri, Rj)]), R = [R1 ,..., Rn ],
é x1 ù é0 ù x = êê : úú, O = êê : úú, êë xn úû êë0úû
é1ù 1 = êê : úú êë1úû
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
35
6.4. Optymalny portfel akcji 6.4.2. Optymalizacja portfela akcji jako zadanie programowania kwadratowego (2/7)
6. Programowanie wypukłe i kwadratowe
Przykład 6.4 Notowania Spółka 1 Spółka 2 Spółka 3 Spółka 4 Spółka 5 53.60 15.20 273.00 26.90 67.50 52.00 15.75 283.00 27.20 66.00 51.00 15.50 275.50 27.80 66.50 52.30 15.50 270.00 29.30 65.70 54.60 15.25 274.50 31.40 68.00 58.30 15.20 290.00 29.80 69.00 61.00 15.50 283.50 28.70 70.00 61.90 15.50 281.00 29.00 69.00 61.90 16.00 286.00 28.90 68.30 59.40 16.00 286.00 29.80 68.10 64.20 16.50 285.00 33.00 68.80 66.60 16.90 272.00 32.70 71.50 65.70 17.70 270.50 34.30 75.30 64.30 17.20 265.00 34.50 73.90 64.30 17.30 267.00 34.00 74.00 66.20 17.20 263.50 33.30 72.30 67.60 18.60 265.00 32.90 72.40 67.10 18.50 268.00 32.80 72.20 65.10 17.95 270.00 31.30 71.40 65.00 18.50 269.50 29.10 72.10 64.00 19.15 270.50 31.00 73.50
Oczekiwane stopy zysku z akcji w okresie t w % Spółka 1 Spółka 2 Spółka 3 Spółka 4 Spółka 5 -2.99 -1.92 2.55 4.40 6.78 4.63 1.48 0.00 -4.04 8.08 3.74 -1.35 -2.13 0.00 2.95 2.11 -0.74 -2.98 -0.15 -1.54
3.62 -1.59 0.00 -1.61 -0.33 1.97 0.00 3.23 0.00 3.13 2.42 4.73 -2.82 0.58 -0.58 8.14 -0.54 -2.97 3.06 3.51
3.66 -2.65 -2.00 1.67 5.65 -2.24 -0.88 1.78 0.00 -0.35 -4.56 -0.55 -2.03 0.75 -1.31 0.57 1.13 0.75 -0.19 0.37
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
1.12 2.21 5.40 7.17 -5.10 -3.69 1.05 -0.34 3.11 10.74 -0.91 4.89 0.58 -1.45 -2.06 -1.20 -0.30 -4.57 -7.03 6.53
-2.22 0.76 -1.20 3.50 1.47 1.45 -1.43 -1.01 -0.29 1.03 3.92 5.31 -1.86 0.14 -2.30 0.14 -0.28 -1.11 0.98 1.94 36
6.4. Optymalny portfel akcji 6.4.2. Optymalizacja portfela akcji jako zadanie programowania kwadratowego (3/7)
6. Programowanie wypukłe i kwadratowe
Obliczenia pomocnicze
Oczekiwane stopy zysku z akcji w % Ri
Spółka 1
Spółka 2
Spółka 3
Spółka 4
Spółka 5
0.94
1.20
-0.02
0.81
0.45
Macierz wariancji-kowariancji stóp zysku Spółka 1 Spółka 2 Spółka 3 Spółka 4 Spółka 5 Spółka 1 Spółka 2 Spółka 3 Spółka 4 Spółka 5
11.4312 1.1701 0.1232 1.6619 2.0254
1.1701 7.7723 0.4983 1.1374 1.7056
0.1232 0.4983 5.1598 -1.3094 -0.6307
1.6619 1.1374 -1.3094 20.2858 2.2824
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
2.0254 1.7056 -0.6307 2.2824 4.3189 37
6.4. Optymalny portfel akcji 6.4.2. Optymalizacja portfela akcji jako zadanie programowania kwadratowego (4/7)
6. Programowanie wypukłe i kwadratowe
Model matematyczny
Cel Znalezienie portfela akcji oczekiwanej stopie zwrotu.
minimalizującego
ryzyko
o
zadanej
Zmienne decyzyjne x1 – udział w portfelu akcji spółki 1, x2 – udział w portfelu akcji spółki 2, x3 – udział w portfelu akcji spółki 3, x4 – udział w portfelu akcji spółki 4, x5 – udział w portfelu akcji spółki 5, T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
38
6.4. Optymalny portfel akcji 6.4.2. Optymalizacja portfela akcji jako zadanie programowania kwadratowego (5/7)
6. Programowanie wypukłe i kwadratowe
Model matematyczny (c.d.)
Funkcja celu f(x1, x2, x3, x4, x5) = [x1, x2, x3, x4, x5] × V × [x1, x2, x3, x4, x5]T à min V=
11.4312 1.1701 0.1232 1.6619 2.0254
1.1701 7.7723 0.4983 1.1374 1.7056
0.1232 0.4983 5.1598 -1.3094 -0.6307
1.6619 1.1374 -1.3094 20.2858 2.2824
2.0254 1.7056 -0.6307 2.2824 4.3189
Ograniczenia oczekiwany zysk z portfela ma być większy od 1%, czyli: 0,94x1 + 1,20x2 – 0,02x3 + 0,81x4 + 0,45x5 ³ 1 udziały akcji w portfelu sumują się do jedności: x1 + x2 + x3 + x4 + x5 = 1 warunki nieujemności: x1, x2, x3, x4, x5 ³ 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
39
6.4. Optymalny portfel akcji 6.4.2. Optymalizacja portfela akcji jako zadanie programowania kwadratowego (6/7)
6. Programowanie wypukłe i kwadratowe
Rozwinięta postać zadania
f ( x1 , x2 , x3 , x4 , x5 ) = é 11,4312 ê 1,1701 ê - [ x1 , x2 , x3 , x4 , x5 ] ê 0,1232 ê ê 1,6619 êë 2,0254
1,1701 0,1232 7,7723 0,4983 0,4983 5,1598 1,1374 - 1,3094 1,7056 - 0,6307
1,6619 2,0254ù 1,1374 1,7056úú - 1,3094 - 0,6307ú ú 20,2858 2,2824ú 2,2824 4,3189úû
é x1 ù êx ú ê 2ú ê x3 ú ® max ê ú ê x4 ú êë x5 úû
przy warunkach ograniczających: –0,94x1 – 1,20x2 + 0,02 x3 – 0,81x4 – 0,45x5 £ –1 x1
+ x2
+ x3
+ x4
+ x5 £ 1
–x1
– x2
– x3
– x4
– x5 £ –1
x1, x2, x3, x4, x5 ³ 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
40
6.4. Optymalny portfel akcji 6.4.2. Optymalizacja portfela akcji jako zadanie programowania kwadratowego (7/7)
6. Programowanie wypukłe i kwadratowe
Rozwiązanie i interpretacja
Rozwiązanie optymalne x1 = 0,2468
x2 = 0,5391
x3 = 0,0285
x4 = 0,1060
x5 = 0,0797
Interpretacja rozwiązania Optymalny portfel, dla którego stopa oczekiwanego zysku jest nie mniejsza niż 1% będzie się składał (w ujęciu wartościowym) w 24,68% z akcji spółki 1, w 53,91% z akcji spółki 2, w 2,85% z akcji spółki 3, w 10,6% z akcji spółki 4 i w 7,97% akcji spółki 5. Ryzyko takiego portfela wynosi 2 » 1,41
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
41
6.4. Optymalny portfel akcji 6.4.3. Dwukryterialne zadanie poszukiwania optymalnego portfela akcji (1/5)
6. Programowanie wypukłe i kwadratowe
Przykład 6.4
Cel Szukamy takiego portfela akcji, dla którego ryzyko jest minimalne, a oczekiwany zysk portfela – maksymalny. Zmienne decyzyjne x1 – udział w portfelu akcji spółki 1, x2 – udział w portfelu akcji spółki 2, x3 – udział w portfelu akcji spółki 3, x4 – udział w portfelu akcji spółki 4, x5 – udział w portfelu akcji spółki 5, T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
42
6.4. Optymalny portfel akcji 6.4.3. Dwukryterialne zadanie poszukiwania optymalnego portfela akcji (2/5)
6. Programowanie wypukłe i kwadratowe
Model matematyczny
Funkcje celu Minimalizacja ryzyka portfela é ê ê [ x1 , x2 , x3 , x4 , x5 ] ê ê ê êë
11,4312 1,1701 0,1232 1,6619 2,0254
1,1701 0,1232 7,7723 0,4983 0,4983 5,1598 1,1374 - 1,3094 1,7056 - 0,6307
1,6619 2,0254ù 1,1374 1,7056úú - 1,3094 - 0,6307ú [ x1 , x2 , x3 , x4 , x5 ]T ® min ú 20,2858 2,2824ú 2,2824 4,3189úû
Maksymalizacja oczekiwanej stopy zysku portfela: 0,94x1 + 1,2x2 – 0,02x3 + 0,81x4 + 0,45x5 ® max Ograniczenia x1 + x2 + x3 + x4 + x5 = 1 x1, x2, x3, x4, x5 ³ 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
43
6.4. Optymalny portfel akcji 6.4.3. Dwukryterialne zadanie poszukiwania optymalnego portfela akcji (3/5)
6. Programowanie wypukłe i kwadratowe
Metoda satysfakcjonującego poziomu kryteriów
Funkcja celu 0,1232 1,6619 2,0254ù é11,4312 1,1701 ê 1,1701 7,7723 ú 0 , 4983 1 , 1374 1 , 7056 ê ú [ x1 , x2 , x3 , x4 , x5 ] ê 0,1232 0,4983 5,1598 - 1,3094 - 0,6307ú [ x1 , x2 , x3 , x4 , x5 ]T ® min ê ú 1 , 6619 1 , 1374 1 , 3094 20 , 2858 2 , 2824 ê ú êë 2,0254 1,7056 - 0,6307 2,2824 4,3189úû
Ograniczenia –0,94x1 – 1,20x2 + 0,02x3 – 0,81x4 – 0,45x5 £ –R0 x1 +
x2 +
x3 +
x4 +
x5 £ 1
–x1 –
x2 –
x3 –
x4 –
x5 £ –1
x1, x2, x3, x4, x5 ³ 0 T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
44
6.4. Optymalny portfel akcji 6.4.3. Dwukryterialne zadanie poszukiwania optymalnego portfela akcji (4/5)
6. Programowanie wypukłe i kwadratowe
Wyniki obliczeń
Parametry portfeli wyznaczonych dla założonych wartości R0 Lp P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
R0 1.2 1.15 1.1 1.0 0.9 0.8 0.7 0.6 0.5 0.4
Vp 2.79 2.42 2.20 2.00 1.83 1.67 1.53 1.43 1.36 1.34
x1 0 0.1841 0.2527 0.2468 0.2171 0.1874 0.1577 0.1280 0.0984 0.0687
x2 1 0.8104 0.6594 0.5391 0.4671 0.3951 0.3231 0.2511 0.1791 0.1071
x3 0 0 0 0.0285 0.0897 0.1510 0.2122 0.2734 0.3347 0.3959
x4 0 0.0054 0.0879 0.1060 0.0986 0.0911 0.0837 0.0763 0.0689 0.0615
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
x5 0 0 0 0.0797 0.1275 0.1754 0.2233 0.2711 0.3190 0.3668 45
6.4. Optymalny portfel akcji 6.4.3. Dwukryterialne zadanie poszukiwania optymalnego portfela akcji (5/5)
1,4
1,4
1,2
1,2
1
1
0,8
0,8
0,6
0,6
0,4
0,4 1
1,5
2
2,5
ryzyko portfela
oczekiwana stopa zysku z portfela w %
0,2
3
–3
y1
–2,5
–2
–1,5
ryzyko portfela ´ –1
y2
oczekiwana stopa zysku z portfela w %
y2
y2 oczekiwana stopa zysku z portfela w %
6. Programowanie wypukłe i kwadratowe
Granica efektywna
–1 y 1
1,4 1,2 1 0,8 0,6 0,4 0,2
1
1,5
2
2,5
3
y1 ryzyko portfela T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
46
6. Programowanie wypukłe i kwadratowe
Pora na relaks
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem
47
