4 Konvexita a mnohostěny V této přednášce si uvedeme či zopakujeme základní matematické pojmy nutné pro pochopení a zdůvodnění principů lineární optimalizace a jejího řešení tzv. simplexovou metodou. Mimo připomenutí běžných pojmů algebry a topologie se jedná především o pojmy konvexity a mnohostěnu. Samotný pojem mnohostěnu přitom je intuitivní v dimenzích 2 nebo 3, ale ve vyšších dimenzích již přináší netriviální komplikace. Stručný přehled lekce ˇ Zopakování základních pojmů lineární algebry a topologie. ˇ Definice konvexity a konvexní množiny, Farkasovo lema. ˇ Mnohostěny a jejich vlastnosti. Petr Hliněný, FI MU 1 IA102 "OU": Konvexita a mnohostěny 4.1 Vybrané matematické pojmy Definice některých základních pojmů lineární algebry: ˇ d-dimenzionální euklidovský prostor je vektorový prostor Rd s klasickým skalár- ním součinem. ˇ Afinní podprostor je vektorový podprostor posunutý o daný vektor (tj. nemusí procházet počátkem) . ˇ Dimenze podprostoru je počet prvků jeho báze. Dimenze množiny X je nejmenší dimenzí afinního podprostoru obsahujícího X. ˇ Nadrovinou v Rd rozumíme afinní podprostor dimenze d - 1. ˇ Poloprostor v Rd je uzavřená podmnožina, jejíž hranicí je nadrovina, neformál- ními slovy množina všech bodů "na jedné straně nadroviny". ˇ Nechť x = x2 1 + . . . + x2 d značí délku vektoru x Rd . Nadrovina v Rd je určena lineární rovnicí a x = a1x1 + . . . + adxd = b. Poloprostor v Rd je určen lineární nerovnicí a x = a1x1 + . . . + adxd b. Značení: Pokud H označuje nadrovinu, H+ a H- označuje příslušné dva poloprostory určené H (bez definovaného rozlišení, který ze dvou je H+ a který H- ). Petr Hliněný, FI MU 2 IA102 "OU": Konvexita a mnohostěny Definice několika běžných topologických pojmů: ˇ Mějme množinu X Rd . X je omezená, pokud existuje konstanta k R taková, že x X platí x < k. ˇ Množina X Rd je uzavřená, pokud pro každou konvergentní posloupnost (x1, x2, ...) X platí (limn xn) X. (Neformálně, že "hranice X patří" do X.) ˇ Množina X Rd je otevřená, pokud její doplněk je uzavřený. ˇ Funkce f se je spojitá, je-li vzorem otevřené množiny (tj. f-1 (U)) opět otevřená množina. (Neformálně pro každé dva "dostatečně blízké" body jsou si blízké i jejich funkční hodnoty.) Definice 4.1. Kompaktní množina X je taková, ve které každá nekonečná posloupnost (x1, x2, ...) X má podposloupnost konvergu- jící uvnitř X. Věta 4.2. Nechť X Rd . a) Pak X je kompaktní právě když je X omezená a uzavřená. b) Každá spojitá funkce f : X R má na kompaktní množině X globální maximum i minimum. Petr Hliněný, FI MU 3 IA102 "OU": Konvexita a mnohostěny 4.2 Konvexita: definice a vlastnosti Definice 4.3. Konvexní kombinací vektorů x, y Rd rozumíme každý vektor tvaru x + (1 - )y, 1, 0 . (Tj. všechny body na úsečce s konci x a y.) Množina X Rd je konvexní, pokud s každými dvěma body x, y X patří do X i celá úsečka xy, tj. všechny konvexní kombinace vektorů x, y. x 0.6x + 0.4y y Obrázek 4.1: Příklad konvexní kombinace vektorů x, y. Lema 4.4. Průnik X Y dvou konvexních množin X, Y je konvexní. Důkaz: Zcela jasné z definice konvexní množiny. 2 Důsledek 4.5. Množina všech přípustných řešení úlohy LP je konvexní. Definice: Nechť K je konvexní množina. Bod v K je krajním bodem K, pokud neexistují body x, y K \ {v} takové, že v by bylo konvexní kombinací x a y. Petr Hliněný, FI MU 4 IA102 "OU": Konvexita a mnohostěny Věta 4.6. Nechť X Rd je uzavřená a konvexní množina a z Rd je bod z / X. Pak existuje nadrovina H Rd oddělující z od X, jinými slovy existují a Rd , b R takové, že a z < b a x X: a x > b. zX H a x > b a x = b a x < b Důkaz: Nechť x X je libovolné a l = x - z . Pak vezmeme X X podmnožinu všech bodů ve vzdálenosti l od z. X je uzavřená, omezená, tedy kompaktní, a tudíž podle Věty 4.2 má funkce vzdálenosti f(x) = x - z minimum na X v některém bodě y X (y je bod X nejbližší k z). Za oddělující nadrovinu H vezmeme kolmou nadrovinu k úsečce yz procházející jejím středem, tj. volíme a = y - z a b = y+z 2 a. Pokud by existoval bod t X, pro který a t < b (tzn. t leží na stejné straně H jako z), pak by i celá úsečka yt patřila do X podle definice konvexity. Jelikož však úsečka yt protíná oddělující nadrovinu H, musí na ní podle trojúhelníkové nerovnosti ležet bod bližší k z než je y, a to je spor. (Uvědomte si, že zmíněný bližší bod nemusí být t samotný.) 2 Petr Hliněný, FI MU 5 IA102 "OU": Konvexita a mnohostěny Velmi známý důsledek předchozí věty je znám jako Farkasovo lema. Důsledek 4.7. (Farkasovo lema) Soustava lineárních rovnic u T A = c T má ne- záporné řešení u 0 právě tehdy, když pro každé řešení soustavy A y 0 platí c y 0. Důkaz : Předpokládejme, že u 0 a y jsou takové, že uT A = cT a A y 0. Potom c y = (uT A) y = uT (A y) 0. Důkaz (sporem): Předpokládejme, že uT A = cT nemá nezáporné řešení. Ukážeme, že potom existuje y takové, že A y 0 a c y > 0. Uvažme množinu P = {uT A : u 0}. Množina P je zřejmě uzavřená a konvexní a platí, že c P. Podle Věty 4.6 existuje oddělující nadrovina mezi c a množinou P, tj. existují a a b takové, že ac < b a zároveň a x b pro každé x P. Dokážeme, že lze volit b = 0 (tj. že naše oddělující nadrovina může procházet počát- kem). Zřejmě 0 P a tedy a c < 0, protože 0 = a 0 b. Přepokládejme, že existuje x P takové, že ax < 0. Z definice P plyne, že pro každé 0 platí x P. Avšak pro dostatečně velké dostaneme, že a(x) = (ax) < b, neboť (ax) - pro , a tedy že P se nachází na obou stranách oddělující nadroviny, ale to je zřejmý spor. Z toho plyne, že a x 0 pro každé x P, tedy že můžeme volit b = 0. Konečně zvolme y = -a. Potom c y = -a c > 0 a zároveň A y = -A a 0, což plyne dosazením jednotlivých řádků matice A za x do nerovnice ax b = 0 (všechny řádkové vektory A jsou zřejmě v P). 2 Petr Hliněný, FI MU 6 IA102 "OU": Konvexita a mnohostěny Důsledek 4.8. (Farkasovo lema trochu jinak) Nechť soustava A x c, x 0 nemá řešení. Pak existuje vektor 0 takový, že A 0 a c < 0. Důkaz: Zřejmě soustava (A) (x) c, x 0 má řešení právě když má řešení následující soustava (A | I) x z = c, x 0, z 0 . Nechť u T = (x T , z T ) a A = AT I . Z Farkasova lematu 4.7 pro A a u plyne, že existuje y takové, že A y 0 a c y > 0. Nyní zvolme = -y T . Pak A T = -A y 0, což lze rozepsat jako AT T = ( A) T 0 a navíc I = 0. Zároveň platí, že c = -c y < 0. 2 Alternativní formulace Farkasova lematu v Důsledku 4.8 má následující pěkný význam: Nemá- li soustava A x c, x 0 řešení, lze přímo získat nezápornou lineární kombinací řádků soustavy spor 0 A x c < 0. Petr Hliněný, FI MU 7 IA102 "OU": Konvexita a mnohostěny 4.3 Mnohostěny Mnohostěn lze popsat jeho vrcholy nebo jeho stěnami (facetami), ale převod mezi těmito popisy není vůbec jednoduchý a může z výpočetního hlediska vést k exponen- ciálnímu nárustu složitosti. Proto se na mnohostěny budeme dívat dvěma odlišnými formálními pohledy, nejprve pohledem na jeho stěny. Definice 4.9. Polyedr v Rd je průnikem konečně mnoha poloprostorů. (Je to konvexní a uzavřená množina podle Lemmatu 4.4.) Dobře si uvědomme, že z této definice vůbec nevyplývá omezenost polyedru. polyedr neomezený polyedr Petr Hliněný, FI MU 8 IA102 "OU": Konvexita a mnohostěny Definice 4.10. Stěna F d-dimenzionálního polyedru P je každá taková množina F P, pro kterou existuje nadrovina H v Rd určující poloprostor H+ , že P H+ a F = P H. Všimněme si, že i prázdná množina může být stěnou polyedru. Obvykle se za stěnu bere navíc i celý polyedr P a pak se a celému P říká nevlastní stěny. Všechny stěny včetně nevlastních zřejmě tvoří svaz s nejmenším i největším prvkem, navíc se jedná u omezeného polyedru o svaz atomický (atomy jsou jednotlivé vrcholy). Značení: Dimenzí stěny F přirozeně míníme afinní dimenzi množiny F. Stěny dimenze 0 nazýváme vrcholy, stěny dimenze 1 nazýváme hranami a stěny dimenze d-1 facetami d-dimenzionálního polyedru P. Fakt: Přímo z definic plyne, že vrcholy polyedru dimenze větší než 0 jsou jeho krajními body a naopak. (Pro dimenzi 0 se o tento fakt definice rozšíří.) Petr Hliněný, FI MU 9 IA102 "OU": Konvexita a mnohostěny Následuje druhý pohled na mnohostěny podle jejich vrcholů. Poznamenáváme, že obecně se v matematice mluví o konvexních mnohostěnech, ale jelikož zde uvažujeme jen konvexní množiny, tento přívlastek pro jednoduchost vynecháváme. Definice: Konvexním obalem conv(V ) množiny V Rd je průnik všech konvexních množin obsahujících V ; tj. neformálně množina všech bodů, které lze získat z bodů V (násobnými) konvexními kombinacemi. konvexní obal Definice 4.11. Polytop je konvexním obalem konečně mnoha bodů v Rd . (Opět se jedná o uzavřenou konvexní množinu, navíc vždy omezenou.) Poznámka: Citovaná učebnice [?] nerozlišuje mezi pojmy polyedru a polytopu a používá jen slovo "polyédr" v obou našich významech. To rozhodně není matematicky přesné. My přejdeme ke zjednodušené záměně pojmů polyedru a polytopu až po důkazu následující Věty 4.12. Petr Hliněný, FI MU 10 IA102 "OU": Konvexita a mnohostěny Ekvivalence pohledů na mnohostěny Nakonec si ukážeme, že z matematického pohledu lze pojmy polyedru a polytopu dle potřeby zaměnit. Platí však, že složitost popisu téhož tělesa jako polytopu se může diametrálně líšit od jeho popisu coby polyedru. Fakt: d-dimenzionální hyperkrychle má 2d stěn a 2d vrcholů. Věta 4.12. Omezený polyedr je polytop a naopak. Důkaz této důležité věty bude podán následujícími tvrzeními. Lema 4.13. Nechť P je omezený polyedr a F jeho faceta. Pak existuje vrchol (krajní bod) v P který neleží na F. Důkaz: Uvědomme si, že v dimenzi 0 je tvrzení triviální ­ jakékoliv těleso dimenze 0 je tvořeno jediným bodem, který je zároveň krajním bodem, a jedinou facetou takového tělesa je prázdná množina. Dále postupujeme matematickou indukcí podle dimenze P. Nechť H je nadrovina definující facetu F v P. Podle Věty 4.2 má funkce vzdálenosti bodu od H své globální maximum na kompaktním P, řekněme v bodě x P \ F. Označme H nadrovinu rovnoběžnou s H a rocházející x. Pokud H P = {x}, máme požadovaný vrchol. Jinak je H P polyedrem menší dimenze než P a podle indukčního předpokladu má H P nějaký vrchol. 2 Petr Hliněný, FI MU 11 IA102 "OU": Konvexita a mnohostěny Následující tvrzení pro zjednodušení nedokazujeme, ale odkazujeme čtenáře na argu- menty uvedené v Oddíle 6.2. Tvrzení 4.14. Nechť x je krajním bodem polyedru P dimenze d. Pak existuje d facet F1, . . . , Fd polyedru P takových, že F1 . . . Fd = {x}. Lema 4.15. Nechť P je omezený polyedr a X množina jeho krajních bodů. Pak X je konečná a conv(X) = P (tj. X jsou vrcholy tohoto polytopu). Důkaz: V prvé řadě, jelikož P má konečně mnoho facet, řekněme , má podle Tvr- zení 4.14 nejvýše d krajních bodů. Proto je X konečná. Označme T = conv(X). Zřejmě T P, protože P je konvexní z definice. Předpokládejme nyní, že existuje x P \ T . Z Věty 4.6 plyne, že mezi T a x existuje oddělující nadrovina H. Nechť x H- (H- je záporná strana H), tj. T H+ . Uvažme polyedr P = P H- s facetou F = P H. Podle Lematu 4.13 existuje další krajní bod s P nenáležející F. Proto je s zároveň krajním bodem původního P. Jelikož však podle naší volby X H+ a s H- , máme s X, spor. 2 Petr Hliněný, FI MU 12 IA102 "OU": Konvexita a mnohostěny Tímto jsme dokázali, že z popisu polyedru odvodíme jeho popis (téhož tělesa) coby polytopu. V opačném směru důkazu Věty 4.12 potřebujeme popsat daný polytop coby polyedr. Využijeme následujícího užitečného pojmu: Definice: Nechť S Rn . Polární množinou k S nazveme S = {y Rn : x y 1 pro všechna x S} . (1) Fakt: Pro každou S Rn je (S ) S. Praktický význam polární operace pro nás tkví v tom, že "převrací" popis polytopu P na popis P jako polyedru, zvaného polární polyedr (a taky naopak). Blíže viz následující tvrzení. Lema 4.16. Nechť P je polytop. Pak P je omezený polyedr. Důkaz: Podle definice P = {y Rn : x y 1 pro všechna x X} . Označme X konečnou množinu vrcholů P. Tvrdíme, že P = Q, kde Q = {y Rn : x y 1 pro všechna x X} , z čehož je ihned vidět, že P je průnikem konečně mnoha poloprostorů x y 1, tedy polyedrem. Zřejmě P Q. Nechť naopak y Q, pak x y 1 pro všechna x X a tudíž i pro každé x, které je konvexní kombinací z X. Proto q P . Navíc je Q zřejmě omezené. 2 Petr Hliněný, FI MU 13 IA102 "OU": Konvexita a mnohostěny Nyní pokud P je polytop, pak Q = P je omezený polyedr, a tudíž podle Lematu 4.15 je Q i polytop. Uplatněním stejné úvahy ještě jednou dostáváme, že i Q je omezený polyedr. Pro dokončení důkazu Věty 4.12 zbývá zdůvodnit, že Q = P. Je zřejmé, že posunutím souřadnic můžeme předpokládat, že počátek souřadnic je vnitřním bodem P. Lema 4.17. Nechť P je polytop obsahující počátek souřadnic 0 jako svůj vnitřní bod. Pak (P ) = P. Důkaz: Označme Y množinu vrcholů polyedru­polytopu P . Chceme dokázat P = S, kde S = {x Rn : x y 1 pro všechna y Y } . Jelikož již víme S (P ) P, stačí nám pro důkaz sporem předpokládat, že xo P pro nějaké xo S. Podle Věty 4.6 (o oddělující nadrovině) pak existují a, b takové, že a xo < b a přitom a x > b pro všechna x P. Jelikož 0 P, platí 0x = 0 > b. Vydělením uvedených nerovností záporným b proto dostáváme c xo > 1 , x P : c x < 1 , kde c = 1 b a. Proto podle definice (1) je c P . Jelikož P je také polytop, je c konvexní kombinací jeho vrcholů z Y ; c = 1y1 + . . . kyk . Nakonec získáme úpravou 1 < c xo = k i=1 iy i xo = k i=1 i(xo y i ) k i=1 i 1 = 1 , což je zřejmý spor. 2 Petr Hliněný, FI MU 14 IA102 "OU": Konvexita a mnohostěny