1
Du´ aln´ı simplexov´ a metoda
Autor: Mark´eta Popelov´ a Datum: 8.5.2011 Pˇredmˇet: Z´ aklady spojit´e optimalizace
Zad´ an´ı Mˇejme matici A ∈ Rm×n a prim´ arn´ı u ´lohu line´arn´ıho programov´an´ı v norm´aln´ım tvaru (P) a k n´ı pˇr´ısluˇsnou du´ aln´ı u ´lohu (D): (P ) max cT x, MP = {x ∈ Rn |Ax ≤ b, x ≥ 0} MP
(D) min bT y, MD = {y ∈ Rm |AT y ≥ c, y ≥ 0} MD
Ekvivalentn´ı u ´ lohy Prvnˇe vytvoˇrme u ´lohy (P’) a (D’) ekvivalentn´ı k (P) a (D) tak, ˇze pˇrid´ame nov´e promˇenn´e x0 = (xn+1 , . . . , xn+m ) y0 = (ym+1 , . . . , ym+n ) a definujeme u ´lohy jako (P 0 ) max cT x, MP0 = {(x, x0 ) ∈ Rn+m |Ax + x0 = b, x, x0 ≥ 0} MP
0
0 (D ) min bT y, MD = {(y, y0 ) ∈ Rn+m |AT y − y0 = c, y, y0 ≥ 0} MD
Myˇ slenka DSM Budeme proch´ azet pˇr´ıpustn´ a b´ azick´ a ˇreˇsen´ı du´aln´ı u ´lohy. Jim budou odpov´ıdat nepˇr´ıpustn´a b´azick´e ˇreˇsen´ı prim´ arn´ı u ´lohy se stejnou hodnotou c´ılov´e funkce. Tuto hodnotu budeme sniˇzovat, ˇc´ımˇz se bude zlepˇsovat hodnota c´ılov´e funkce du´ alu, avˇsak zhorˇsovat hodnota c´ılov´e funkce prim´aru. Jakmile dostaneme pˇr´ıpustn´e b´ azick´e ˇreˇsen´ı prim´ arn´ı u ´lohy, uk´ aˇzeme, ˇze to je optimum. Tabulka du´ aln´ı simplexov´e metody je redukovan´a, tedy neobsahuje jednotkovou podmatici za b´ azick´e sloupce. Ve sloupci d0 najdeme hodnoty prim´arn´ıch b´azick´ ych promˇenn´ ych a bude odpov´ıdat kriteri´aln´ımu ˇr´ adku. Uvˇedomme si, ˇze to, ˇze je prim´ arn´ı b´azick´e ˇreˇsen´ı nepˇr´ıpustn´e, znamen´a, ˇze m´a alespoˇ n jednu sloˇzku z´ apornou, tedy d0 6≥ 0. Tedy jakmile bude d0 ≥ 0, budeme v optimu (1. DSM). V ˇr´ adku d∗0 najdeme hodnoty du´ aln´ıch b´azick´ ych promˇenn´ ych. Ty maj´ı b´ yt po celou dobu pˇr´ıpustn´e, tedy d∗0 ≥ 0. Hodnota d00 odpov´ıd´ a hodnotˇe c´ılov´e funkce prim´arn´ı u ´lohy s prim´arn´ımi b´azick´ ymi promˇenn´ ymi, stejnˇe jako hodnotˇe c´ılov´e funkce du´ aln´ı u ´lohy s du´aln´ımi b´azick´ ymi promˇenn´ ymi. Na tabulku tedy m˚ uˇzeme nahl´ıˇzet jako simplexovou tabulku pro du´aln´ı u ´lohu, pˇriˇcemˇz je vˇse transponovan´e (hodnoty jsou v ˇr´ adku m´ısto ve sloupci, nem´ame kriteri´aln´ı ˇr´adek, ale sloupec, atd.). Algoritmus (Du´ aln´ı simplexov´ a metoda) 1. Inicializace. 2. Transformace. (a) Pokud (d0 ≥ 0) ⇒ x = (xB , xN ) = (d0 , 0) je optimum prim´arn´ı u ´lohy s hodnotou c´ılov´e funkce d00 ⇒ konec. (b) Pokud (∃i ∈ B : di0 < 0 & Di∗ ≥ 0) ⇒ (P) ani (D) nemaj´ı optim´aln´ı ˇreˇsen´ı ⇒ konec.
1
(c) Zvolme pivota Dsr a proved’mˇe transformaci D podle tohoto pivota. s := min{i ∈ B | di0 < 0} ∗ ∗ d0k d0j r := min k ∈ N j ∈ N, Dsj < 0 = min |Dsk | |Dsj |
1. DSM Necht’ d0 ≥ 0. Pak x = (xB , xN ) = (d0 , 0) je optim´aln´ı ˇreˇsen´ı prim´arn´ı u ´lohy a y = (yB , yN ) = (d∗0 , 0) je optim´ aln´ı ˇreˇsen´ı du´ aln´ı u ´lohy se spoleˇcnou hodnotou c´ılov´e funkce d00 . D˚ ukaz Algoritmus n´ am zaruˇcuje, ˇze y je pˇr´ıpustn´e b´azick´e ˇreˇsen´ı1 a ˇze d0 jsou hodnoty xB . Jsou-li vˇsechny kladn´e, m´ ame nav´ıc pˇr´ıpustn´e ˇreˇsen´ı prim´ arn´ı u ´lohy a dle principu duality se jedn´a o optim´aln´ı ˇreˇsen´ı se spoleˇcnou hodnotou c´ılov´e funkce, kter´ a je d00 dle volby simplexov´e tabulky. 2. DSM Necht’ ∃i ∈ B : di0 < 0 & Di∗ ≥ 0. Pak (P) ani (D) nemaj´ı optim´aln´ı ˇreˇsen´ı. D˚ ukaz aln´ıch Vezmˇeme si libovoln´e x ∈ MP0 . Pro nˇej plat´ı vztah xB = d0 − DxN ≥ 02 , kde B jsou indexy aktu´ b´ azick´ ych promˇenn´ ych, N indexy aktu´ aln´ıch neb´azick´ ych promˇenn´ ych. Tedy pro i-tou sloˇzku plat´ı: xi = di0 − D∗i xN < 0, a nebot’ di0 < 0 z pˇredpoklad˚ u vˇety, Di∗ ≥ 0 takt´eˇz z pˇredpoklad˚ u vˇety a xN ≥ 0 z definice MP0 . Tedy i-t´ 0 0 aporn´a, tedy MP = ∅ ⇒ MP = ∅. Tedy (P) nem´a optim´aln´ı ˇreˇsen´ı sloˇzka kaˇzd´eho pˇr´ıpustn´eho ˇreˇsen´ı MP je z´ a dle principu duality ani (D) nem´ a optim´aln´ı ˇreˇsen´ı. 3. DSM Necht’ nejsou splnˇeny pˇredpoklady 1. ani 2. DSM. Necht’ s := min{i ∈ B | di0 < 0} ∗ ∗ d0k d0j r := min k ∈ N = min j ∈ N, Dsj < 0 . |Dsk | |Dsj |
d00
Pak po jedn´e transformaci tabulky s pivotem Dsr dostaneme nov´e b´azick´e ˇreˇsen´ı x0 s b´azick´ ymi hodnotami a nov´e pˇr´ıpustn´e b´ azick´e ˇreˇsen´ı y0 s hodnotami d0∗ a spoleˇ c nou hodnotou c´ ılov´ y ch funkc´ ı 0 cT x0 = bT y0 = d000 ≤ d00 .
1 Jedn´ a 2 Toto
se sice o ˇreˇsen´ı (D’) a (P’), ale to jsou ekvivalentn´ı u ´lohy k (D) a (P).) bychom mˇ eli dok´ azat, ˇ ze to je zachov´ an´ı po celou dobu algoritmu.
2
D˚ ukaz Nejdˇr´ıve ukaˇzme, ˇze d00 jsou hodnoty x0B . Z indukˇcn´ıho pˇredpokladu v´ıme, ˇze d0 = A−1 B b, D = A−1 B AN . Podle stejn´e u ´vahy jako u SM plat´ı, ˇze d00 = A−1 B0 b, D0 = A−1 B0 AN0 . Z prvn´ı rovnosti vid´ıme, ˇze d00 jsou hodnoty nov´ ych b´azick´ ych promˇenn´ ych x0B . D´ale d∗0 udrˇzujeme tak, aby platilo d∗0 = (AT )−1 B0 c. D´ ale se uk´ aˇze i ten zbytek, kter´ y v podstatˇe vyjde z volby pivota.
Parametrick´ e programov´ an´ı Obor ˇreˇsitelnosti jsou takov´ a re´ aln´ a λ, ˇze s nimi m´a u ´loha ˇreˇsen´ı. Obor stability ˇreˇsen´ı x1 jsou takov´a re´ aln´ a λ, ˇze s nimi m´ au ´loha optim´ aln´ı ˇreˇsen´ı x1 . Funkce ˇreˇsitelnosti dan´e u ´lohy je φ(λ) = minM (c + λc0 )T x kde λ je z oboru ˇreˇsitelnosti. D´ a se dok´ azat, ˇze pro jedno x1 existuje uzavˇren´ y maxim´aln´ı obor stability. D´ ale ˇze pro λ mimo obor ˇreˇsitelnosti existuje otevˇren´ y interval okolo, kter´ y tak´e spad´a mimo obor ˇreˇsitelnosti. A nakonec, ˇze pro jedno x1 s nˇejak´ ym oborem stability existuje sousedn´ı x2 s navazuj´ıc´ım oborem stability.
´ Ulohy na voln´ y extr´ em Prostˇe takov´ a anal´ yznick´ au ´loha, kdy se hled´a glob´aln´ı extr´em funkce na Rn . Hledaj´ı se stacion´arn´ı body (nulov´ a derivace, resp. nulov´ y gradient (vektor parci´aln´ıch derivac´ı)). Pak se poˇc´ıt´a Hessi´an a ovˇeˇruje se definitnost ve stacion´ arn´ıch bodech. Jsou i nˇejak´e numerick´e metody.
Neline´ arn´ı programov´ an´ı Konvexn´ı programov´ an´ı – lok´ aln´ı minimum je i glob´aln´ı. Pro explicitnˇe-kvazikonvexn´ı to plat´ı takt´eˇz, ale pro konvexn´ı ne. Konvexn´ı ⇒ explicitnˇe-kvazikonvexn´ı ⇒ konvexn´ı Pseudokonvexn´ı: pomoc´ı gradientu f v pseudokonvexn´ım bodˇe lze urˇcit absolutn´ı minimum f na M. 1.0.1
Metody
1. Metody pˇr´ıpustn´ ych smˇer˚ u, napˇr. metoda Franka a Wolfa. Fajn pro konvexn´ı M , aby ˇslo rychle urˇcit, zda jsi uvnitˇr. C´ılov´ a fce f libovoln´ a, ale f ∈ C 1 . 2. Metody vnˇejˇs´ı aproximace, jako seˇcn´e nadroviny. Najde se konvexn´ı polyedr, co obsahuje M , najde se jeho optimum. A kdyˇz tam neleˇz´ı, tak se sestroj´ı seˇcn´a nadrovina a uˇr´ızne se kus konvexn´ıho polyedru. Fajn pro jednoduchou c´elovou funkci, ide´alnˇe liner´an´ı, p´aˇc se pak l´epe hled´a optimum na tom konvexn´ım polyedru. 3. Metody vnitˇrn´ı aproximace. C´ılov´ a funkce se aproximuje nˇejakou snazˇs´ı. 4. Metody zaloˇzen´e na K.-T. podm´ınk´ ach. Vhodn´e pro kvadratick´e programov´an´ı, p´aˇc z toho pak vznikne soustava rovnic a nerovnic. 5. Branch and Bound. Dˇel´ı velkou u ´lohy na posloupnost menˇs´ıch. Fajn pro koneˇcnou M .
3
6. Penalizaˇcn´ı metody. Vyjde se z libovoln´eho bodu a pak se pˇribliˇzuje k M . C´ılov´a funkce je nˇejak min f + αk p(x) a jelikoˇz αk → ∞, tak potˇrebujeme, aby p → ∞, coˇz znamen´a, ˇze se pˇribliˇzujeme k M . 7. Bari=rov´e metody. Mus´ı se naj´ıt vnitˇrn´ı bod M . Pak se nˇejak zlepˇsuje hodnota c´ılov´e funkce. V´ yhodn´e je, ˇze lze skonˇcit a m´ıt pˇrijateln´e ˇreˇsen´ı. 1.0.2
Metoda Franka a Wolfa
f je libovoln´ a konvexn´ı z C 1 funkce, M je omezen´ y konvexn´ı polyedr (tedy d´an soustavou nerovnic). 1. Najdeme v´ ychoz´ı bod x1 ∈ M . Kdyˇz neexistuje, tak hotovo (M pr´azdn´a). 2. Sestav´ıme teˇcnou nadrovinu M v x1 jako ∇f (x1 )(x − x1 ), coˇz je line´arn´ı funkce. Staˇc´ı uvaˇzovat ∇f (x1 )T x, p´ aˇc minimum nez´ avis´ı na konstantˇe. Najdeme minimum na M s touto c´ılovou line´ arn´ı funkc´ı pomoc´ı SM, oznaˇc´ıme ho x ˆ. Pokud x1 nebylo optimum, tak m´ame pˇr´ıpustn´ y smˇer x ˆ − x1 , kter´ y alespoˇ n kousek kles´ a, tedy derivace f v tomto smˇeru z bodu x1 je ∇f (x1 )T (x − x1 ) ≤ 0. (Kdyby byla rovna nule, jsme v optimu. Pokud ∇f (ˆ x)T (x − x1 ) ≤ 0, urˇc´ıme x2 := x ˆ a pokraˇcujeme krokem 1. Jinak 1 1 hled´ ame min f (x aλ(ˆ x − x )) pro λ ∈ h0, 1, i, coˇz je funkce jedn´e promˇenn´e na kompaktn´ı mnoˇzinˇe, tedy m´ a dle Weierstrasse minimum a lze ho jasnˇe urˇcit hnusn´ ym vzorcem s derivacemi. Kdyˇz ho tam dosad´ıme, z´ısk´ ame x2 pro dalˇs´ı krok.
V´ıcekriteri´ aln´ı programov´ an´ı C´ılovou funkci tvoˇr´ı vektor s funkc´ı fi : Rn → R. M´ame 4 moˇznosti, jak hodnotit, kter´e ˇreˇsen´ı je nejlepˇs´ı: 1. Ide´ aln´ı ˇreˇsen´ı. Je maximem pro vˇsechny fi . To typicky nenast´av´a. 2. Dominantn´ı ˇreˇsen´ı. Vybereme si jednu fi a na ostatn´ı se vybodnem. 3. Kompromisn´ı ˇreˇsen´ı. Uˇzivatel n´ am ta fi nˇejak ohodnot´ı (tˇreba jim d´a v´ahy), tzn. d´a n´am funkci F (fi ) a my pak ˇreˇs´ıme maximum t´eto funkce. Dˇel´ı se to jeˇstˇe podle toho, kdy tyto preference dostaneme: (a) Nikdy. Nˇejak je tedy vymysl´ıme sami, v podstatˇe sp´ıˇse z matematick´eho hlediska. (b) Pˇred v´ ypoˇctem. Fajn, rozvnou v´ıme, co ˇreˇsit. (c) Pˇri v´ ypoˇctu. To je pak pr´ y nˇejak sloˇzit´e. (d) Po skonˇcen´ı v´ ypoˇctu. Na zaˇc´ atku si je nˇejak zvol´ıme a po konci to zopakujeme s preferencemi uˇzivatele. 4. Eficientn´ı ˇreˇsen´ı. Neexistuje jin´e takov´e, ˇze by bylo ve vˇsech fi alespoˇ n stejnˇe dobr´e a v alespoˇ n jedn´e fj by bylo lepˇs´ı. Eficientn´ı ˇ reˇ sen´ı S Podstatn´ y je skal´ arn´ı parametrick´ y ekvivalent obecn´e u ´lohy VP. Plat´ı totiˇz, ˇze λ>0 Mopt (λ), tedy sjednocen´ı pˇres vˇsechna λ mnoˇzin vˇsech optim´ aln´ıch ˇreˇsen´ı pro dan´e λ, patˇr´ı cel´a do mnoˇziny vˇsech eficientn´ıch ˇreˇsen´ı . D˚ ukaz je snadn´ y, d˚ usledky jsou d˚ uleˇzit´e. Dokonce pro line´arn´ı VP se to rovn´a, pro konvexn´ı sice ne, ale lze odhadnout zhora sjednocen´ım stejn´e mnoˇziny pˇres λ ≥ 0. Pro tento typ ˇreˇsen´ı existuj´ı algoritmy dialogu. Ten prvn´ı si zvol´ı nˇejak´a vhodn´a λ1 , λ2 , ˇreˇs´ı pak maximum λ1 + t(λ2 − λ1 )T f (x), kde t je voliteln´ y parametr. Pro t = 0 to vyˇreˇs´ı a nab´ıdne uˇzivateli optim´aln´ı ˇreˇsen´ı spoleˇcnˇe s nˇekolika dalˇs´ımi informacemi. Uˇzivatel se m˚ uˇze rozhodnout, zda: 1. pokraˇcovat v tomto smˇeru, tedy zvˇetˇsit t, 2. pokraˇcovat v jin´em smˇeru, tedy zmˇenit λ2 , 3. vr´ atit se k dˇr´ıve dosaˇzen´emu optimu a pˇr´ısluˇsn´emu λ,
4
4. zmˇenit λ1 , λ2 , 5. skonˇcit. Druh´ y algoritmus dialogu se pouˇzije tehdy, co je uˇzivatel dlouho nespokojen. Nˇejak se tam zavede jeˇstˇe nˇejak´e K a kdyˇz je z nˇejak´eho hlesika (jedn´e fi ) v´ ysledek jiˇz dobr´ y, tak se dan´e fi uˇz nesnaˇz´ıme zlepˇsit, ale snaˇz´ıme se ho pˇr´ıliˇs nezhorˇsit. Kompromisn´ı ˇ reˇ sen´ı Kdyˇz n´ am uˇzivatel nic ned´ a, pouˇzije se metoda glob´aln´ı c´ılov´e funkce. Pro kaˇzd´e i se najde vyˇreˇs´ı maximalizace fi (x). A pak hled´ a ˇreˇsen´ı, kter´e se minim´alnˇe odch´ yl´ı od kaˇzd´e z tˇechto hodnot. D´a se uk´azat, ˇze toto je eficientn´ı ˇreˇsen´ı. Pak jsou jeˇstˇe nˇejak´e dalˇs´ı moˇznosti.
Dynamick´ e programov´ an´ı Syst´em je to, co zkoum´ ame v ˇcasov´em intervalu ht1 , t2 i. Stav syst´emu v ˇcase t je popsan´ y n-tic´ı stavov´ych promˇenn´ych. X ⊂ Rn je mnoˇzina pˇr´ıpustn´ ych stav˚ u. Stavy se mˇen´ı na z´akladˇe rozhodnut´ı u, coˇz je m-tice rezhodovac´ıch promˇenn´ych. U ⊂ Rm je mnoˇzina pˇr´ıpustn´ ych rozhodnut´ı. Rozhodov´ an´ı mohou nast´ avat bud’ v libovoln´em ˇcase (ˇcas je spojit´ y), coˇz vede na Pontrjagin˚ uv princip maxima, nebo jen v diskr´etn´ıch ˇcasov´ ych okamˇzic´ıch, coˇz budeme uvaˇzovat v dalˇs´ı ˇc´asti. D´a se pak totiˇz uk´ azat, ˇze plat´ı Ballman˚ uv princip optimality, kter´ y ˇr´ık´a, ˇze kaˇzd´a podstategie optim´aln´ı strategie je optim´ aln´ı. Def. Chov´ a-li se syst´em v ˇcasov´em intervale ht1 , t2 i dle n´asleduj´ıc´ıch podm´ınek, ˇr´ık´ame, ˇze v ht1 , t2 i prob´ıh´ a N -stupˇ nov´ y diskr´etn´ı proces se stavovou transformac´ı ∀i ∈ ht1 , t2 ixi+1 = Ti (xi , ui ). T´ım je myˇsleno, ˇze stav syst´emu v ˇcase i je d´ an nˇejakou funkc´ı pˇredchoz´ıho stavu a pˇredchoz´ıho rozhodnut´ı. A ted’ ty podm´ınky: 1. Interval ht1 , t2 i je rozdˇelen pomoc´ı t1 , . . . , tN ˇcasov´ ych okamˇzik˚ u, kde N > 0, N ∈ N. 2. Stav syst´emu se mˇen´ı jen v ti , kde i ∈ h1, N i ∩ Z. 3. ∀i v intervalu hti−1 , ti ) m´ ame stav xi , pˇred prvn´ım rozhodnut´ım u1 m´ame poˇc´ateˇcn´ı stav x1 a posledn´ı stav je xn+1 . 4. Stav xi+1 z´ avis´ı jen na xi , ui . P´ıˇseme ∀i ∈ ht1 , t2 ixi+1 = Ti (xi , ui ). ˇ m´ Cas ame rozdˇelen diskr´etnˇe na intervaly t1 , . . . , tN . V kaˇzd´em tomto intervalu se zmˇen´ı stav na z´ akladˇe rozhodnut´ı u, coˇz je m-tice nˇejak´ ych re´ aln´ ych ˇc´ısel. Pˇr´ıpustn´a strategie je posloupnost u1 , . . . uN , ˇze vede z pˇr´ıpustn´eho stavu do pˇr´ıpustn´eho stavu po pˇr´ıpustn´ ych stavech pˇres pˇr´ısluˇsn´a rozhodnut´ı. Zaj´ım´ a n´ as pˇredevˇs´ım u ´loha, kdy m´ ame d´ an vstupn´ı stav x1 a m´ame za N krok˚ u nasb´ırat co nejv´ıce bod˚ u pˇrechody mezi stavy, pˇriˇcemˇz u ´ˇcelov´ a funkce z´ avis´ı vˇzdy na stavu, odkud jsme pˇriˇsli, a rozhodnut´ı, kter´e n´as k tomu vedlo, a ˇcase, ve kter´ y se to dˇeje. Dynamick´e programov´an´ı vyuˇz´ıv´a Bellman˚ uv princip optimality, ˇze kaˇzd´ a podstategie optim´ aln´ı strategie je optim´ aln´ı. 1. Pro kaˇzd´ y pˇredposledn´ı stav vybereme posledn´ı stav, kter´e spojuje hrana nejvyˇsˇs´ı hodnoty. 2. Pro kaˇzd´ y pˇredpˇredposledn´ı stav vybereme nejlepˇs´ı pˇredposledn´ı stav, tedy maximalizujeme hodnotu hrany do tohoto stavu + hodnotu c´ılov´e funkce v tamtom stavu, kterou uˇz m´ame spoˇc´ıtanou. 3. . . . atd. aˇz z´ısk´ ame optim´ aln´ı hodnotu pro prvn´ı vrchol.
5
Teorie her M´ ame matici A, ˇr´ adkov´ y hr´ aˇc si vyb´ır´ a i index ˇr´adku, sloupcov´ y j index sloupce, ˇr´adkov´emu se pˇriˇcte aij , coˇz m˚ uˇze b´ yt i z´ aporn´e. Strategie hr´ aˇce je vektor pravdˇ e podobnost´ ı v´ ybˇeru dan´eho indexu. Jsou-li dan´e Pn strategie p, q, je oˇcek´ avan´ a hodnota E(p, q) = i,j=1 pi aij qj . Vˇeta ˇr´ık´ a, ˇze existuj´ı optim´ aln´ı strategie p∗ , q ∗ , ˇze E(p∗ , q) ≥ E(p∗ , q ∗ ) ≥ E(p, q ∗ ) = v. Tedy se jim nevyplat´ı hr´ at jinak neˇz tou optim´ aln´ı strategi´ı. Tedy vˇzdy existuje nˇejak´e v, kter´e m˚ uˇze hr´aˇc uhr´at, at’ bude hr´ at ten druh´ y jakkoliv. N´ as zaj´ım´ a optim´ aln´ı strategie p∗ , q ∗ . Nˇejak uk´aˇzeme, ˇze staˇc´ı uvaˇzovat jednotkov´e vektory. D´ale z toho sestav´ıme u ´lohu line´ arn´ıho programov´ an´ı, kde p∗ bude optim´aln´ı ˇreˇsen´ı prim´aru a q ∗ bude optim´aln´ı ˇreˇsen´ı du´ alu.
6
