Post on 14-Jan-2016
description
transcript
Gradientní metody
Metoda největšího spádu (volný extrém)
Zoutendijkova metoda (vázaný extrém)
Metoda největšího spádu
• Řešíme úlohu na volný extrém
• Předpoklad: funkce f je diferencovatelná
• Největší spád je ve směru gradientu
• Volíme výchozí bod• Určíme směr• Určíme délku k-tého
kroku • Konstruujeme
posloupnost bodů
fD)f( xxmin
d=- f x
k
,,,k)f(ηkdexxxx kkkkkk 210,,,...,,...,, 1121 xxx
Pro lineární funkci je gradient směrnicí kolmice. Přímka účelové funkce se posouvá ve směru kolmice, tj. ve směru gradientu.
Nejkratší cesta?
Gradientní metoda s krátkým krokem
• Volíme konstantní délku kroku
• Optimum:• Sledujeme
konvergenci:
• Zvolíme dostatečně malé - optimum:
f x 0
1
f x 0
0k kx x
21k k(x x ) ε
ε
Příklad 1
• Minimalizujte funkci:• Výchozí bod:• Délka kroku:
2 22 1 2 1 2f x 12 4 4 4x x x x x
0
0
0x
0,1
1 2
1 2
1 0 0 1
2 1 1 2
3 2 2
8 4f x
12 4 8
0 0 0 4,80,1 f 0,1 ; f
0 12 1,2 2,4
0 4,8 0,48 1,920,1 f 0,1 ; f
1, 2 2, 4 1, 44 2,4
0,480,1 f
1, 44
x x
x x
x x x x
x x x x
x x x
3
4 3 3 4
1,92 0,68 1,280,1 ; f
2,4 1,68 1, 28
0,68 1,28 0,81 1,440,1 f 0,1 ; f
1,98 1, 28 2,11 1,64
x
x x x x
Gradientní metoda s dlouhým krokem
• Pro každý krok počítáme délku kroku
• Pro největší zlepšení hodnoty účelové funkce
• Délka kroku – pomocná úloha
1( ) ( ( ))k k k kf f f x x x
0,0))(((max
kkk ffd
dxx
Příklad 1 b
Stejná funkce i výchozí bod, hledáme takovou délku kroku,aby v bodě x1 dosáhla funkce minima (lokálního). Vyjádříme x1 a dosadíme do původní funkce f. Vzniklá funkce je konvexní funkce 1 proměnné , její bod minima najdeme pomocí první derivace=0.
1 0 1 0 11
2 22 1 2 1 2
2 21 1 1 1 1 1 1
11
1
1
00 0f
120 12
f x 12 4 4 4
f 12 12 4 12 144 576
1152 144 0
1440,125
1152
x x x
x x x x x
x
d
d
1 0 1 0 11
1
212 1 2 2
22 2 2 2 2
00 0 0 0f
120 12 12.0,125 1,5
6f
0
0 6 6f x
1,5 0 1,5
9 36 144
x x x
x
x x
f x
Optimalizace s podmínkamiÚloha s přípustným směrem
• Řešíme úlohu na vázaný extrém (omezující podmínky mohou být nelineární)
• Konstruujeme posloupnost bodů
• Řešení je přípustné:
• Snížení účelové funkce dosáhneme, pokud navíc platí:
nji R,n,,j,x,m,,i,)(q)f( xxx 1010min
,,,kskdexxxx kkkkk 210,,,...,,...,, 1121 xx
0, 1, ,i k kq ( ) i m x s
( ) 0Tf s x
Příklad 2• Je daná úloha:• Výchozí bod:
• Vektor s je přípustným směrem, pokud platí:
• Ke snížení hodnoty účelové funkce dojde, jestliže:
(Řešením může být více než jeden přípustný směr, v němž dojde ke snížení ÚF)
2 2
1 2
1 2
1 2
1 2
3 1 min
3
3 5
0; 0
x x
x x
x x
x x
1
2x
1 2
1 2
0
3 0
s s
s s
2 21 1 2 2
1
2
0
1 2
6 9 2 1
2 6
2 2
1 4
2 2
4 2 0
f x x x x x
xf x
x
f x f x
s s
Grafické znázornění
X0 výchozí bod
X=(3,1) globální minimum
Obecný algoritmus
• 1. krok - Výchozí řešení– Za výchozí bod iteračního postupu zvolíme libovolný bod x z
množiny M , tj. libovolné přípustné řešení, které označíme x0 , k = 0.
• 2. krok - Směr a délka kroku– Řešení (k+1) iteračního kroku vypočítáme pomocí směrového
vektoru a délky kroku
– Přitom musí platit: xk+1 M a f(xk+1 ) = f(xk + sk) < f(xk )• 3. krok - Test optimality
– Pokud nelze nalézt směrový vektor nebo délku kroku tak, aby byly splněny podmínky 2), je poslední nalezené řešení xk optimálním řešením a výpočet končí.
– Jinak je určeno nové řešení xk+1, položíme k = k+1 a přejdeme ke kroku 2 - budeme hledat nový směr a délku kroku.
Zoutendijkova metoda
1. krok
Zvolíme přípustné výchozí řešení x0;k=0
Pokud bod leží na některé hraniční přímce (není vnitřním bodem množiny přípustných řešení), přidává se k úloze o optimálním směru podmínka:
0ia s
Zoutendijkova metoda
2. krok
Určení optimálního směru: Směr, který svírá minimální úhel s gradientem a je přípustný.
Příslušná úloha je nelineární a nahrazuje se jednodušším lineárním vztahem – lineární normalizace vztahu
00
0
1,
1min
Tf xf x s s s s
s s
f x ss
Úloha o optimálním směru
Vypočítáme gradienty funkcí f a g v bodě xk a vyřešíme pomocnou úlohu lineárního programování o optimálním směru. Jestliže opt. řešení úlohy (OS) má nulovou hodnotu kritéria, pak je algoritmus u konce a řešení xk je optimálním řešením
njs
qmi)(q
f(
j
kikki
kk
,,1,11
0)(a,,1pro0
)min
xsx
sx
Úloha o optimálním směru
Úloha vede na řešení simplexem. Abychom zajistili nezápornost proměnných, přičteme 1:
k
1 1
0 2
0
pouze pro hraniční přímky (funkce), na nichž bod x leží
j
j
i k k
s
s
q ( )
x s
Zoutendijkova metoda
3. krok: Určení optima
Jestliže opt. řešení úlohy (OS) má nulovou hodnotu kritéria, pak je algoritmus u konce a řešení xk je optimálním řešením, jinak pokračujeme krokem 4.
Zoutendijkova metoda
4. Krok: Určení délky kroku
z hlediska přípustnosti nového řešení a z hlediska největší možné celkové změny hodnoty účelové funkce.
5. krok – test optimality II.– Jestliže délka kroku nulová, je řešení xk je optimální
– Jinak jsme nalezli nové řešení a přejdeme ke kroku 2.
0min:
+ max
,(min
**
*
***
)f(
M
)
kk
kk
k
sx
sx
Příklad 2b
1. krok• Výchozí bod splňuje
první 2 omezující podmínky jako rovnice, tj. leží na příslušných hraničních přímkách
2 21 1 2 2
1 1 2
2 1 2
1 2
6 2 10
: 3
: 3 5
0; 0
f x x x x x
q x x
q x x
x x
0
1
2x
Příklad 2b
2. Krok – úloha o OS
2 21 1 2 2
1
2
1 1 2
1
2 1 2
2
6 2 10
2 6
2 2
: 3
1
1
: 3 5
1
3
f x x x x x
xf x
x
q x x
q
q x x
q
1 2
1 2
1
2
1 2
1
2
0
0
3 0
1 1
1 1
4 2 min
2 6
2 2
4
2
s s
s s
s
s
s s
xf x
x
f x
1 1 2 2
1 1 2 2
1 2
1 2 2
1 2
1 2
1
2
1 2
1; 1
1; 1
1 1
2
3
0
4 1
2
2
2
4 2 2 mi
2 1 min
n
s s s s
s s s s
s s
s s
s s
s
s
s
s
s
s
-4 2 0 0 0 0s1 s2 d1 d2 d3 d4 b
0 d1 1 1 1 0 0 0 20 d2 -1 3 0 1 0 0 20 d3 1 0 0 0 1 0 20 d4 0 1 0 0 0 1 2
4 -2 x x x x 00 d1 0 1 1 0 -1 0 00 d2 0 3 0 1 1 0 4-4 s1 1 0 0 0 1 0 20 d4 0 1 0 0 0 1 2
x -2 x x -4 x -8
• Hodnota optimální ÚF úlohy o optimálním směru není nula – řešení není optimální.
1 2
1 1 2 2
1 2
2; 0
1; 1
1; 1
s s
s s s s
s s
Příklad 2b- Určení délky kroku0
1 00
0 0
0 0
0
0
0
0
0
0
*
11 1
22 1
1 2 3...platí vždy
1 6 3 5
5 4 5
0
1 0
1
2 0
2
2
x
0
2 2
0 0 0 0
20
0
0
**0
0
min 1 6 1 2 2 2 10
min 2 6 5
4 6 0
3
23
23 3
min(2, )2 2
01 0
0
0
01 1
0
11
2
11 1
22 1
3
25
1 2 ...bod leží jenom na q2 1
2
2 6 1
2 2 1
x
x
xf x
x
Grafické znázornění
0
X0 =(2,1)
výchozí bod
X=(3,1) globální minimum
Směr s0
X1=(2,5;0,5)
-1 -1 0 0 0s1 s2 d1 d2 d3 b
0 d1 1 1 1 0 0 20 d2 1 0 0 1 0 20 d3 0 1 0 0 1 2
1 1 x x x 00 d1 0 1 1 -1 0 0-2 s1 1 0 0 1 0 20 d3 0 1 0 0 1 2
x 0 x -2 x -4
1 2
1 1 2 2
1 2
1 2
2; 0
1; 1
1; 1
( ) : min
1 1 min
( ) 0
s s
s s s s
s s
Uf OS s s
Uf OS
ŘEŠENÍ JE OPTIMÁLNÍ