wyk-optym-pr-geom-z-ogr.pdf

(207 KB) Pobierz
Programowaniegeometrycznezograniczeniami
Wcze–nieju»yli–mynier ó wno–ci(AG)dorozwi¡zaniazagadnieniaprogramowania
geometrycznegobezogranicze«,tzn.dozminimalizowaniafunkcjipostaci
X
n
Y
m
(t j ) ij
g(t)=g(t 1 ;:::;t m )=
c i
(1)
i=1
j=1
nazbiorzewektor ó wt=(t 1 ;:::;t m )takich,»et j >0,j=1;:::;m,gdziedane
s¡c i >0, ij 2 R ,j=1;:::;m,i=1;:::;n.Obecnierozszerzymytƒtechnikƒ
dozagadnieniaprogramowaniageometrycznegozograniczeniami,wkt ó rymfunkcja
celuifunkcjeograniczaj¡cebƒd¡postaci(1).Punktemwyj–ciadorozwi¡zaniatych
zagadnie«jestrozszerzonanier ó wno–¢Roz(AG).Wykorzystamyr ó wnie»Twierdze-
nieKarusha-Kuhna-Tuckerawpostacigradientowej,kt ó rebƒdziedostarcza“oteorety-
cznegouzasadnieniazastosowanejtechniki.
Zacznijmyodudowodnieniapewnegowariantunier ó wno–ciArytmetyczno-Geometrycznej.
Twierdzenie1(rozszerzonanier ó wno–¢Arytmetyczno-Geometryczna).Niech
x 1 ,:::,x n >0.Je»eli 1 ;:::; n albowszystkies¡dodatniealbowszystkies¡zerami
orazk“ad¡c= 1 +:::+ n ,to
n X
Y
i=1
i ) i ;
( x i
x i
Roz(AG)
i=1
przyprzyjƒciukonwencji0 0 =1oraz( x i 0 ) 0 =1.
Ponadto,r ó wno–¢wRoz(A G)zachodzi,wtedyitylkowtedy,gdyalbo 1 =:::=
n =0,gdy=0albo
n X
x i = i
x i
; i=1;:::;n; gdy >0:
i=1
Dow ó d.Dow ó dprzeprowadzonynawyk“adzie.
Przejd„mydode nicjizagadnieniaprogramowaniageometrycznegozograniczeni-
ami.
De nicja1.Za“ ó »my,»efunkcjezmiennycht=(t 1 ;:::;t m )-g 0 ;g 1 ;:::;g k s¡postaci
(1).Problempostaci
8
<
g 0 (t)!min
przyograniczeniach
g 1 (t)1;:::;g k (t)1;
t 1 ;:::;t m >0;
(CGP)
:
nazywamyproblememgeometrycznegoprogramowaniazograniczeniami.
1
1092455754.001.png 1092455754.002.png 1092455754.003.png
 
Uwaga1.Wprogramie(CGP)wystƒpujek+1funkcjika»daznichjestpostaci
X
n
Y
m
(t j ) ij :
g(t)=g(t 1 ;:::;t m )=
c i
i=1
j=1
Ka»d¡ztychfunkcjidajesiƒprzedstawi¢jakosko«czon¡sumƒsk“adnik ó wpostaci
u l (t)=c l t l1 1 :::t lm m :
W ó wczasproblem(CGP)mo»nazapisa¢wnastƒpuj¡cejr ó wnowa»nejpostaci
8
<
g 0 (t)=u 1 (t)+:::+u n 0 (t)!min
przyograniczeniach
g 1 (t)=u n 0 +1 (t)+:::+u n 1 (t)1;
:::::::::::::::::::::::::::::::::;
g k (t)=u n k 1 +1 (t)+:::+u n k (t)1;
gdziet 1 ;:::;t m >0; n k =p:
(CGP)
:
p-oznaczailo–¢wszystkichsk“adnik ó wu l wfunkcjiceluifunkcjachograniczaj¡cych.
Podobniejakwprogramowaniugeometrycznymbezogranicze«,dziƒki(AG)oraz
Roz(AG)okre–lamyproblemdualnydo(CGP)postaci
<
p Y
j k Y
c j j
i () i () !max
v()=v( 1 ;:::; p )=
j=1
i=1
przyograniczeniach
1 +:::+ n 0 =1;
11 1 +:::+ p1 p =0;
:::::::::::::::::::::;
1m 1 +:::+ pm p =0;
gdzie i >0; i=1;:::;n 0 ;
( l >0n i1 +1 l n i albo l =0n i1 +1 l n i );
oraz i ()= n i 1 +1 +:::+ n i ; i=1;:::;k:
(DCGP)
:
De nicja2.Niechdanebƒdziezagadnienieprogramowaniageometrycznegozograniczeni-
ami(CGP).Funkcjƒv()nazywamydualn¡funkcj¡celudladualnegozagad-
nieniaprogramowaniageometrycznegozograniczeniami(DCGP),aograniczenia
wystƒpuj¡cew(DCGP)nazywamydualnymiograniczeniami.Wektor( 1 ;:::; p )2
R
p
spe“niaj¡cyograniczeniaw(DCGP)nazywamywektoremdopuszczalnym(fea-
sible)dla(DCGP).Zagadnienieprogramowaniadualnegodoprogramowaniageom-
etrycznegozograniczeniaminazywamyzgodnym(consistent),gdyzbi ó rwektor ó w
dopuszczalnychdla(DCGP)jestniepusty.Rozwi¡zaniemdla(DCGP)nazywamy
wektordopuszczalnydla(DCGP),wkt ó rymfunkcjavosi¡gamaksimumglobalnena
zbiorzewektor ó wdopuszczalnychdla(DCGP).
2
Uwaga2.TwierdzeniaKarusha-Kuhna-Tuckerawpostacigradientowejniemo»na
bezpo–redniostosowa¢doka»degoprogramu(CGP),gdy»np.funkcjat ! t , 2
(0;1)niejestwypuk“a.Jednak»eka»d¡funkcjƒpostaci
X
n
Y
m
(t j ) ij
g(t 1 ;:::;t m )=
c i
i=1
j=1
mo»naprzekszta“ci¢dofunkcjiwypuk“ejh(x 1 ;:::;x m )na R
m stosuj¡czamianƒzmi-
ennych
t j =e x j ; t j >0 j=1;:::;m:
W ó wczas
X
n
P m j=1 ij x j :
h(x 1 ;:::;x m )=
c i e
i=1
Powy»szazamianazmiennychprzekszta“caproblemprogramowaniageometrycznegoz
ograniczeniami
8
<
g 0 (t)!min
przyograniczeniach
g 1 (t)1;:::;g k (t)1;
t 1 ;:::;t m >0;
(CGP)
:
naodpowiadaj¡cymuproblemwypuk“y
8
<
h 0 (x)!min
przyograniczeniach
h 1 (x)10;:::;h k (x)10;
x 2 R
(CGP) ?
:
m :
Poniewa»x ! e x jestfunkcj¡rosn¡c¡na R ,toprogramy(CGP)i(CGP) ? s¡r ó wnowa»ne
wtymsensie,»et ? =(t ? 1 ;:::;t ? m )jestrozwi¡zaniem(CGP),wtedyitylkowtedy,gdy
x ? =(x ? 1 ;:::;x ? m )jestrozwi¡zaniem(CGP) ? ,gdziet i =e x ? i ,i=1;:::;m.
Przejd„mydodowodug“ ó wnegotwierdzeniazwi¡zanegozzagadnieniemprogramowa-
niageometrycznegozograniczeniami.
Twierdzenie2.(i)Je»elitjestwektoremdopuszczalnymdla(CGP),ajestwektorem
dopuszczalnymdla(DCGP),to
g 0 (t) v()(nier ó wno–¢pierwotno-dualna):
(ii)Za“ ó »my,»eprogramgeometrycznegoprogramowaniazograniczeniami(CGP)jest
superzgodnyorazt ? jestrozwi¡zaniem(CGP).W ó wczasprogramdualnydo(CGP)-
(DCGP)jestzgodny,wiƒcejmarozwi¡zanie ? ,kt ó respe“niawarunki
g 0 (t ? )=v( ? );
( u i (t ? )
g 0 (t ? ) ; dlai=1;:::;n 0 ;
j ( ? )u i (t ? ); dlai=n j1 +1;:::;n j ; j=1;:::;k; n k =p:
i =
3
Dow ó d.(i)Niechtbƒdziewektoremdopuszczalnymdla(CGP),abƒdziewektorem
dopuszczalnymdla(DCGP).Dlal=1;:::;k, l >0,0< g l (t)1mamy,»e
(g l (t)) l 1.St¡d
Y
k
Y
k
(g l (t)) l =[u 1 (t)+:::+u n 0 (t)]
(g l (t)) l =
g 0 (t) g 0 (t)
l=1
l=1
= h 1 u 1 (t)
i k Y
(g l (t)) l (AG) n Y
i=1
Y
k
1 +:::+ n 0 u n 0 (t)
( u i (t)
i ) i
(g l (t)) l =
n 0
l=1
l=1
Mo»nazastosowa¢(AG),gdy»zdopuszczalno–ciwektora( 1 ;:::; p )wiadomo,»e
1 ;:::; n 0 >0oraz P n 0
i=1 i =1.
n Y
Y
m
Y
k
P n 0
i=1 ij i
( c i i ) i
(u n l 1 +1 (t)+:::+u n l (t)) l Roz(AG)
g 0 (t)
(t j )
i=1
j=1
l=1
( l ) l h u n l 1 +1 (t)
i n l
i n l 1 +1 ::: h u n l (t)
n l
n Y
Y
m
Y
k
P n 0
i=1 ij i
( c i i ) i
(t j )
=
n l 1 +1
i=1
j=1
l=1
Mo»nazastosowa¢krazyRoz(A G)dlag i ,i=1;:::;k,gdy»zdopuszczalno–ci
wektora( 1 ;:::; p )wiadomo,»e n i 1 +1 ;:::; n i s¡albojednocze–niedodatniealbo
jednocze–niezeramidlai=1;:::;k.Przekszta“caj¡cpowy»szedostajemy,»e
c n s
n s
n s
Y
n 0
Y
m
Y
k
Y
n l
Y
m
P k l=1 P n l
(t j ) P n 0
s=n l 1 +1 ls l =
( c i i ) i
i=1 ij i
( l ) l
g 0 (t)
(t j )
i=1
j=1
l=1
s=n l 1 +1
j=1
= p Y
i=1
( c i i ) i k Y
l=1
( l ) l Y
j=1
P p i=1 ij i :
(t j )
Nakoniec,zauwa»my,»ezdopuszczalno–ciwektora( 1 ;:::; p )wynikaj¡warunki
p
X
ij i =0; j=1;:::;m
i=1
cooznacza,»eprawastronanier ó wno–ciniezale»yodzmiennych(t 1 ;:::;t m )idotrzy-
mujemyoszczacowaniezdo“uwarto–cifunkcjig 0
g 0 (t) v():
(ii)Za“ ó »my,»et ? =(t ? 1 ;:::;t ? m )jestrozwi¡zaniemsuperzgodnegoprogramu(CGP).
W ó wczas(CGP) ? jestsuperzgodnyimarozwi¡zaniex ? =(x ? 1 ;:::;x ? m ),gdzie
x i =lnt i ; i=1;:::;m:
ZTwierdzeniaKarusha-Kuhna-Tuckerawpostacigradientowejotrzymujemyistnienie
mno»nikaKKT ? =( ? 1 ;:::; k )takiego,»e
4
a) i 0,i=1;:::;k,
b) i (h i (x ? )1)=0,i=1;:::;k,
c)(h 0 ) 0 x j (x ? )+ P i=1 i (h i ) 0 x j (x ? )=0,j=1;:::;m.
Poniewa»t j =e x j ,j=1;:::;m,tozpochodnejfunkcjiz“o»onejmamy,»e
@h i
@x j = @h i
@x j = @g i
@t i
@t j e x j ; i=0;1;:::;k; j=1;:::;m
@t j
st¡dorazfaktu,»ee x j >0,j=1;:::;mwarunekc)jestr ó wnowa»nywwarunkiem
c’)(g 0 ) 0 t j (t ? )+ P i=1 i (g i ) 0 t j (t ? )=0,j=1;:::;m.
Poniewa»t j >0,j=1;:::;m,toc’)jestrownowa»nyzwarunkiem
c )t j (g 0 ) 0 t j (t ? )+ P i=1 i t j (g i ) 0 t j (t ? )=0,j=1;:::;m.
Wykorzystuj¡cfakt(analogiczniejakwprogramowaniugeometrycznymbezogranicze«),
»eu l (t)=c l Q j=1 (t j ) lj dostajemy,»e
n X
t j (g 0 ) 0 t j (t ? )=
lj u l (t ? ); j=1;:::;m;
l=1
n X
t j (g i ) 0 t j (t ? )=
lj u l (t ? ); j=1;:::;m; i=1;:::;k:
l=n i 1 +1
Takwiƒcc )implikuje,»e
X
n 0
X
k
X
n r
lj u l (t ? )+
r rj u r (t ? )=0; j=1;:::;m:
l=1
r=1
l=n r 1 +1
Dziel¡cprzezg 0 (t ? )= P n 0
l=1 u l (t ? )>0dostajemy,»e
n X
X
k
n X
lj u l (t ? )
r rj u r (t ? )
g 0 (t ? ) +
g 0 (t ? ) =0; j=1;:::;m:
l=1
r=1
l=n r 1 +1
Zde niujemy ? nastƒpuj¡co
( u l (t ? )
g 0 (t ? ) ; dlal=1;:::;n 0 ;
? r u l (t ? )
l =
g 0 (t ? ) ; dlal=n r1 +1;:::;n r ; r=1;:::;k:
Zauwa»my,»e l >0dlal=1;:::;n 0 orazdlaka»degor=1;:::;kalbowszytkie
i >0,gdy r >0albowszytkie i >0,gdy r >0dlan r1 +1 i n r ,gdy»
r 0.
WarunkizKKTpokazuj¡,»espe“niones¡warunkinazerowaniesiƒpotƒgprzyzmien-
nychoraz
X
n 0
X
n 0
u l (t ? )
l =
g 0 (t ? ) =1:
l=1
l=1
5
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin