Polynomiální algoritmy. Petr Kolman

Polynomi´ aln´ı algoritmy pro line´ arn´ı programov´ an´ı Petr Kolman Prosinec 2013

Pˇredmluva Tento text se snaˇz´ı ˇctenáˇri se základn´ımi znalostmi line´ arn´ı algebry, matematické anal´ yzy a line´ arn´ıho programován´ı elementárn´ım zp˚ usobem pˇredstavit dvˇe metody pro ˇreˇsen´ı u ´loh line´ arn´ıho programován´ı v polynomi´ aln´ım ˇcase, totiˇz elipsoidovou metodu a metodu vnitˇrn´ıho bodu (resp. jednu z jej´ıch mnoha variant ze skupiny metod sniˇzován´ı potenci´ alu). Dˇekuji Martinu Perglovi za v´ ychoz´ı verzi poznámek k elipsoidivé metodˇe podle bˇehu pˇredn´ aˇsky Matematické programován´ı v roce 2006/2007 a Duˇsanovi Knopovi za elektronickou podobu jeho poznámek k metodˇe vnitˇrn´ıho bodu z bˇehu téˇze pˇredn´ aˇsky ve ˇskoln´ım roce 2008/2009. Za podporu dˇekuji téˇz Centru Excelence – Institutu Teoretické Inforˇ matiky (CE – ITI, projekt P202/12/G061 GA CR).

Praha, prosinec 2013

Petr Kolman

Obsah

1 Struˇ cn´ y historick´ yu ´ vod 2 Elipsoidov´ a metoda 2.1 N´ aˇcrt algoritmu . . . . . . . . . . . . . . . . 2.2 Opakovan´ı z line´ arn´ı algebry . . . . . . . . 2.3 Poˇcáteˇcn´ı elipsoid . . . . . . . . . . . . . . . 2.4 Iteraˇcn´ı krok: v´ ypoˇcet Ek+1 z Ek . . . . . . 2.5 Kdy skonˇcit . . . . . . . . . . . . . . . . . . 2.6 Jak se zbavit zjednoduˇsuj´ıc´ıch pˇredpoklad˚ u 2.7 Shrnut´ı . . . . . . . . . . . . . . . . . . . .

1 . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

5 5 6 8 9 15 17 19

3 Metoda vnitˇ rn´ıho bodu 3.1 N´ aˇcrt algoritmu . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Základn´ı definice a pozorován´ı . . . . . . . . . . . . . . . 3.3 Struktura algoritmu . . . . . . . . . . . . . . . . . . . . . 3.4 Jak nalézt striknˇe pˇr´ıpustn´ a ˇreˇsen´ı s omezen´ ym potenciálem 3.5 Iteraˇcn´ı krok . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Jak ze skoro optimáln´ıho ˇreˇsen´ı naj´ıt u ´plnˇe optimáln´ı . . . 3.7 Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21 21 23 25 26 28 35 37

Literatura

40

1 Struˇcn´ y historick´ yu ´vod Soustavám line´ arn´ıch nerovnic a teorii mnohostˇen˚ u, vˇcetnˇe jejich aplikac´ı, vˇenovali matematikové pozornost pˇrinejmenˇs´ım od 19. stolet´ı. Jmenujme alespoˇ n Fouriera, jeˇstˇe pˇred n´ım Lagrangea a Bernoulliho, pozdˇeji Farkase a Minkowského. Za poˇcátek nového oboru naz´ yvaného line´ arn´ı programován´ı se pokl´ ad´ a ale aˇz druhá polovina 40. let 20. stolet´ı. Matematické základy oboru tehdy poloˇzili pˇredevˇs´ım von Neumann a trojice matematik˚ u Gale, Kuhn, Tucker. Jejich hlavn´ım pˇr´ınosem bylo vybudován´ı teorie duality line´ arn´ıho programován´ı; von Neumann ve svém pˇr´ıstupu vyuˇzil v´ ysledky, které z´ıskal pˇri práci na jiném novém oboru rozv´ıjej´ıc´ım se v té dobˇe, teorii her. Jeˇstˇe pˇred nimi se nez´ avisle na sobˇe souvisej´ıc´ım problémum vˇenovali v Sovˇetském svazu Kantoroviˇc a ve Spojen´ ych státech Hitchcock; jejich práce z˚ ustaly ˇzel ˇrady let nedocenˇeny. Kl´ıˇcov´ ym momentem pro v´ yvoj line´ arn´ıho programován´ı byl Dantzig˚ uv simplexov´ y algoritmus (publikován 1947), kter´ y se na mnoho let stal nezbytnou souˇcást´ı oboru. Nezanedbateln´ ym podnˇetem, kter´ y rozvoj line´ arn´ıho programován´ı podstatnˇe ovlivnil a podpoˇril, byl pˇr´ıchod poˇc´ıtaˇc˚ u, z nichˇz prvn´ı pˇriˇsly na svˇet právˇe ve 40. letech. Uspokojivé praktické v´ ysledky simplexového algoritmu byly v´ yborn´ ym doporuˇcen´ım pro jeho ˇsiroké pouˇzit´ı v praxi a line´ arn´ı programov´ an´ı se simplexov´ ym algoritmem se na dlouhou dobu stalo nezbytn´ ym arzen´ alem ekonom˚ u. Za zm´ınku stoj´ı v této souvislosti skuteˇcnost, ˇze Kantoriviˇc a Koopmans, kteˇr´ı v´ yraznˇe pˇrispˇeli k rozvoji line´ arn´ıho programován´ı, obdrˇzeli spoleˇcnˇe v roce 1975 Nobelovu cenu za ekonomii. Témˇeˇr oddˇelenˇe prob´ıhal v´ yvoj t´ ykaj´ıc´ı se obecnˇejˇs´ıch optimalizaˇcn´ıch problém˚ u. V tomto svˇetˇe se doˇckaly velkého rozkvˇetu v 60. letech 20. stolet´ı postupy zn´ amé dnes pˇredevˇs´ım pod jménem metody

2

Kapitola 1. Struˇcn´ y historick´ yu ´vod

vnitˇrn´ıho bodu (Frisch, Fiacco, McCormick). Algoritmy navrˇzené v této dobˇe vˇsak ˇcasto trpˇely numerickou nestabilitou. S nov´ ym podnˇetem k dalˇs´ımu rozvoji line´ arn´ıho programován´ı pˇriˇsla na poˇcátku 70. let teorie sloˇzitosti. Nejprve se ˇrada lid´ı pokouˇsela dokázat, ˇze simplexov´ y algoritmus pracuje v polynomi´ aln´ım ˇcase. V roce 1972 ovˇsem Klee a Minty popsali pˇr´ıklad ukazuj´ıc´ı exponenciáln´ı ˇcasovou sloˇzitost pro nˇekteré varianty simplexového algoritmu; brzy pˇribyly podobné v´ ysledky i pro jiné varianty algoritmu. To podn´ıtilo zájem o alternativn´ı postupy na ˇreˇsen´ı u ´loh line´ arn´ıho programován´ı. Zlom pˇricház´ı v roce 1979, kdy rusk´ y matematik Chaˇcijan publikoval v ruˇstinˇe krátk´ y ˇcl´ anek (bez d˚ ukaz˚ u) o tom, jak lze pomoc´ı tzv. elipsoidové metody ˇreˇsit u ´lohu line´ arn´ıho programován´ı v polynomi´ aln´ım ˇcase; samotná metoda byla navrˇzena jiˇz dˇr´ıve v 70. letech pro problémy konvexn´ıho nelineárn´ıho ˇ programován´ı (Yudin, Nemirovski, Sor). V´ ysledek mˇel neb´ yval´ y medi´ aln´ı ohlas, ˇzel se ale záhy ukázalo, ˇze k praktickému pouˇzit´ı se metoda nehod´ı. Hled´ an´ı alternativ simplexového algoritmu pokraˇcovalo. Dalˇs´ım mezn´ıkem v historii line´ arn´ıho programován´ı byl rok 1984, kdy Karmakar ze spoleˇcnosti AT&T navrhl algoritmus spadaj´ıc´ı do skupiny metod vnitˇrn´ıho bodu a dokázal, ˇze doba jeho bˇehu je polynomi´ aln´ı. Jak jsme jiˇz zm´ınili v´ yˇse, samotná metoda nebyla nová, hlavn´ı Karmarkar˚ uv pˇr´ınos byl v aplikaci metody na u ´lohu line´ arn´ıho programován´ı a zejména v anal´ yze ˇcasové sloˇzitosti algoritmu. Za zm´ınku stoj´ı, ˇze velmi podobn´ y algoritmus pro line´ arn´ı programován´ı navrhl (1967) a posléze (1974) dokázal jeho konvergenci k optimáln´ımu ˇreˇsen´ı Kantoroviˇc˚ uv student, rusk´ y matematik Dikin; jeho práce ˇzel z˚ ustala dlouho nepovˇsimnuta. Od roku 1984 byly publikovány doslova tis´ıce ˇcl´ ank˚ u t´ ykaj´ıc´ıch se metod vnitˇrn´ıho bodu. Velmi zhruba se daj´ı rozdˇelit na metody sniˇzován´ı potenciálu (sem patˇr´ı Karmakar˚ uv algoritmus a také algoritmus popsan´ y v tomto textu), metody sledován´ı centráln´ı cesty (ty se dnes zdaj´ı nejlepˇs´ı pro praktické pouˇzit´ı a hojnˇe se pouˇz´ıvaj´ı v softwarov´ ych bal´ıc´ıch pro line´ arn´ı programován´ı, pˇredevˇs´ım algoritmy tzv. Mehrotrova typu) a metody afinn´ıch transformac´ı (u tˇech se vˇetˇsinou dokazuje pouze konvergence k optimáln´ımu ˇreˇsen´ı, nikoli polynomi´ aln´ı odhad na ˇcasovou sloˇzitost); mnohé varianty také najdete pod jménem bariérové metody. Mimo jiné se ukázalo, ˇze tyto metody jsou pouˇzitelné i pro nˇekteré jiné problémy konvexn´ı optimalizace, pˇredevˇs´ım pro semidefinitn´ı programován´ı. Nepˇr´ım´ ym d˚ usledkem Karmakarovy práce je i to, ˇze doˇslo k vˇetˇs´ımu propojen´ı dvou vˇedeck´ ych komunit: komunity ekonom˚ u vˇenuj´ıc´ıch se line´ arn´ımu programován´ı, a komunity matematik˚ u

3 studuj´ıc´ıch nelineárn´ı optimalizaci. Na závˇer si jeˇstˇe vˇsimnˇeme nˇekter´ ych rozd´ıl˚ u mezi simplexov´ ym algoritmem, elipsoidovou metodou a metodou vnitˇrn´ıho bodu. Simplexov´ y algoritmus chod´ı po hranici mnohostˇenu, totiˇz po jeho vrcholech. Elipsoidov´ y algoritmus se (kromˇe posledn´ıho kroku) pohybuje vnˇe mnohostˇenu. Metoda vnitˇrn´ıho bodu na rozd´ıl od obou ostatn´ıch metod pracuje uvnitˇr mnohostˇenu. Svou podstatou je simplexov´ y algoritmus diskrétn´ım algoritmem, zat´ımco elipsoidová metoda i metoda vnitˇrn´ıho bodu je iteraˇcn´ım algoritmem. Pro sezn´ amen´ı se se základy teorie line´ arn´ıho programován´ı doporuˇcujeme ˇctenáˇri uˇcebn´ı text J. Matouˇska Line´ arn´ı programov´ an´ı a line´ arn´ı algebra pro informatiky [7], pˇr´ıpadnˇe rozˇs´ıˇrenou anglickou verzi [8]. Pozornosti zv´ıdavého ˇctenáˇre doporuˇcujeme dále n´ asleduj´ıc´ı v´ ysledky (a jeden problém): • Silnˇe polynomi´ aln´ı algoritmus pro line´ arn´ı programy s koeficienty 1, -1, 0 – Tardos [12]. • Silnˇe polynomi´ aln´ı algoritmus pro line´ arn´ı programy v omezené dimenzi – Megiddo [9]. • Zd˚ uvodnˇen´ı, proˇc simplexov´ y algoritmus potˇrebuje ,,vˇetˇsinou” pouze polynomi´ aln´ı ˇcas – Spielman a Teng [11]. • Hirschova (polynomi´ aln´ı) hypotéza - do optimáln´ıho vrcholu vˇzdy vede ,,krátká” cesta po hranici mnohostˇenu.

2 Elipsoidová metoda 2.1 Náˇcrt algoritmu Zad´ an´ı: Pro dan´ y mnohostˇen P = {x | Ax ≤ b} naj´ıt x ∈ P , pokud existuje, a v opaˇcném pˇr´ıpadˇe rozpoznat, ˇze P je prázdn´ y. V tomto textu pop´ıˇseme tzv. elipsoidovou metodu, coˇz je algoritmus, kter´ y dan´ y problém ˇreˇs´ı v polynomi´ aln´ım ˇcase vzhledem k velikosti zadán´ı (podrobnosti n´ıˇze). Na konci kapitoly uvedeme, jak algoritmus zobecnit pro ˇreˇsen´ı optimalizaˇcn´ı verze problému, tedy pro u ´lohu u ´lohu T max{c x | Ax ≤ b}. Pro zjednoduˇsen´ı popisu algoritmu budeme prozat´ım o mnohostˇenu P pˇredpokl´ adat: P1 P je omezen´ y (tj. cel´ y P se vejde do koule o dostateˇcnˇe velkém pr˚ umˇeru), P2 Je-li P nepr´ azdn´ y, pak je plné dimenze (tj. pro dostateˇcnˇe malé ǫ > 0 se do P vejde celá koule s pr˚ umˇerem ǫ). Hrub´ y n´ aˇ crt algoritmu: Najdeme dostateˇcnˇe velk´ y elipsoid E0 takov´ y, aby obsahoval cel´ y mnohostˇen P (pˇredpoklad P1 zaruˇcuje, ˇze takov´ y elipsoid existuje) a opakovanˇe provád´ıme následuj´ıc´ı. Pokud stˇred zk elipsoidu Ek leˇz´ı uvnitˇr P , naˇsli jsme poˇzadované ˇreˇsen´ı. V opaˇcném pˇr´ıpadˇe v´ıme, ˇze zk poruˇsuje nˇejakou nerovnost ze systému Ax ≤ b, ˇreknˇeme i-tou nerovnost aTi x ≤ bi . Vezmeme poloprostor odpov´ıdaj´ıc´ı poruˇsené nerovnosti a posuneme ho tak, aby jeho hranice procházela bodem zk ; oznaˇcme Hk tento posunut´ y poloprostor, tedy Hk = {x | aTi x ≤

6

Kapitola 2. Elipsoidová metoda

y mnohostˇen P leˇz´ı v pr˚ uniku elipsoidu Ek s poloprostoaTi zk }. Pak cel´ rem Hk . Najdeme nov´ y (menˇs´ı) elipsoid Ek+1 obsahuj´ıc´ı Ek ∩ Hk a krok opakujeme. Jak poznáme, ˇze je P prázdn´ y a ˇze m˚ uˇzeme pˇrestat s konstrukc´ı nov´ ych elipsoid˚ u? Vyuˇzijeme náˇs druh´ y pˇredpoklad P2. Je-li P nepr´ azdn´ y, je moˇzno na základˇe A a b spoˇc´ıtat doln´ı odhad na objem P . Pokud zajist´ıme, ˇze objem elipsoidu Ek+1 je vˇzdy v´ yraznˇe menˇs´ı neˇz objem elipsoidu Ek , pak po dostateˇcném poˇctu krok˚ u budeme vˇedˇet, ˇze nepr´ azdn´ y P by se jiˇz d´ıky svému objemu do elipsoidu El , pro dostateˇcnˇe velké l, neveˇsel a tud´ıˇz P mus´ı b´ yt prázdn´ y. Abychom dostateˇcnˇe popsali elipsoidovou metodu (za v´ yˇse uveden´ ych pˇredpoklad˚ u P1 a P2), potˇrebujeme zodpovˇedˇet tyto ot´ azky: 1. Jak na poˇcátku volit elipsoid E0 tak, aby P ⊆ E0 ? 2. Jak ze starého elipsoidu Ek spoˇc´ıtat nov´ y Ek+1 , neboli jak volit parametry nového, aby obklopoval, co m´ a, a pˇritom byl co do objemu podstatnˇe menˇs´ı? 3. Kolik iterac´ı je tˇreba provést k nalezen´ı x ∈ P nebo k rozpoznán´ı, ˇze P je prázdné? D´ ale bude tˇreba ukázat, jak se pˇredpoklad˚ u P1 a P2 zbavit. Neˇz se ale tˇemto ot´ azk´ am budeme vˇenovat, zavedeme a pˇripomeneme nˇekteré základn´ı potˇrebné pojmy a skuteˇcnosti.

2.2 Opakovan´ı z lineárn´ı algebry Porovnán´ı vektor˚ u (pˇr´ıpadnˇe matic) provád´ıme po sloˇzk´ ach: pro vektory n x, y ∈ R p´ıˇseme x ≤ y, pokud xi ≤ yi pro i = 1, . . . , n. Jednotkovou matici znaˇc´ıme I. Opakovanˇe budeme pracovat s vektory 0 = (0, 0, . . . , 0)T a e1 = (1, 0, . . . , 0)T . 2.2.1 Definice. Symetrickou matici A ∈ finitn´ı, jestliˇze ∀x 6= 0 plat´ı xT Ax > 0.

Rn×n nazýváme positivnˇe de-

2.2.2 Tvrzen´ı. Pro pozitivnˇe definitn´ı matici A plat´ı: • Vˇsechna vlastn´ı ˇc´ısla matice A jsou kladn´ a, • inverzn´ı matice A−1 je také pozitivnˇe definitn´ı,

2.2. Opakovan´ı z line´ arn´ı algebry

7

• existuje právˇe jedna pozitivnˇe definitn´ı matice Q taková, ˇze A = QT · Q; takovou matici Q znaˇc´ıme A1/2 . Pro nás bude d˚ uleˇzitá posledn´ı vlastnost. 2.2.3 Definice. Mnoˇzinu E(a, A) = {x ∈ Rn | (x − a)T A−1 (x − a) ≤ 1} , kde A je pozitivnˇe definitn´ı matice, budeme naz´ yvat elipsoidem se stˇredem v a a urˇcen´ ym matic´ı A. 2.2.4 Pˇ r´ıklad. E(0, I) = {x ∈ stˇredem v poˇcátku.

Rn

| xT x ≤ 1} – jednotková koule se

2.2.5 Definice. Zobrazen´ı T : Rn → Rn naz´ yv´ ame afinn´ı zobrazen´ı, pokud je dáno pˇredpisem T (x) = Qx + s, kde Q ∈ Rn×n je matice a s ∈ Rn je vektor (tj. T je sloˇzen´ım line´ arn´ıho zobrazen´ı a posunut´ı). 2.2.6 Tvrzen´ı. Kaˇzd´ y elipsoid E(a, A) je afinn´ım obrazem jednotkové koule: E(a, A) = A1/2 · E(0, I) + a .

D˚ ukaz. E(a, A) = {x ∈ Rn : (x − a)T A−1 (x − a) ≤ 1} = {x ∈ Rn | (x − a)T · A−1/2 T · A−1/2 · (x − a) ≤ 1}. Oznaˇcme y = A−1/2 · (x − a). Potom A1/2 y+a = x. Dosad´ıme-li do formule popisuj´ıc´ı elipsoid, z´ısk´ ame −1/2 (uvˇedomme si, ˇze A je také positivnˇe definitn´ı matice, tud´ıˇz je syT metrická a A−1/2 = A−1/2 ): E(a, A) = {(A1/2 y + a) ∈ Rn | yT y ≤ 1} = A1/2 · E(0, I) + a . Pro T ⊆ Rn budeme vol(T ) oznaˇcovat objem mnoˇziny T . 2.2.7 Tvrzen´ı. Pro afinn´ı zobrazen´ı T : T (x) = Qx + t a mnoˇzinu X ⊆ Rn plat´ı:

Rn

→

Rn

⊔ ⊓

dané pˇredpisem

vol(T (X)) = | det Q| · vol(X) . V pˇr´ıpadˇe elipsoid˚ u dostaneme rovnost: vol(E(a, A)) = | det(A1/2 )| · vol(E(0, I)).

8


2.2.8 Pozorov´ an´ı. Pro objem elipsoidu E(a, A) plat´ı: | det(A1/2 )| · n−n ≤ vol(E(a, A)) ≤ | det(A1/2 )| · 2n . Odhady se op´ıraj´ı o objem krychle vepsané, resp. opsané. 2.2.9 Definice. Velikost zápisu. Pro celé ˇc´ıslo k znaˇc´ıme hki = 1 + ⌈log2 (|k|+1)⌉, coˇz je poˇcet bit˚ u potˇrebn´ ych pro zápis k vˇcetnˇe znaménka. p Podobnˇe pro racion´ aln´ı ˇc´ıslo r = q , kde p a q jsou nesoudˇelná, znaˇc´ıme Pn n znaˇ Q hri = hpi + hqi. Pro racion´ aln´ı vektor v ∈ c ´ ıme hvi = i=1 hvi i a P m Pn m×n pro matici A ∈ Q obdobnˇe hAi = i=1 j=1 hai,j i. Je uˇziteˇcné uvˇedomit si, ˇze pro kaˇzdé pˇrirozené ˇc´ıslo r plat´ı nerovnost |r| ≤ 2hri−1 − 1.

2.3 Poˇcáteˇcn´ı elipsoid Zaˇcneme pˇripomenut´ım zn´ amé nerovnosti poskytuj´ıc´ı horn´ı odhad na velikost determinantu matice. 2.3.1 Lemma (Hadamardova nerovnost). Pro kaˇzdou ˇctvercovou matici C plat´ı: n Y kCi k , | det C| ≤ i=1

kde Ci oznaˇcuje i-t´ y sloupec matice C a kuk velikost vektoru u.

V d˚ ukazu hlavn´ıho v´ ysledku této kapitolky bude naˇs´ım nástrojem následuj´ıc´ı lemma. 2.3.2 Lemma. Necht’ C je celoˇc´ıselná matice n × n. Pak plat´ı 2

| det C| ≤ 2hCi−n . D˚ ukaz. 1 + | det C| ≤ 1 +

n Y i=1

kCi k ≤

n Y i=1

(1 + kCi k) ≤

n Y

2

2kCi k−n = 2hCi−n .

i=1

Vu ´pravách jsme kromˇe Hadamardovy nerovnosti pouˇzili pro velikost nsloˇzkového racion´ aln´ıho vektoru x odhad kxk ≤ 2hxi−n − 1, odvozen´ y

2.4. Iteraˇcn´ı krok: v´ ypoˇcet Ek+1 z Ek

9

takto: 1 + kxk ≤1 + n Y i=1

n X i=1

|xi | ≤

n Y i=1

hxi i−1

(1 + (2

(1 + |xi |) ≤

− 1)) ≤

n Y

(2.1)

2hxi i−1 = 2hxi−n .

i=1

⊔ ⊓

y mnohostˇen a 2.3.3 Lemma. Je-li P = {x | Cx ≤ d} ⊆ Qn omezen´ C a d jsou celoˇc´ıselné, pak vˇsechny vrcholy P jsou obsaˇzeny v kouli se √ stˇredem v poˇcátku a polomˇerem R = n · 2hC,di+n log n . D˚ ukaz. Uvaˇzme libovoln´ y vrchol v polytopu P . Z teorie mnohostˇen˚ u ′ ′ v´ıme (napˇr. [1]), ˇze pak existuje podsystém nerovnost´ı C x ≤ d (vybran´ y ze systému nerovnost´ı Cx ≤ d) takov´ y, ˇze v je jedin´ ym ˇreˇsen´ım ′ det(C ) C ′ x = d′ . Z Cramerova pravidla dost´ aváme: vi = det(Ci′ ) , kde Ci′ je matice vzniklá z C ′ nahrazen´ım i-tého sloupce vektorem d′ . Protoˇze matice C ′ je celoˇc´ıselná a regul´ arn´ı, m´ ame |det(C ′ )| ≥ 1. Pro horn´ı odhad velikosti vi uˇzijeme následuj´ıc´ı horn´ı odhad velikosti determinantu. K yv´ a dokonˇcen´ı d˚ ukazu Lemmatu 2.3.3 si vˇsimneme, ˇze hCi′ i ≤ hC, di. Zb´ hC,di+n log n upoˇc´ıtatqdélku vektoru o vˇsech sloˇzk´ ach velikosti nejv´ yˇse 2 : Pn √ hC,di+n log n )2 = kvk ≤ n · 2hC,di+n log n , coˇz je hledan´ y poi=1 (2 lomˇer R. ⊔ ⊓ Jako poˇcáteˇcn´ı elipsoid E1 pouˇzijeme tedy kouli E(, R · I).

2.4 Iteraˇcn´ı krok: v´ ypoˇcet Ek+1 z Ek Snadn´ y pˇ r´ıpad: Ek = E(0, I) a Hk = {x | x1 ≤ 0}. V této ˇcásti pˇredpokl´ ad´ ame, ˇze Ek = E(0, I) a Hk = {x | x1 ≤ 0}. Pro zjednoduˇsen´ı zápisu (uˇsetˇren´ı index˚ u) budeme pouˇz´ıvat znaˇcen´ı B m´ısto Ek (jedn´ a se o jednotkovou kouli kolem poˇcátku) a H m´ısto Hk . M´ ame tedy B = n T n T {x ∈ R | x x ≤ 1}, H = {x ∈ R | e1 x ≤ 0} a oznaˇcme B − = B ∩ H ,,zápornou” polovinu jednotkové koule se stˇredem v poˇcátku, to jest B − = {x ∈ Rn |xT x ≤ 1, x1 ≤ 0}. Hled´ ame elipsoid E ′ obsahuj´ıc´ı B − , kter´ y bude ,,mal´ y”. Pˇresnˇeji, chceme, aby vol(E ′ ) ≤ q · vol(E) pro nˇejakou konstantu q < 1. Protoˇze mnoˇzina

10


B

B−

E′

Obrázek 2.1: Hledané E ′ . B − je symetrická kolem osy x1 , budeme hledat E ′ ve tvaru E ′ = {x ∈ Rn |(x − z)T Z −1 (x − z) ≤ 1},

kde z = t · e1 pro t ∈ R− a Z je diagon´ aln´ı matice. Vezmˇeme 0 < p < 1 a d > 1 a diagon´ aln´ı matici Z takovou, ˇze 1  p2

Z −1

   =  

1 d2

1 d2

..

. 1 d2

    .  

Pak elipsoid E ′ bude ve smˇeru prvn´ı souˇradnice smrˇstˇen´ y (ve srovnán´ı s koul´ı o stejném poˇcátku) a ve smˇeru vˇsech ostatn´ıch souˇradnic roztaˇzen´ y. Chceme, aby se tento náˇs nov´ y elipsoid E ′ toho p˚ uvodn´ıho E = B dot´ ykal v bodech −e1 a e2 (viz obr. 2.1) a ze vˇsech takov´ ych chceme ten s nejmenˇs´ım objemem. Z prvn´ı podm´ınky na dotek dost´ aváme následuj´ıc´ı omezen´ı: 

a tedy:

  T  (−1 − t)e1   

1 p2

1 d2

1 d2

 ..

. 1 d2

(1 + t)2 =1. p2

    (−1 − t)e1 = 1  


11

Ze druhé podm´ınky na dotek dost´ aváme: 1

p2

1 d2

   (−t, 1, 0, ..., 0)   

1 d2

..

. 1 d2

  −t  1     0    = 1 ,   ..   .  0

tedy t2 1 + =1. p2 d 2 Z v´ yˇse uveden´ ych v´ yraz˚ u vyj´ adˇr´ıme 1/p2 a 1/d2 jako funkce promˇenné t: 1 1 1 + 2t 1 = , = . p2 (1 + t)2 d2 (1 + t)2 Nyn´ı m´ ame dvˇe podm´ınky na tˇri promˇenné. Tˇret´ı podm´ınku z´ısk´ ame ′ z poˇzadavku na minimáln´ y podle Tvrpı objem elipsoidu E , pro kter´ ′ zen´ı 2.2.7 plat´ı vol(E ) = | det(Z)|vol(B), coˇz je rovno ′

vol(E ) = pd

n−1

(1 + t)n

vol(B) . vol(B) = p (1 + 2t)n−1

Snadno ovˇeˇr´ıme, ˇze vol(E ′ ) jako funkce promˇenné t nab´ yv´ a svého minima pro −1 . t= n+1 Dosazen´ım za p, d a t dost´ aváme, ˇze hledan´ y elipsoid E ′ je tvaru 1 1 ′ 2 T E = x ∈ R | (x + e1 ) D(x + e1 ) ≤ 1 , n+1 n+1 kde

(n+1)2 2  n



 D=  

0

0

n2 −1 n2

0 0

0 0

... ... .. . ...



0  0   .  0 

n2 −1 n2

Pro kontrolu ovˇeˇr´ıme, ˇze elipsoid E ′ vskutku obsahuje celou ,,zápornou polovinu”koule B, tedy ˇze B − ⊆ E ′ . V´ıme, ˇze pro x ∈ B −

12


plat´ı xT x ≤ 1, x1 ≤ 0. Rozeps´ an´ım podm´ınky v zápisu E ′ dostaneme 2 n n −1 X 2 n+1 2 1 2 ) + (x1 + xi ≤ 1 . n 1+n n2 i=2

Podle pˇredpoklad˚ u

Pn

2 i=1 xi

n2 − 1 n2

≤ 1 a proto také

X n

x2i

i=2

n2 − 1 ≤ (1 − x21 ) . 2 n

Lev´ a stranˇe nápadnˇe pˇripom´ın´ a omezen´ı v zápisu elipsoidu E ′ . Vˇsimneme si dále, ˇze 2 n+1 2 2 n+1 1 1 n+1 2 = x1 + 2 2 x1 + 2 . x1 + n n+1 n n n Posledn´ı dvˇe nerovnosti (resp. nerovnost a rovnost) seˇcteme. S uˇzit´ım x21 + x1 ≤ 0 pro −1 ≤ x1 ≤ 0 dostaneme k´ yˇzené (x +

1 1 e1 )T Z −1 (x + e1 ) T ≤ 1 . n+1 n+1

Zb´ yv´ a ukázat, ˇze nov´ y elipsoid bude m´ıt objem v´ yraznˇe menˇs´ı, neˇz elipsoid p˚ uvodn´ı. 2.4.1 Lemma.

−1 vol(E ′ ) ≤ e 2(n+1) . vol(B) √ D˚ ukaz. Pˇripomeˇ nme, ˇze vol(E ′ ) = det Z · vol(B). Proto s s n−1 ′ n2 n2 vol(E ) √ = det Z = · vol(B) (n + 1)2 n2 − 1 n−1 2 n−1 1 n n2 1 2 · ) · (1 + ) = = (1 − n+1 n2 − 1 n+1 n2 − 1

≤e

1 + n−1 · − n+1 2

1 n2 −1

=e

1 1 − n+1 + 2(n+1)

−1

= e 2(n+1) .

Pro poˇr´ adek dodejme, ˇze ve v´ ypoˇctu jsme pouˇzili odhad 1 + x ≤ ex . ⊓ ⊔ Obecn´ y pˇ r´ıpad. Pˇripomeˇ nme si situaci. Je dán elipsoid E se stˇredem v a urˇcen´ y pozitivnˇe definitn´ı matic´ı A. D´ ale je dán poloprostor H


E

T −1

13

R−1 z

E′

T

R

a f c

Obrázek 2.2: Obrázek demonstruje, jaká zobrazen´ı pouˇzijeme. s normálov´ ym vektorem c, jehoˇz hranice procház´ı stˇredem a elipsoidu E; poloprostor H odpov´ıd´ a poruˇsené nerovnosti. V´ıme, ˇze vˇsechna pˇr´ıpustn´ a 1/2 ˇreˇsen´ı se vyskytuj´ı v poloprostoru H. Oznaˇcme Q = A . Formálnˇe tedy: E = E(a, A) = {x ∈ Rn | (x − a)T A−1 (x − a) ≤ 1} = Q · E(0, I) + a , H = {x ∈ Rn | cT x ≤ cT a} = {x ∈ Rn | cT (x − a) ≤ 0} .

Hled´ ame elipsoid E ′ = E(f, C) ⊇ E ∩ H s co nejmenˇs´ım objemem. Znovu vyuˇzijeme skuteˇcnosti, ˇze kaˇzd´ y elipsoid je afinn´ım obrazem jednotkové koule. Pro dan´ y elipsoid E = E(a, A) oznaˇcme T afinn´ı zobrazen´ı, které jednotkovou kouli se stˇredem v poˇcátku zobraz´ı na E; s pomoc´ı T −1 zobraz´ıme naopak náˇs elipsoid E na jednotkovou kouli. Toto zobrazen´ı T −1 aplikujeme také na poloprostor H = {x | cT (x − a) ≤ 0}. Vˇsimnˇeme si, ˇze poloprostor T −1 (H) typicky nebude totoˇzn´ y s poloprostorem H0 = {x ∈ Rn | x1 ≤ 0}, ale pro vhodnou rotaci R kolem poˇcátku jistˇe T −1 (H) = R(H0 ). Abychom mohli pouˇz´ıt v´ ysledek z −1 −1 pˇredeˇslé sekce, zobraz´ıme poloprostor T (H) pomoc´ı R na H0 (viz obr. 2.2). Pak jistˇe R−1 (T −1 (E)) ∩ R−1 (T −1 (H)) ⊆ E(

−1 e1 , Z) , n+1

(2.2)

−1 e1 , Z))) obsahuje E ∩ H. Chceme proto a tud´ıˇz elipsoid T (R(E( n+1 spoˇc´ıtat zobrazen´ı T a R. V dalˇs´ıch v´ ypoˇctech vyuˇzijeme o zobrazen´ı T následuj´ıc´ı vlastnosti:

• T (y) = Q · y + a • T −1 (x) = Q−1 · (x − a)

14

Kapitola 2. Elipsoidová metoda • T −1 (H) = {T −1 (x) | cT (x − a) ≤ 0} = {y ∈ Rn | cT (T (y) − a) ≤ 0} = {y | cT Qy ≤ 0} = {y | (Qc)T y ≤ 0}.

Po rotaci R vyˇzadujeme jedinou vlastnost, totiˇz R

−1

Qc kQck

= e1 .

(2.3)

Vˇsimnˇeme si, ˇze v R2 je rotace R urˇcena jednoznaˇcnˇe, ale v prostorech vyˇsˇs´ıch dimenz´ı uˇz nikoli (coˇz nám ovˇsem nevad´ı, jak za chv´ıli uvid´ıme). Nyn´ı pouˇzijeme sloˇzen´ı zobrazen´ı T a R k pops´ an´ı E ′ (pro jednoduchost poˇz´ıv´ ame R pro oznaˇcen´ı zobrazen´ı i oznaˇcen´ı matice totoho zobrazen´ı). Pˇripomeˇ nme si jeˇstˇe z line´ arn´ı algebry, ˇze pro matici R rotace T plat´ı RR = I. 2.4.2 Vˇ eta. Pro elipsoid E ′ = E(f, C) se stˇredem v f a urˇceném matic´ı C, kde 1 Ac √ , n + 1 cT Ac n2 2 AccT AT C= 2 · (A − ), n −1 n + 1 cT Ac f=a−

plat´ı: E(a, A) ∩ {x | cT (x − a) ≤ 0} ⊆ E(f, C) ,

(2.4)

−1 vol(E(f, C)) ≤ e 2(n+1) . vol(E(a, A))

(2.5)

D˚ ukaz. Nejprve urˇc´ıme stˇred f elipsoidu E ′ , pomoc´ı zobrazen´ı R a T : f = T (R(z)) = T

Qc −1 · n + 1 kQck

=a−

Ac 1 √ . n + 1 cT Ac

Pˇred urˇcen´ım C provedeme pomocn´ y v´ ypoˇcet. x − f = x − T (R(z)) = x − a − QRz = QR(R−1 Q−1 (x − a) − z).

2.5. Kdy skonˇcit

15

Nyn´ı opˇet vyuˇzijime vlastnosti T a R, a pomocn´ y v´ ypoˇcet: E(f, C) ={T (Ry) | (y − z)T Z −1 (y − z) ≤ 1}

={x | (R−1 T −1 (x) − z)T Z −1 (R−1 T −1 (x) − z) ≤ 1}

={x | (R−1 Q−1 (x − a) − z)T Z −1 (R−1 Q−1 (x − a) − z) ≤ 1}

={x | R−1 Q−1 (x − f))T Z −1 (R−1 Q−1 (x − f)) ≤ 1} T

T

={x | (x − f)T Q−1 R−1 Z −1 R−1 Q−1 (x − f) ≤ 1}

={x | (x − f)T C −1 (x − f) ≤ 1} , neboli

C = (QRZ 1/2 )(QRZ 1/2 )T . S vyuˇzit´ım pˇredeˇslého v´ ypoˇctu a znalosti Z = diag vyj´ adˇr´ıme matici C pomoc´ı matice A a vektoru a. C =Q · R · Z · RT · QT n2 = 2 n −1 n2 = 2 n −1 n2 = 2 n −1 n2 = 2 n −1

n2 n2 , , ... 2 2 (n+1) n −1

n−1 · Q · R · diag , 1, . . . , 1 · RT · QT n+1 2 · (QRIRT QT − · QRe1 eT1 RT QT ) n+1 cT AT 2 Ac √ √ · ) · (A − · n+1 cT Ac cT Ac 2 AccT AT · (A − ). n + 1 cT Ac

Poznamenejme jeˇstˇe, ˇze C je jistˇe symetrická a pozitivnˇe definitn´ı matice. Vlastnost (2.4) i (2.5) plyne ze vztahu (2.2), tedy je pˇr´ım´ ym d˚ usledkem v´ ypoˇct˚ u proveden´ ych v pˇredeˇslé kapitolce. ⊔ ⊓

2.5 Kdy skonˇcit 2.5.1 Lemma. Je-li P = {x | Cx ≤ d} polytop plné dimenze a C a d jsou celoˇc´ıselné, pak 3

vol(P ) ≥ 2−(n+1)hCi+n . D˚ ukaz. Pro jednoduchost zde dokáˇzeme pouze slabˇs´ı odhad; pro náˇs hlavn´ı c´ıl – ukázat, ˇze existuje polynomi´ aln´ı algoritmus pro hledán´ı pˇr´ıpustného ˇreˇsen´ı – to nehraje ˇzádnou roli.

16


Protoˇze polytop P je plné dimenze, m´ a n + 1 afinnˇe nez´ avisl´ ych vrchol˚ u v0 , v1 , . . . , vn a plat´ı: vol(conv(v0 , . . . , vn )) ≤ vol(P ) , kde conv(· · · ) oznaˇcuje konvexn´ı obal dané mnoˇziny vrchol˚ u. Oznaˇcme ei vektor s jedinou nenulovou sloˇzkou, totiˇz i-tou, kter´ a je rovna jedné, pro i = 1, . . . , n. Pak conv(v0 , . . . , vn ) = T (conv(0, e1 , . . . , en )) , kde T znaˇc´ı afinn´ı zobrazen´ı T (x) = v0 + (v1 − v0 , . . . , vn − v0 ) x. V dalˇs´ım opˇet vyuˇzijeme toho, ˇze kaˇzd´ y vrchol mnohostˇenu P je ˇreˇsen´ım vhodné soustavy rovnic odvozené z Cx ≤ d: pro kaˇzdé vi existuje podsystém Ci x ≤ di systému Cx ≤ d takov´ y, ˇze vi je jedin´ ym det Ci,j ˇreˇsen´ım soustavy Ci x = di . Podle Cramerova pravidla vi,j = det Ci , kde Ci,j je matice vzniklá z Ci nahrazen´ım j-tého sloupce vektorem di . S uˇzit´ım Tvrzen´ı 2.2.7, rovnosti vol(conv(0, e1 , . . . , en ) = 1/n! pro objem simplexu daného vektory 0, e1 , . . . , en , a vˇety o rozvoji determinantu dost´ aváme, pˇri znaˇcen´ı ui = det Ci · vi , následuj´ıc´ı odhad: 1 1 1 . . . 1 vol(conv(v0 , . . . , vn )) = det v0 v1 . . . vn n! det C det C . . . det C 0 0 0 det u0 u1 ... un 1 = · n! | det C0 · det C1 · ... · det Cn | (n+1) 1 1 ≥ · 2 hCi+n log n n! ≥2−n log n · 2−(n+1)·hCi−n(n+1) log n . U pˇredposledn´ı nerovnosti jsme vyuˇzili skuteˇcnosti, ˇze se jedn´ a o determinant celoˇc´ıselné matice, o které z pˇredpoklad˚ u (afinn´ı nez´ avislosti vrchol˚ u v0 , v1 , . . . , vn ) v´ıme, ˇze je regul´ arn´ı, a tud´ıˇz jej´ı determinant je alespoˇ n jedna. ⊔ ⊓ 2.5.2 Vˇ eta. Je-li P nepr´ azdn´ y plnodimenzion´ aln´ı polytop, pak algoritmus popsan´ y v této kapitole nejpozdˇeji do k = 2 · (n + 1) · (2(n + 1)hCi + 3 n · hdi − n ) iterac´ı nalezne x ∈ P . √ D˚ ukaz. Zaˇcneme jednoduch´ ym odhadem vol(E0 ) ≤ (2r)n , kde r = n · 2hC|di+n log n .

2.6. Jak se zbavit zjednoduˇsuj´ıc´ıch pˇredpoklad˚ u

17

Nyn´ı pˇredpokl´ adejme, ˇze algoritmus provedl k iterac´ı. Pak s pouˇzit´ım uvedeného odhadu a Lemmatu 2.4.1 dost´ aváme vol(Ek ) < vol(P ), coˇz je spor s invariantem algoritmu, ˇze cel´ y mnohostˇen P je vˇzdy plnˇe obsaˇzen v elipsoidu Ek . ⊔ ⊓ 2.5.3 D˚ usledek. Pokud algoritmus do k iterac´ı nenajde x ∈ P , pak je P prázdn´ y.

2.6 Jak se zbavit zjednoduˇsuj´ıc´ıch pˇredpoklad˚ u Omezenost. Bez u ´jmy na obecnosti m˚ uˇzeme pˇredpokl´ adat, ˇze matice A v popisu mnohostˇenu P = {x | Ax ≤ b} je plné sloupcové hodnosti; v opaˇcném pˇr´ıpadˇe lze snadno pˇrej´ıt do niˇzˇs´ı dimenze. Pˇripomeˇ nme, ˇze ′ ′ kaˇzd´ a minimáln´ı stˇena P lze popsat jako mnoˇzina {x | A x = b }, kde A′ je matice téˇze hodnosti jako A, vzniklá z A v´ ybˇerem vhodn´ ych ˇr´ adk˚ u, a ′ b je vektor odpov´ıdaj´ıc´ıch sloˇzek b. M´ a-li A plnou sloupcovou hodnost, je nutnˇe kaˇzd´ a minimáln´ı stˇena mnohostˇenu P vrcholem. Tud´ıˇz, je-li P nepr´ azdn´ y, obsahuje vrchol. D´ ale uˇz v´ıme, ˇze je-li v libovoln´ y vrchol P , pak pro jeho i-tou hA,bi+n log n souˇradnici vi plat´ı |vi | ≤ 2 . Pokud tedy P nˇejaké vrcholy m´ a, jejich konvexn´ı obal se jistˇe vejde do koule se stˇredem v poˇcátku √ a pr˚ umˇerem R = n · 2hC,di+n log n . Algoritmus bude po celou dobu svého bˇehu zachovávat invariant, ˇze konvexn´ı obal vrchol˚ u P leˇz´ı uvnitˇr aktuáln´ıho elipsoidu, coˇz zaruˇcuje spr´ avné chován´ı algoritmu i pro tento pˇr´ıpad. Pln´ a dimenze. 2.6.1 Lemma. Necht’ A je celoˇc´ıselná matice a b celoˇc´ıseln´ y vektor. Pak systém Ax ≤ b m´ a ˇreˇsen´ı právˇe kdyˇz systém Ax ≤ b + 1 · ε m´ a ˇreˇsen´ı 1 pro ε = . hA,bi−n2 2m2

D˚ ukaz. Implikace zleva doprava je trivi´ aln´ı. Pro opaˇcnou pouˇzijeme Farkasovo lemma a ukáˇzame, ˇze y z Farkasova lemmatu pro p˚ uvodn´ı u ´lohu funguje i pro odvozenou. Podrobnosti pˇrenecháme tentokráte ˇctenáˇri. ⊓ ⊔ Hled´ an´ı optim´ aln´ıho ˇ reˇ sen´ı. 2.6.2 Lemma. Pˇredpokl´ adejme, ˇze u ´loha ,,rozhodni, zda je mnohostˇen P je prázdn´ y ˇci nepr´ azn´ y”je ˇreˇsiteln´ a v polynomi´ aln´ım ˇcase. Pak

18


i u ´loha ,,nalezni x ∈ P , nebo poznej, ˇze P je prázdné”, je ˇreˇsiteln´ a v polynomi´ aln´ım ˇcase. D˚ ukaz. Uvˇedomme si, ˇze ˇreˇsen´ı u ´lohy s uvolnˇenou pravou stranou (viz Lemma 2.6.1) nemus´ı b´ yt ˇreˇsen´ım p˚ uvodn´ı u ´lohy (coˇz je ta, kter´ a nás opravdu zaj´ımá). Pˇredeslé lemma nás ale ujiˇst’uje, ˇze m´ a-li ˇreˇsen´ı uvolnˇen´ a soustava, m´ a ˇreˇsen´ı (ne nutnˇe stejné) i u ´loha p˚ uvodn´ı. Jde o to, jak tuto znalost vyuˇz´ıt k tomu, abychom ˇreˇsen´ı skuteˇcnˇe nalezli. Idea je následuj´ıc´ı: sniˇzovat poˇcet nerovnost´ı v p˚ uvodn´ı soustavˇe tak dlouho, aˇz nám zbydou pouze rovnosti. Jak to provést? Nab´ız´ı se dva zp˚ usoby: ub´ır´ an´ı nadbyteˇcn´ ych nerovnost´ı a pˇremˇena ostatn´ıch na rovnice. Systém tvoˇren´ y pouze rovnicemi vyˇreˇs´ıme napˇr. Gaussovou eliminac´ı. Popiˇsme si postup trochu pˇresnˇeji: Pˇredpokl´ adejme, ˇze naˇse soustava Ax ≤ b obsahuje k nerovnost´ı (a jedno kolik rovnost´ı – dvˇe opaˇcné nerovnosti poˇc´ıt´ ame jako jednu rovnost). Vezmeme libovolnou nerovnost, nahrad´ıme ji rovnost´ı a otestujeme, zda nová soustava m´ a ˇreˇsen´ı (pomoc´ı pˇredeˇslého lemmatu). M´ a-li nová soustava ˇreˇsen´ı, ubyla nám jedna nerovnost a soustava m´ a i nad´ ale nˇejaké ˇreˇsen´ı. Nem´ a-li nová soustava ˇreˇsen´ı, pak vybran´ a nerovnost neodpov´ıd´ a ˇzádné stˇenˇe mnohostˇenu a m˚ uˇzeme ji proto vynechat jako nadbyteˇcnou. ⊔ ⊓ 2.6.3 Lemma. Je-li u ´loha ,,nalezni x ∈ P , nebo poznej, ˇze P je prázdné” ˇreˇsiteln´ a v polynomi´ aln´ım ˇcase, pak je i optimalizaˇcn´ı verze u ´lohy ˇreˇsiteln´ a v polynomi´ aln´ım ˇcase. ´ D˚ ukaz. Ulohu max{cT x | Ax ≤ b} vyˇreˇs´ıme pomoc´ı algoritmu pro u ´lohu ,,nalezni x ∈ P , nebo poznej, ˇze P je prázdné”. Ze silné duality v´ıme, ˇze max{cT x | Ax ≤ b} = min{yT b | yT A = cT , y ≥ 0}, jsou-li obˇe mnoˇziny nepr´ azdné. Postupovat tedy budeme takto: 1. Otestuj zda {x ∈ neexistuje.

Rn

| Ax ≤ b} = ∅. Pokud ano, pak ˇreˇsen´ı

2. Uvaˇz P ′ = {(x, y) ∈ Rn+m | Ax ≤ b, y ≥ 0, yT A ≤ cT , −yT A ≤ −cT , cT x ≤ yT b, −cT x ≤ −yT b}. Pokud P ′ = ∅, pak P je neomezen´ y a maximum c´ılové funkce je libovolnˇe velké. Pokud P ′ nen´ı prázdn´ y, pak existuje x0 , y0 ∈ P ′ , pˇriˇcemˇz snadno vid´ıme, ˇze x0 je pˇr´ıpustné ˇreˇsen´ı primárn´ı u ´lohy, y0 je pˇr´ıpustné ˇreˇsen´ı duáln´ı u ´lohy a silná dualita nás ujiˇst’uje, ˇze obˇe jsou optimáln´ı.

2.7. Shrnut´ı

19 ⊔ ⊓

Nepˇ r´ıjemnost s odmocninami. V uvedené anal´ yze algoritmu pom´ıj´ıme skuteˇcnost, ˇze algoritmus ve zde popsané podobˇe pracuje s odmocninami, a tedy pˇr´ıpadnˇe s iracionáln´ımi ˇc´ısly. Tomuto problému je moˇzno se vyhnout vhodn´ ym zaokrouhlován´ım, kterému uˇz se v tomto textu vˇenovat nebudeme. Zv´ıdavého ˇctenáˇre odkazujeme na klasickou monografii [6].

2.7 Shrnut´ı Odhlédneme-li od problém˚ u s odmocninami, dokázali jsme následuj´ıc´ı vˇetu. 2.7.1 Vˇ eta (Chaˇ cijan, 1979). Existuje polynomi´ aln´ı algoritmus pro ˇreˇsen´ı u ´lohy line´ arn´ıho programován´ı.

3 Metoda vnitˇrn´ıho bodu 3.1 Náˇcrt algoritmu V tomto textu budeme uvaˇzovat u ´lohu line´ arn´ıho programován´ı v rovnicovém (téˇz naz´ yvaném standardn´ı) tvaru: min cT x

(3.1)

Ax = b x ≥ 0,

kde A je reálná matice m × n, b ∈ Rm , c ∈ budeme pracovat s duáln´ı u ´lohou ve tvaru max yT b

Rn

a x ∈

Rn. Zároveˇn (3.2)

AT y + s = c s ≥ 0,

yv´ ame pˇr´ıdavné. Bez u ´jmy kde y ∈ Rm a s ∈ Rn ; promˇenné si naz´ na obecenosti budeme pˇredpokl´ adat, ˇze matice A m´ a plnou ˇr´ adkovou hodnost. Vˇsimnˇeme si, ˇze pak ˇreˇsen´ı (y, s) duáln´ı u ´lohy je moˇzno jednoznaˇcnˇe reprezentovat pomoc´ı vektoru s pˇr´ıdavn´ ych promˇenn´ ych (z nˇehoˇz ˇ lze y dopoˇc´ıtat, napˇr. Gaussovou eliminac´ı). Rekneme, ˇze x je striknˇe pˇr´ıpustné ˇreˇsen´ı, pokud x > 0 a x je pˇr´ıpustné ˇreˇsen´ı; obdobnˇe pro s. V tomto textu se budeme vˇenovat problému nalezen´ı optim´ aln´ıho ˇreˇsen´ı primárn´ı u ´lohy. Jádrem metody je postup, kter´ y z libovolného striknˇe pˇr´ıpustného ˇreˇsen´ı primárn´ı u ´lohy spoˇc´ıt´ a v polynomi´ aln´ım ˇcase (skoro) optimáln´ı

22

Kapitola 3. Metoda vnitˇrn´ıho bodu

ˇreˇsen´ı. To se na prvn´ı pohled nezdá pˇr´ıliˇs uspokojivé: v´ıme, ˇze uˇz samotné nalezen´ı nˇejakého pˇr´ıpustného ˇreˇsen´ı u ´lohy line´ arn´ıho programován´ı je ,,stejnˇe” obt´ıˇzné jako nalezen´ı optimáln´ıho ˇreˇsen´ı této u ´lohy. Trik umoˇzn ˇuj´ıc´ı zaˇc´ınat rovnou se striknˇe pˇr´ıpustn´ ym ˇreˇsen´ım, aniˇz bychom ˇreˇsili nˇejak´ y line´ arn´ı program, spoˇc´ıv´ a v drobné u ´pravˇe u ´lohy line´ arn´ıho programován´ı (pˇrid´ an´ı dvou promˇenn´ ych a drobn´ a u ´prava soustavy); v upravené u ´loze je moˇzné striktnˇe pˇr´ıpustné ˇreˇsen´ı z´ıskat zadarmo, pˇriˇcemˇz optimáln´ı ˇreˇsen´ı upravené u ´lohy pˇr´ımo dává optimáln´ı ˇreˇsen´ı u ´lohy p˚ uvodn´ı. Podobnˇe jako elipsoidová metoda je i metoda vnitˇrn´ıho bodu iteraˇcn´ı metoda. U elipsoidové metody jsme konstruovali posloupnost bod˚ u (stˇredy elipsoid˚ u), která zaˇc´ınala typicky nˇekde vnˇe zadaného mnohostˇenu P a pokud byl P nepr´ azdn´ y, konˇcila nˇekde uvnitˇr P . V metodˇe vnitˇrn´ıho bodu budeme také konstruovat posloupnost bod˚ u, kter´ a ovˇsem zaˇc´ın´ a nˇekde uvnitˇr zadaného mnohostˇenu P , v mnohostˇenu P celou dobu z˚ ustává a konˇc´ı v (témeˇr) optimáln´ım ˇreˇsen´ı; jedn´ a se tedy o posloupnost pˇr´ıpustných ˇreˇsen´ı primárn´ı u ´lohy. V podobˇe popsané v tomto textu jde o primárnˇe-duáln´ı algoritmus, tedy o algoritmus, kter´ y pracuje zároveˇ n s ˇreˇsen´ımi primárn´ı i duáln´ı u ´lohy; spoleˇcnˇe s posloupnost´ı ˇreˇsen´ı primárn´ı u ´lohy budeme konstruovat jeˇstˇe druhou posloupnost bod˚ u reprezentuj´ıc´ıch ˇreˇsen´ı duáln´ı u ´lohy. Kl´ıˇcov´ ym nástrojem metody je potenci´ al a zde popsan´ a varianta algoritmu patˇr´ı mezi metody sniˇzov´ an´ı potenci´ alu. Pro dvojici (x, s) striknˇe pˇr´ıpust´ ych ˇreˇsen´ı primárn´ı a duáln´ı u ´lohy definujeme potenciál jako ˇc´ıslo G(x, s) =(n +

√

T

n) ln(x s) −

n X

ln(xi si ) .

(3.3)

i=1

Potenciál nám poslouˇz´ı dvoj´ım zp˚ usobem. Jednak bude uˇziteˇcn´ y pro kontrolu doby bˇehu algoritmu (napˇr. podle nˇej poznáme, kdy uˇz m˚ uˇzeme skonˇcit), a jednak bude ˇr´ıdit volbu dalˇs´ıch bod˚ u v obou konstruovan´ ych posloupnostech. Obdobnou roli hrály v elipsoidové metodˇe elipsoidy: jejich objem nám slouˇzil jako poˇc´ıtadlo, hl´ıdaj´ıc´ı dobu bˇehu algoritmu, a elipsoidy samotné se pouˇz´ıvaly ke konstrukci dalˇs´ıch bod˚ u posloupnosti. Záhy nahlédneme, ˇze pro pˇribliˇzován´ı se k optimáln´ı dvojici ˇreˇsen´ı ¯ a ¯s jsou aktuáln´ı body konpotˇrebujeme potenciál sniˇzovat. Necht’ x struovan´ ych posloupnost´ı. Základn´ı myˇslenkou metody je spoˇc´ıtat gradient g potenciálu G(x, s) vzhledem k vektoru promˇenn´ ych x v m´ıstˇe (¯ x, ¯s) a vydat se v posloupnosti ˇreˇsen´ı primárn´ı u ´lohy smˇerem −g, ne¯ − αg pro nˇejaké vhodné α > 0. boli za dalˇs´ı bod posloupnosti vz´ıt x

3.2. Základn´ı definice a pozorován´ı

23

Takto jednoduˇsˇse to ovˇsem nep˚ ujde, protoˇze bychom vˇetˇsinou poruˇsili omezuj´ıc´ı podm´ınky Ax = b primárn´ı u ´lohy. Proto nep˚ ujdeme pˇr´ımo ve smˇeru −g, ale ve smˇeru daném projekc´ı vektoru −g do nadroviny Ax = 0. T´ım se vyhneme problému s omezuj´ıc´ımi podm´ınkami, ale m˚ uˇze se nám stát, ˇze tato projekce bude pˇr´ıliˇs mal´ a, v d˚ usledku ˇcehoˇz by krok˚ u potˇrebn´ ych k dosaˇzen´ı optima bylo potˇreba nepˇrijatelnˇe mnoho (pokud bychom ho v˚ ubec kdy dos´ ahli). Z tohoto d˚ uvodu provedeme v pˇr´ıpadˇe, ˇze projekce g do nadroviny Ax = 0 je mal´ a, tzv. du´ aln´ı krok a m´ısto zmˇeny ˇreˇsen´ı primárn´ı u ´lohy zmˇen´ıme ˇreˇsen´ı duáln´ı u ´lohy. N´ apovˇedu ke zmˇenˇe duáln´ıho ˇreˇsen´ı nám opˇet poskytne potenciál, nebo pˇresnˇeji gradient potenciálu G(x, s) vzhledem k s v m´ıstˇe (¯ x, ¯s). Ukáˇzeme, ˇze v pˇr´ıpadˇe primárn´ıho i duáln´ıho kroku dojde k v´ yraznému sn´ıˇzen´ı potenciálu, coˇz bude staˇcit k polynomi´ aln´ımu odhadu na ˇcas bˇehu algoritmu. Na konci tohoto hrubého náˇcrtu metody zmiˇ nme jeˇste jeden kl´ıˇcov´ y nástroj metody, totiˇz afinn´ı transformaci. Metoda potˇrebuje, aby vˇsechna ˇreˇsen´ı, která postupnˇe konstruuje, byla striktnˇe pˇr´ıpustn´ a. To p˚ usob´ı jist´ a omezen´ı v moˇznostech, kter´ ym smˇerem a jak daleko se vydat pˇri v´ ypoˇctu dalˇs´ıho bodu posloupnosti ˇreˇsen´ı. Abychom se tˇemto omezen´ım vyhnuli, pouˇzijeme na zaˇcátku kaˇzdé iterace afinn´ı transformaci, kter´ a ′ T posledn´ı bod primárn´ı posloupnosti zobraz´ı na bod x = (1, 1, . . . , 1) . V tomto transformovaném prostoru spoˇc´ıt´ ame iteraˇcn´ı krok zp˚ usobem naˇcrtnut´ ym v´ yˇse a inverzn´ı transformac´ı se vrát´ıme do p˚ uvodn´ıho prostoru. Uvid´ıme, ˇze pokles potenciálu v p˚ uvodn´ım prostoru bude stejnˇe velk´ y jako pokles potenciálu v transformovaném prostoru. Pouˇzitá afinn´ı transformace nám také podstatn´ ym zp˚ usobem zjednoduˇsˇs´ı práci s gradientem g a jeho projekc´ı do Ax = 0.

3.2 Základn´ı definice a pozorován´ı 3.2.1 Lemma. Necht’ x je pˇr´ıpustné ˇreˇsen´ı primárn´ı u ´lohy a s je pˇr´ıpustné ˇreˇsen´ı duáln´ı u ´lohy. Pak plat´ı c T x − y T b = sT x . D˚ ukaz. cT x − yT b = yT Ax + sT x − yT Ax = sT x .

(3.4) ⊔ ⊓

Pˇripomeˇ nme, ˇze potenci´ al dvojice (x, s) primárn´ıho a duáln´ıho ˇreˇsen´ı

24


definujeme jako G(x, s) = (n +

√

T

n) ln(x s) −

n X

ln(xi si ) .

(3.5)

i=1

Vˇsimnˇeme si, ˇze pro dvojici (x, s) bl´ızkou optimáln´ı dvojici ˇreˇsen´ı se podle pˇredeˇslého lemmatu prvn´ı ˇclen pravé strany rychle bl´ıˇz´ı k −∞; abychom se pˇribl´ıˇzili k optimáln´ımu ˇreˇsen´ı, bude proto tˇreba potenciál minimalizovat. Pokud se snaˇz´ıme o minimalizaci potenci´ alu, pak suma Pn z´ı jako bariéra kolem hranic xi ≥ 0 a i=1 ln(xi si ) v jeho definici slouˇ si ≥ 0: pokud se nˇekterá sloˇzka x nebo s bl´ıˇz´ı k nule, zp˚ usob´ı odeˇcten´ı této sumy v´ yrazn´ y nár˚ ust potenciálu. Pro poˇr´ adek upozorˇ nujeme, ˇze pro potenciál se v jin´ ych variantách metody Pn vnitˇrn´ıho bodu pouˇz´ıvaj´ı i jiné √ T funkce (napˇr. (n + n) ln(x s) − i=1 ln xi ). V následuj´ıc´ım textu bu√ deme pro zkr´ acen´ı zápisu pouˇz´ıvat znaˇcen´ı q = n + n. Pro velikost zápisu u ´lohy line´ arn´ıho programován´ı pouˇz´ıv´ ame oznaˇcen´ı L. N´ asleduj´ıc´ı vˇeta a jej´ı d˚ usledek budou d˚ uleˇzité pˇri rozhodován´ı o ukonˇcen´ı algoritmu. 3.2.2 Vˇ eta. Necht’ A je celoˇc´ıselná matice, b, c jsou celoˇc´ıselné vektory a necht’ u a v jsou vrcholy polyedru P = {x | Ax = b, x ≥ 0}. Pak, za pˇredpokladu cT u 6= cT v, plat´ı |cT u − cT v| > 2−2L .

(3.6)

D˚ ukaz. Z teorie mnohostˇen˚ u v´ıme, ˇze je-li u vrcholem polyedru P , pak u je jedin´ ym ˇreˇsen´ım vhodného podsystému rovnic systému Ax = b, x ≥ 0. Tud´ıˇz, podle Cramerova pravidla, i-t´ a souˇradnice vrcholu u se dá ˆ ˆ vyj´ adˇrit jako ui = det Ai→b eho podsystému ˆ , kde A je matice onoho vhodn´ det A (tedy Aˆ je vhodná podmatice matice AI ) a Aî→b je matice vzniklá z Aˆ nahrazen´ım jej´ıho i-tého sloupce odpov´ıdaj´ıc´ımi sloˇzkami pravé strany ˆ ≤ 2L−n2 < 2L p˚ uvodn´ıho line´ arn´ıho programu. Z podoby Aˆ plyne | det A| (viz Pozorován´ı 2.3.2 v ˇcásti o elipsoidové metodˇe). Obdobn´ a pozorován´ı m˚ uˇzeme udˇelat i pro vrchol v. V´ıme proto, ˇze existuj´ı q1 , q2 ∈ N taková, ˇze q1 , q2 < 2L a zároveˇ n T T u q1 a v q2 jsou celoˇc´ıselné vektory. Tud´ıˇz T T u − cT v) T v q q (c q c u q c 1 2 1 2 = > 1 , |cT u − cT v| = − 22L q1 q2 q1 q2 kde v posledn´ı nerovnosti vyuˇz´ıv´ ame skuteˇcnosti, ˇze q1 q2 (cT u − cT v) je d´ıky volbˇe q1 a q2 celé ˇc´ıslo. ⊔ ⊓

3.3. Struktura algoritmu

25

3.2.3 D˚ usledek. Je-li xT s ≤ 2−2L , pro dvojici ˇreˇsen´ı x a (y, s) primárn´ı a duáln´ı u ´lohy, pak jak´ ykoli vrchol x′ takov´ y, ˇze cT x′ ≤ cT x, je optimáln´ı. D˚ ukaz. Sporem. Pˇredpokl´ adejme, ˇze existuje vrchol x′ takov´ y, ˇze cT x′ ≤ cT x, ale x′ nen´ı optimáln´ı. Pak podle pˇredeˇslé vˇety plat´ı cT x⋆ < cT x′ − 2−2L , kde x⋆ je nˇejak´ y optimaln´ı vrchol. S pouˇzit´ım pˇredpoklad˚ u xT s ≤ 2−2L a cT x′ ≤ cT x, rovnosti cT x = yT b + xT s a nerovnosti yT b ≤ cT x⋆ plynouc´ı z optimality x⋆ , dost´ aváme k´ yˇzen´ y spor cT x⋆ < cT x′ − 2−2L ≤ c T x − xT s = y T b ≤ c T x⋆ . ⊔ ⊓ Ve zbytku této kapitoly uvád´ıme tˇri pomocn´ a technick´ a tvrzen´ı. Jejich d˚ ukazy pˇrenecháváme ˇctenáˇri jako cviˇcen´ı z matematické anal´ yzy a line´ arn´ı algebry. 3.2.4 Lemma (Geometrick´ y a aritmetick´ y pr˚ umˇ er). Pro volná tj ≥ 0, j = 1, . . . , n, plat´ı:  

n Y

j=1

1/n

tj 

libo-

n

1X tj . ≤ n

(3.7)

j=1

3.2.5 Lemma (Odhady logaritm˚ u). Pro reálná ˇc´ısla x a a splˇ nuj´ıc´ı |x| ≤ a < 1 plat´ı x2 −x − ≤ ln(1 − x) ≤ −x . 2(1 − a)

(3.8)

3.2.6 Lemma. Je-li A matice plné ˇr´ adkové hodnosti, pak je matice AAT regul´ arn´ı.

3.3 Struktura algoritmu Na zaˇcátku najdeme dvojici striktnˇe pˇr´ıpustn´ ych ˇreˇsen´ı (x0 , s0 ) tako√ vou, ˇze G(x0 , s0 ) = O( nL). V kaˇzdé iteraci pak zajist´ıme pokles potenci´ alu o alespoˇ n 1/120 a skonˇc´ıme ve chv´ıli, kdy potenciál poprvé klesne √ pod −2 nL. T´ım bude zaruˇcen polynomi´ aln´ı poˇcet iterac´ı. Protoˇze ˇcas potˇrebn´ y pro kaˇzdou iteraci bude také omezen polynomem ve velikosti zadán´ı, bude i celkov´ y ˇcas algoritmu polynomi´ aln´ı. Rozhodnut´ı ukonˇcit algoritmus pˇri poklesu potenciálu pod hodnotu √ nuje následuj´ıc´ı lemma. −2 nL ospravedlˇ

26


√ 3.3.1 Lemma. Je-li G(x, s) ≤ −2 nL, pak xT s < e−2L . D˚ ukaz. Pouˇzijeme Lemma 3.7 pro tj = xj sj , j = 1, . . . , n. Po zlogaritmován´ı obou stran nerovnosti (3.7) a drobné u ´pravˇe dostaneme nerovnost n ln xT s −

n X j=1

ln xj sj ≥ n ln n .

(3.9)

Podle pˇredpoklad˚ u lemmatu, definice potenciálu (3.5) a nerovnosti (3.9) plat´ı n X √ √ T −2 nL ≥G(x, s) = (n + n) ln(x s) − ln(xi si ) ≥

√

n ln xT s + n ln n ≥

√

i=1

n ln xT s .

Tud´ıˇz −2L ≥ ln xT s a d˚ ukaz je hotov.

⊔ ⊓

D˚ usledek 3.2.3 spolu s Lemmatem 3.3.1 zaruˇcuj´ı, ˇze pˇri poklesu po√ tenci´ alu pod −2 nL uˇz jsme takˇrka v optimáln´ım ˇreˇsen´ı.

3.4 Jak nalézt striknˇe pˇr´ıpustná ˇreˇsen´ı x0 a s0 s omezen´ ym potenciálem Chceme p˚ uvodn´ı dvojici line´ arn´ıch program˚ u nahradit novou dvojic´ı tak, aby i) pro nov´ y line´ arn´ı program bylo snadné nalézt pˇr´ıpustné ˇreˇsen´ı s mal´ ym potenciálem, a aby ii) z optimáln´ıho ˇreˇsen´ı nového line´ arn´ıho programu bylo moˇzné jednoduˇsˇse z´ıskat optimáln´ı ˇreˇsen´ı p˚ uvodn´ıho line´ arn´ıho programu. Poslouˇz´ı nám n´ıˇze uvedené line´ arn´ı programy. min

cT x + 26L xn+1 Ax + (b − 22L Ae)xn+1 (24L e − c)T x + 24L xn+2 x xn+1 xn+2

= = ≥ ≥ ≥

b k 0 0 0

3.4. Jak nalézt striknˇe pˇr´ıpustn´ a ˇreˇsen´ı s omezen´ ym potenciálem

27

kde k = 26L (n + 1) − 22L cT e. bT y + kym+1 T 4L A y + (2 e − c)ym+1 + s 2L (b − 2 Ae)T y + sn+1 4L 2 ym+1 + sn+2 s sn+1 sn+2

max

= c = 26L = 0 ≥ 0 ≥ 0 ≥ 0

3.4.1 Lemma. Plat´ı: 1. Vektory x′ = (22L , 22L , . . . , 22L , 1, 22L ) a (y′ ; s′ ) = (0, −1; 24L , 24L , . . . , 24L , 26L , 24L ) jsou striktnˇe pˇr´ıpustn´ a ˇreˇsen´ı a √ nav´ıc G(x′ , s′ ) = O( nL). 2. Velikost nového line´ arn´ıho programu je O(L). 3. Jsou-li vektory x⋆ a y⋆ optimáln´ım ˇreˇsen´ım line´ arn´ıho programu ′′ ⋆ 4L (3.1) a (3.2), pak vektory x = (x , 0, (k − (2 e − c)T x⋆ )/24L ) a (y′′ , s′′ ) = (y⋆ , 0, s⋆ , 26L − (b − 22L Ae)T y⋆ , 0) jsou optimáln´ım ˇreˇsen´ım nov´ ych line´ arn´ıch program˚ u. 4. Maj´ı-li oba line´ arn´ı programy (3.1) a (3.2) pˇr´ıpustn´ a ˇreˇsen´ı a jsouli vektory x′′ and (y′′ , s′′ ) optimáln´ım ˇreˇsen´ım nov´ ych line´ arn´ıch program˚ u, pak vektory x a (y, s), kde x a s jsou restrikc´ı x′′ a s′′ na prvn´ıch n sloˇzek a y je restrikc´ı y′′ na prvn´ıch m sloˇzek, jsou optimáln´ım ˇreˇsen´ım line´ arn´ıch program˚ u (3.1) a (3.2).

D˚ ukaz. Ovˇeˇren´ı prvn´ıho, druhého a tˇret´ıho tvrzen´ı lemmatu je pouze technickou záleˇzitost´ı. Posledn´ı ˇcást vyˇzaduje o trochu v´ıce práce a jej´ı d˚ ukaz pˇreskoˇc´ıme; piln´ y ˇctenáˇr se o d˚ ukaz m˚ uˇze s pomoc´ı vˇet (podm´ınek) o komplementaritˇe primárn´ıho a duáln´ıho ˇreˇsen´ı pokusit s´ am. ⊔ ⊓

28


3.5 Iteraˇcn´ı krok Snadn´ y pˇ r´ıpad. V této podkapitole pˇredpokl´ ad´ ame, ˇze aktuáln´ı ˇreˇsen´ı T primárn´ı u ´lohy je e = (1, . . . , 1) a aktuáln´ı ˇreˇsen´ı duáln´ı u ´lohy je ′ s > 0. Jak jsme jiˇz popsali v u ´vodu, základn´ı myˇslenkou je zmˇenit ˇreˇsen´ı primárn´ı u ´lohy ve smˇeru opaˇcném ke gradientu potenciálu G(x, s) podle x v bodˇe (e, s′ ); zaˇcneme proto v´ ypoˇctem tohoto gradientu g.  1   x1 √ s  ..   g =∇x G(x, s)|(e,s′ ) = (n + n) T −  .  ′ x s 1 xn

=(n +

√

(e,s )

s′ n) T ′ − e . e s

(3.10)

Pˇr´ımo ve smˇeru −g ovˇsem j´ıt nem˚ uˇzeme, protoˇze bychom mohli poruˇsit podm´ınky Ax = 0. Z toho d˚ uvodu spoˇc´ıt´ ame projekci d vektoru g do nadroviny {x | Ax = 0}, a pokud bude dostateˇcnˇe velká, pˇrejdeme od aktuáln´ıho ˇreˇsen´ı e primárn´ı u ´lohy k ˇreˇsen´ı e − αd, pro vhodné α > 0, jehoˇz velikost upˇresn´ıme pozdˇeji. g

g−d

d Ax = 0

Obrázek 3.1: Projekce vektoru g do nadroviny {x | Ax = 0}. 3.5.1 Lemma (Projekce g do nadroviny {x | Ax = 0}). d = (I − A(AAT )−1 A)g .

(3.11)

D˚ ukaz. Nejprve si vˇsimneme, ˇze vektor g − d je z ortogonáln´ıho doplˇ nku vektorového prostoru {x | Ax = 0} a tud´ıˇz je line´ arn´ı kombinac´ı ˇr´ adk˚ u m y, ˇze matice A. Jin´ ymi slovy, existuje vektor w ∈ R takov´ g − d = AT w .

(3.12)

3.5. Iteraˇcn´ı krok

29

Podáˇr´ı-li se nám tento vektor w vyj´ adˇrit, budeme m´ıt i pˇredpis pro hledan´ y vektor d. Vynásoben´ım rovnosti (3.12) zleva matic´ı A dostaneme (s pouˇzit´ım rovnosti Ad = 0 vyjadˇruj´ıc´ı, ˇze d je projekce do poˇzadované nadroviny) Ag = AAT w . D´ıky plné ˇrádkové hodnosti matice A je matice AAT regul´ arn´ı, proto plat´ı w = (AAT )−1 Ag . Dosazen´ım za w do rovnosti (3.12) dostaneme k´ yˇzen´ y vztah (3.11).

⊔ ⊓

Prim´ arn´ı krok. Pokud bude kdk ≥ 0, 22 provedeme primárn´ı krok a dalˇs´ı dvojici pˇr´ıpustn´ ych ˇreˇsen´ı urˇc´ıme podle pˇredpisu ˜ =e− x

d , 4 kdk

˜s = s′ .

(3.13)

V opaˇcném pˇr´ıpadé provedeme krok duáln´ı (vysvˇetlen dále). Pro u ´spˇeˇsnost primárn´ıho kroku je tˇreba ovˇeˇrit dvˇe vˇeci: • opˇet jsme z´ıskali striktnˇe pˇr´ıpustné ˇreˇsen´ı primárn´ı u ´lohy, • potenciál podstatnˇe klesl. Ovˇeˇren´ı tˇechto podm´ınek je pˇredmˇetem následuj´ıc´ıch dvou lemmat. ˜ ). Vektor 3.5.2 Lemma (Striktn´ı pˇ r´ıpustnost x pˇr´ıpustné ˇreˇsen´ı primárn´ı u ´lohy.

˜ x

je

striknˇe

d je nejv´ yˇse 1, m´ ame zaruˇceno D˚ ukaz. Protoˇze kaˇzd´ a sloˇzka vektoru kdk ˜ > 0. Protoˇze Ad = 0, m´ ˜. x ame zaruˇcenou i pˇr´ıpustnost x ⊓ ⊔

3.5.3 Lemma (Pokles potenci´ alu v prim´ arn´ım kroku). Po proveden´ı primárn´ıho kroku plat´ı G(˜ x, ˜s) − G(e, s′ ) ≤

−1 . 120

(3.14)

30


√ D˚ ukaz. Pro zkr´ acen´ı zápisu pouˇzijeme v d˚ ukazu znaˇcen´ı q = (n+ n). Po ˜ a ˜s podle vzorce (3.13) dostaneme (indexy nad nˇekter´ dosazen´ı za x ymi relacemi pouˇz´ıv´ ame k pozdˇejˇs´ımu odvoláván´ı se na nˇe) n

X dj dT s ′ )− ln(1 − ) G(˜ x, ˜s) − G(e, s ) = q ln(e s − 4 kdk 4 kdk ′

T ′

j=1

−

n X j=1

ln(s′j ) − q ln(eT s′ ) + n

n X

ln(s′j )

j=1

X dj dT s ′ =q ln(1 − ) − ) ln(1 − 4 kdk eT s′ 4 kdk j=1

n

n

X dj X d2j dT s′ + + ≤−q 4 kdk eT s′ 4 kdk 16 kdk2 2(1 − 41 ) j=1 j=1 i

dT s′ dT e 1 =−q + + 4 kdk eT s′ 4 kdk 24 s′ 1 dT e−q T ′ + = 4 kdk e s 24 dT g 1 =− + 4 kdk 24 ii

kdk2 1 kdk 1 0,2 1 1 =− + =− + ≤− + =− 4 kdk 24 4 24 4 24 120

iii

Nerovnost (i) vycház´ı z odhadu logaritmu pomoc´ı Lemmatu (3.2.5) s |dj | ≤ 41 ). Rovnost (ii) pouˇz´ıv´ ame 4kdk a v´ ypoˇcet parametrem a = 41 (jistˇe m´

gradientu g (3.10). Rovnost (iii) vyuˇz´ıv´ a vztah gT d = dT d plynouc´ı z Pythagorovy vˇety (gT g = dT d + (g − d)T (g − d)). Posledn´ı nerovnost vyuˇz´ıv´ a doln´ı mez na kdk pro primárn´ı krok. ⊔ ⊓

Du´ aln´ı krok. Duáln´ı krok provedeme, pokud kdk < 0,22. Základn´ı myˇslenka duáln´ıho kroku je stejn´ a jako v kroku primárn´ım: spoˇc´ıtat gradient h potenciálu G(x, s) podle s v bodˇe (e, s′ ) a posunout ˇreˇsen´ı duáln´ı u ´lohy ve smˇeru urˇceném vektorem −h. Podobnˇe jako v kroku primárn´ım bude ale tˇreba ohl´ıdat, abychom neporuˇsili ˇzádnou omezuj´ıc´ı podm´ınku. Zaˇcnˇeme v´ ypoˇctem gradientu h. Protoˇze role promˇenn´ ych x a s ve funkci G(x, s) jsou symetrické, s pˇrihlédnut´ım ke vztahu (3.10) rovnou nahlédneme, ˇze pro gradient h potenciálu G(x, s) podle s v bodˇe (e, s′ )


31

plat´ı

h = ∇s G(x, s)|(e,s′ ) = (n +

√

n)



1 s′1



e  ..  −  .  . eT s ′ 1

(3.15)

s′n

Porovnejme nyn´ı jednotlivé sloˇzky vektor˚ u g a h. Plat´ı jednoduch´ y vztah, pro j = 1, . . . , n, gj hj = ′ . sj Protoˇze vˇsechny sloˇzky vektoru s′ jsou kladné, ukazuj´ı vektory g a h podobn´ ym smˇerem, presnˇeji ˇreˇceno, do stejného ortantu. Vzhledem k této podobnosti g a h, a vhledem k tomu, ˇze o vektoru g uˇz lecos v´ıme, budeme v duáln´ım kroku pracovat s vektorem g a nikoli s vektorem h. Oznaˇcme si y′ druhou ˇcást sloˇzek pˇr´ıpustného ˇreˇsen´ı duáln´ı u ´lohy ′ odpov´ıdaj´ıc´ı vektoru s ; protoˇze se jedn´ a o pˇr´ıpustné ˇreˇsen´ı, vektory y′ a s′ splˇ nuj´ı AT y′ + s′ = c .

(3.16)

Naˇs´ım d´ılˇc´ım c´ılem je zmˇenit aktuáln´ı duáln´ı pˇr´ıpustné ˇreˇsen´ı s′ na nové duáln´ı pˇr´ıpustné ˇreˇsen´ı ˜s (a pˇri tom zajistit pokles potenciálu). Zajist´ıme˜ splˇ li pˇri volbˇe ˜s, ˇze existuje vektor y nuj´ıc´ı rovnici ˜ + ˜s = c , AT y

(3.17)

m´ ame zaruˇcenu pˇr´ıpustnost ˜s. Ze vztah˚ u (3.16) a (3.17) plyne pro ˜s omezen´ı ˜s − s′ = AT (y′ − y ˜) .

(3.18)

Vyjádˇreno slovy, ˜s−s′ mus´ı b´ yt line´ arn´ı kombinac´ı ˇr´ adk˚ u matice A, neboli ′ ˜s − s mus´ı b´ yt kolmé na nadrovinu {x | Ax = 0}. S jedn´ım vektorem kolm´ ym na nadrovinu {x | Ax = 0} uˇz jsme pracovali, totiˇz s vektorem g − d. Proto se pˇri rozhodován´ı, jak zlepˇsovat duáln´ı ˇreˇsen´ı s′ , nab´ız´ı vydat se smˇerem −(g − d). Tuto myˇslenku provedeme a v duáln´ım kroku urˇc´ıme dalˇs´ı dvojici pˇr´ıpustn´ ych ˇreˇsen´ı podle pˇredpisu eT s ′ √ (g − d) , x ˜s = s − ˜=e. n+ n ′

Podobnˇe jako v primárn´ım kroku je tˇreba ovˇeˇrit dvˇe vˇeci:

(3.19)

32

Kapitola 3. Metoda vnitˇrn´ıho bodu • z´ıskali jsme striktnˇe pˇr´ıpustné ˇreˇsen´ı duáln´ı u ´lohy, • potenciál podstatnˇe klesl.

Ovˇeˇren´ı tˇechto podm´ınek je pˇredmˇetem následuj´ıc´ıch dvou lemmat. 3.5.4 Lemma (Striktn´ı pˇ r´ıpustnost ˜s). Po proveden´ı kroku je ˜s striktnˇe pˇr´ıpustné ˇreˇsen´ı duáln´ı u ´lohy.

duáln´ıho

˜ splˇ D˚ ukaz. Existence vektoru y nuj´ıc´ımu rovnost (3.17) plyne z definice ˜s (vol´ıme ˜s, aby ˜s − s′ bylo line´ arn´ı kombinac´ı ˇr´ adk˚ u AT ), proto je ˜s pˇr´ıpustné ˇreˇsen´ı. Jeˇstˇe ovˇeˇr´ıme jeho striktn´ı pˇr´ıpustnost. Podle definice ˜s a definice g, pro vektor ˜s plat´ı √ T s′ T s′ n e e n + √ (g − d)s′ − √ ( T ′ s′ − e − d) = ˜s = s′ − n+ n n+ n e s eT s ′ √ (d + e) . (3.20) = n+ n Protoˇze duáln´ı krok provád´ıme v pˇr´ıpadˇe kdk < 0,22, je z posledn´ıho vyj´ adˇren´ı vidˇet ˜s > 0. T´ım je d˚ ukaz hotov. ⊓ ⊔ Dˇr´ıve neˇz odhadneme pokles potenciálu pˇri proveden´ı duáln´ıho kroku, dokáˇzeme pomocné lemma. 3.5.5 Lemma. n X j=1

D˚ ukaz. n X j=1

=

eT ˜s 1 ln s˜j ≥n ln − . n 32

(3.21)

n

eT ˜s X eT s′ eT s ′ eT d ln s˜j − n ln = (1 + dj )) − n ln( (1 + )) ln( n q q n

n X j=1

j=1

n X d2j eT d eT d (dj − )≥ )−n ln(1 + dj ) − n ln(1 + n 2(1 − 0,22) n

kdk2 1 =− ≥− . 2(1 − 0,22) 32

j=1

Prvn´ı rovnost plyne ze vztahu (3.20) odvozeného v d˚ ukazu pˇredeˇslého lemmatu. Pˇri dalˇs´ıch u ´pravách jsou pouˇzity základn´ı vlastnosti funkce logaritmus, jej´ı odhady z Lemmatu 3.2.5 a horn´ı odhad na velikost kdk v duáln´ım kroku. ⊔ ⊓


33

3.5.6 Lemma (Pokles potenci´ alu v du´ aln´ım kroku). Po den´ı duáln´ıho kroku plat´ı G(˜ x, ˜s) − G(e, s′ ) ≤ −

1 . 3

prove-

(3.22)

D˚ ukaz. Zaˇcneme pomocn´ ym v´ ypoˇctem, kde v prvn´ pouˇ z´ıv´ ame Pnı rovnosti P n 2 identitu (3.20) a pro prvn´ı nerovnost vztah ( i=1 di ) ≤ n i=1 d2i (dokaˇzte si s pouˇzit´ım Cauchy-Schwarzovy nerovnosti): √ eT s ′ T eT s ′ eT s ′ √ e ˜s = (e d + n) ≤ ( n kdk + n) ≤ (n + 0,22 n) . q q q T

Dost´ aváme √ √ √ n − 0,22 n eT ˜s n + 0,22 n √ ≤ . =1− eT s ′ q n+ n

(3.23)

Pokles potenciálu pak odhadneme takto: ′

T

G(e, ˜s) − G(e, s ) =q ln(e ˜s) − eT ˜s =q ln T ′ − e s

n X

j=1 n X j=1

T ′

ln s˜j − q ln(e s ) + ln s˜j +

n X

n X

ln s′ j

j=1

ln s′ j

j=1

eT ˜s eT ˜s 1 eT s′ ≤q ln T ′ − n ln + + n ln e s n 32 n T 1 e ˜s =(q − n) ln T ′ + 32 √e s √ ii √ n − 0,22 n 1 1 ≤ − ( n) + ≤ − q 32 3 i

kde nerovnost (i) plyne z odhadu (3.21) (Lemma 3.5.5) a ze vztahu Pn ′ ≤ n ln eT s′ vych´ azej´ıc´ıho z Lemmatu (3.7) (aritmetick´ y a geln s j j=1 n ometrick´ y pr˚ umˇer). Nerovnost (ii) vyuˇz´ıv´ a odhad (3.23) a Lemma 3.2.5 o odhadu logaritmu. V posledn´ı nerovnosti odhadujeme shora q pomoc´ı 2n. ⊔ ⊓ Obecn´ y pˇ r´ıpad. Pomoc´ı vhodné afinn´ı transformace pˇrevedeme obecn´ y pˇr´ıpad na snadn´ y (tj. x = e), pro kter´ y iteraˇcn´ı krok provést ¯ je posledn´ı sestrojené primárn´ı ˇreˇsen´ı a jiˇz um´ıme. Pˇredpokl´ adejme, ˇze x

34


¯s posledn´ı sestrojené duáln´ı ˇreˇsen´ı. ¯ na e. Poloˇzme raz´ı x  x ¯1 ¯ = X  0 0

Chceme afinn´ı zobrazen´ı, které zob0 .. . 0

0



 0  . x ¯n

(3.24)

¯ regul´ ¯ je striknˇe pˇr´ıpustné ˇreˇsen´ı, je matice X Protoˇze x arn´ı a existuje k ¯ −1 a plat´ı n´ı inverzn´ı matice X   −1 x ¯1 0 0  .. ¯ −1 =  (3.25) X  0 . 0  . 0

0

x ¯−1 n

¯ −1 je matice hledaného afin´ıho zobrazen´ı: Matice X ¯ −1 x ¯=e X

¯ −1 x vektor nov´ Oznaˇcme x′ = X ych promˇenn´ ych odvozen´ ych od x ¯ −1 , a vyjádˇreme primárn´ı u pomoci matice X ´lohu v ˇreˇci tˇechto nov´ ych promˇenn´ ych. ¯ ′ min cT Xx ¯ ′=b AXx x′ ≥ 0 ¯ ac ¯ lze u ¯ = cT X Pˇri oznaˇcen´ı A¯ = AX ´lohu pˇrepsat následovnˇe: ¯ T x′ min c ¯ ′=b Ax

(3.26)

x′ ≥ 0 Uvˇedomme si, ˇze x je pˇr´ıpustné ˇreˇsen´ı pro p˚ uvodn´ı primárn´ı u ´lohu právˇe ¯ −1 x je pˇr´ıpustné ˇreˇsen´ı pro poslednˇe uvedenou u tehdy, kdyˇz x′ = X ´lohu line´ arn´ıho programován´ı. Duáln´ı u ´loha k (3.26) pak vypad´ a takto: max bT y ¯ T y + s′ = X¯ ¯c (AX) s′ ≥ 0

3.6. Jak ze skoro optimáln´ıho ˇreˇsen´ı naj´ıt u ´plnˇe optimáln´ı

35

¯ kde s′ = Xs. N´ asleduj´ıc´ı jednoduché lemma vystihuje kl´ıˇcovou vlastnost uˇzité afinn´ı transformace: potenciál dvojice pˇr´ıpustn´ ych ˇreˇsen´ı se transformac´ı nezmˇen´ı. 3.5.7 Lemma (Zachov´ an´ı potenci´ alu). Pro regul´ arn´ı diagon´ aln´ı ma¯ s hlavn´ı diagon´ tici X alou x ¯1 , . . . , x ¯n , a pro libovolná pˇr´ıpustn´ a ˇreˇsen´ı ′ −1 ′ ¯ x a s = Xs ¯ plat´ı (x, s) p˚ uvodn´ı primárn´ı a duáln´ı u ´lohy a pro x = X G(x′ , s′ ) =G(x, s) . D˚ ukaz. Lemma plyne okamˇzitˇe z definice potenciálu a pˇredpis˚ u pro x′ a ⊓ ⊔ ¯i , a tedy xi si = x′i s′i . xi a s′i = si x s′ , podle kter´ ych x′i = xi /¯

3.6 Jak ze skoro optimáln´ıho ˇreˇsen´ı naj´ıt u ´plnˇe optimáln´ı ¯ a (¯ Pˇredpokl´ adejme, ˇze m´ ame k dispozici ˇreˇsen´ı x y, ¯s) u ´loh (3.1) a (3.2) −2L −L T ¯ ¯s < 2 . Pak pro kaˇzdé i jistˇe x ¯i < 2 nebo s¯i < 2−L . taková, ˇze x Budeme se snaˇzit kaˇzdou malou sloˇzku nahradit nulou, a ostatn´ı zmˇenit tak, abychom stále mˇeli pˇr´ıpustn´ a ˇreˇsen´ı. Pokud se nám to podaˇr´ı, bude v´ ysledná dvojice ˇreˇsen´ı jistˇe splˇ novat podm´ınky komplementarity (tj. T x s = 0) a p˚ ujde tedy o optimáln´ı ˇreˇsen´ı. Podobnˇe jako v pˇredeˇslé ˇcásti budeme pˇredpokl´ adat, ˇze matice A a vektory b a c jsou celoˇc´ıselné. Pro n-sloˇzkov´ y vektor u ∈ Rn zavedeme následuj´ıc´ı znaˇcen´ı: M (u) = {j | uj < 2−L } , V (u) = {j | uj ≥ 2−L } . Pro matici A a mnoˇzinu index˚ u J oznaˇcme AJ podmatici matice A tvoˇrenou sloupci s indexy z J. Zaˇcneme dvˇema pomocn´ ymi lemmaty, s jejichˇz pomoc´ı pak provedeme naznaˇcen´ y pl´ an na zaokrouhlen´ı. ¯ pˇr´ıpustné ˇreˇsen´ı u 3.6.1 Lemma. Je-li x ´lohy (3.1), pak v polynomi´ aln´ım ˆ takové, ˇze ˇcase lze naj´ıt pˇr´ıpustné ˇreˇsen´ı x • x ˆj = x ¯j pro j ∈ M (¯ x), • sloupce matice AV (ˆx) jsou line´ arnˇe nez´ avislé.

36


D˚ ukaz. Pˇredpokl´ adejme, ˇze sloupce matice AV (¯x) jsou line´ arnˇe závislé ˆ=x ¯ a jsme hotovi). Pak jistˇe homogenn´ı (v opaˇcném pˇr´ıpadˇe poloˇz´ıme x soustava AV (¯x) v = 0 m´ a netriviáln´ı ˇreˇsen´ı; oznaˇcme v′ nˇejaké takové ˇreˇsen´ı doplnˇené nulami na souˇradnic´ıch M (¯ x) na vektor délky n. Vhod′ ¯ = x ¯ − λv′ pˇr´ıpustn´ nou volbou skaláru λ 6= 0 je vektor x ym ˇreˇsen´ım ′ soustavy (3.1) a nav´ıc V (¯ x ) ( V (¯ x). Opakujeme-li tento postup, dostaˆ s k´ neme po nejv´ yˇsˇse n iterac´ıch vektor x yˇzen´ ymi vlastnostmi. ⊔ ⊓ ¯ pˇr´ıpustné ˇreˇsen´ı u 3.6.2 Lemma. Je-li x ´lohy (3.1), pak existuje vrchol v mnohostˇenu P = {x | Ax = b, x ≥ 0} splˇ nuj´ıc´ı vj = 0 pro kaˇzdé j ∈ M (¯ x). Obdobnˇe, je-li (¯ y, ¯s) pˇr´ıpustné ˇreˇsen´ı u ´lohy (3.2), pak existuje ′ ′ vrchol (y , s ) mnohostˇenu Q = {(y, s) | s ≥ 0 and AT y+s = c} splˇ nuj´ıc´ı T ′ Aj y = cj pro kaˇzdé j ∈ M (¯ s). D˚ ukaz. V d˚ ukazu Vˇety 3.2.2 jsme nahlédli, ˇze kaˇzd´ a nenulová sloˇzka 2 libovolného vrcholu v mnohostˇenu P je vetˇs´ı neˇz 1/2L−n , kde L je velikost zápisu line´ arn´ıho programu (3.1). Pro zjednoduˇsen´ı pro zat´ım pˇredpokl´ adejme, ˇze mnohostˇen P je omezen´ y. Pak dané pˇr´ıpustné ˇreˇsen´ı ¯ je, podle Carathéodorovy vˇety o konvexn´ım obalu, konvexn´ı kombix P ¯ = pi=1 λi vi nac´ı nˇejak´ ych p ≤ n + 1 jeho vrchol˚ u v1 , . . . , vp , neboli x pro nˇejaké nez´ aporné koeficienty λ1 , . . . , λp se souˇctem jedna. Tud´ıˇz jistˇe alespoˇ n jeden koeficient, oznaˇcme ho i, splˇ nuje λi ≥ 1/(n + 1). Ukáˇzeme, ˇze vi,j = 0 pro kaˇzdé j ∈ M (¯ x), neboli v = vi je hledan´ y vrchol. Pˇredpokl´ adejme pro spor, ˇze vi,j > 0 pro nˇejaké j ∈ M (¯ x). Pak doL konce vi,j > 1/2 , protoˇze jde o vrchol P . Pouˇzijme tento fakt k doln´ımu odhadu velikosti x ¯j : x ¯j =

p X k=1

λk vjk ≥ λi vi,j >

1 1 1 · L−n2 > L n+1 2 2

coˇz je ovˇsem spor se skuteˇcnost´ı j ∈ M (¯ x). Druhá ˇcást lemmatu se dokáˇze obdobnˇe. Podle Carathéodorovy vˇety existuje q = m + 1 vrchol˚ u (yi , si ) mnohostˇ enu Q takov´ ych, ˇze (¯ y, ¯s) P q je jejich konvexn´ı kombinac´ı, neboli (¯ y, ¯s) = i=1 µi (yi , si ) pro vhodné nez´ aporné koeficienty µi se souˇctem jedna. Necht’ i je index splˇ nuj´ıc´ı µi ≥ 1/(m + 1). Ukáˇzeme, ˇze vrchol (yi , si ) m´ a poˇzadované vlastnosti. T Kdyby pro nˇejaké j ∈ M (¯ s) neplatilo Aj yi = cj , pak podobnˇe jako v pˇredeˇslém pˇr´ıpadˇe dokonce plat´ı sij > 1/2L . Protoˇze ¯s je konvexn´ı kombinac´ı s1 , . . . , sq s koeficienty µ1 , . . . , µq , dostaneme opˇet spor. ⊔ ⊓

3.7. Shrnut´ı

37

¯ a ¯s najdeme nejprve podle Lemmatu 3.6.1 Pro dan´ a pˇr´ıpustn´ a ˇreˇsen´ı x ˆ takové, ˇze matice AV (ˆx) m´ pˇr´ıpustné ˇreˇsen´ı x a line´ arnˇe nez´ avislé sloupce. Podle Lemmatu 3.6.2 existuje pˇr´ıpustné ˇreˇsen´ı v primárn´ı u ´lohy se vˇsemi souˇradnicemi z M (ˆ x) nulov´ ymi, a také pˇr´ıpustné ˇreˇsen´ı (y′ , s′ ) duáln´ı u ´lohy se vˇsemi souˇradnicemi V (ˆ x) ⊆ M (ˆs) nulov´ ymi. Protoˇze sloupce matice AV (ˆx) jsou line´ arnˇe nez´ avislé, je vrchol v urˇcen jednoznaˇcnˇe a lze z´ıskat ˇreˇsen´ım soustavy line´ arn´ıch rovnic Ax = b pˇri nastaven´ı xi = 0 pro kaˇzdé i ∈ M (ˆ x). Protoˇze vT s′ = 0, je v hledané optimáln´ı ˇreˇsen´ı. Pro u ´plnost jeˇstˇe dodáváme, ˇze existuje nˇekolik dalˇs´ıch postup˚ u pro pˇrechod od skoro optimáln´ıho ˇreˇsen´ı k optimáln´ımu.

3.7 Shrnut´ı Pˇrehlédneme-li drobné implementaˇcn´ı obt´ıˇze s odmocninami, dopracovali jsme se k následuj´ıc´ı vˇetˇe. Pˇripomeˇ nme si, ˇze poˇcet iterac´ı algoritmu je √ O( nL) a nejsloˇzitˇejˇs´ı operac´ı v iteraci je maticové násoben´ı (pˇri Gaussovˇe eliminaci O(n3 ) aritmetick´ ych operac´ı). 3.7.1 Vˇ eta (Karmarkar, 1984). Existuje algoritmus pro ˇreˇsen´ı u ´lohy 3,5 line´ arn´ıho programován´ı s pouˇz´ıt´ım O(n L) aritmetick´ ych operac´ı. Pozn´ amka. P˚ uvodn´ı Karmarkar˚ uv algoritmus z roku 1984 se od zde popsaného algoritmu v mnohém liˇs´ı (jin´ y potenciál, jin´ a transformace, 3,5 jin´ y poˇcet iterac´ı, ..., nicménˇe sloˇzitost O(n L) ); tento text vycház´ı pˇredevˇs´ım z algoritmu navrˇzeného Ye [13] (viz téˇz Freund [2] a Goemans˚ uv uˇcebn´ı text [3]). Karmarkar˚ uv algoritmus byl ale prvn´ım ze skupiny metod vnitˇrn´ıch bod˚ u, pro které byl dokázán polynomi´ aln´ı odhad na dobu bˇehu.

Literatura [1] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver. Combinatorial Optimization. John Wiley, New York, 1997. [2] R. M. Freund. Polynomial algorithms for linear programming based only on primal scaling and projected gradients of a potential function. Mathematical Programming, 51:203–222, 1991. [3] M. Goemans. Advanced algorithms: Linear programming. Technical report, MIT, Boston, 1994. [4] L. G. Chaˇcijan. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR, 244:1093–1096, 1979. [5] N. Karmarkar. A new polynomial time algorithm for linear programming. Combinatorica, 4(4):373–395, 1984. [6] M. Gr¨ otschel and L. Lovász and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, Berlin, 1988. [7] J. Matouˇsek. Line´ arn´ı programov´ an´ı a line´ arn´ı algebra pro informatiky. ITI Series. Univerzita Karlova v Praze, Institut teoretickéinformatiky, 2006. [8] J. Matouˇsek and B. G¨ artner. Understanding and Using Linear Programming. Universitext (En ligne). Springer, 2007. [9] N. Megiddo. Linear programming in linear time when the dimension is fixed. Journal of Association for Computing Machinery, 31(1):114–127, Jan. 1984. [10] R. Seidel. Skript zur Vorlesung Optimierung. Technical report, Universität des Saarlandes, Saarbr¨ ucken, 1996.

40

Literatura

[11] D. A. Spielman and S.-H. Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3):385–463, 2004. [12] E. Tardos. A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res., 34:250–256, 1986. [13] Y. Ye. An O(n3 L) potential reduction algorithm for linear programming. Mathematical Programming, 50:239–258, 1991.

Polynomiální algoritmy. Petr Kolman

Recommend Documents