Zagadnienia

10. Twierdzenia strukturalne 2

10.1. Twierdzenia strukturalne 2

Na zakończenie wykładu pokażemy zastosowanie teorii dualności do opisu wielościanów. Zacznijmy od dualnego opisu stożków.

Lemat 10.1

Niech α1,α2,…,αt będą wektorami. Wówczas zbiór S=∑i=1t⁢ri⁢αi⁢|⁢ri≥0 jest wielościanem.

Niech d⁢i⁢m⁢⁢S=n. Dzięki twierdzeniu 2.4 bez zmniejszenia ogólności możemy przyjąć, że S⊂Rn.

Wybieramy wszystkie wektory γ∈Rn spełniające warunki:

1) ∀1≤i≤t⁢⁢αi∙γ≤0.

2) Istnieje n-1 liniowo niezależnych wektorów αi1,αi2,…,αin-1 w zbiorze α1,α2,…,αt , takich że ∀1≤j<n⁢⁢αij∙γ=0.

3) ⁢γ∙γ=1

Warunki 2) i 3) wymuszają skończoną liczbę wektorów γ.

Niech W=⋂⁢γ⁢Hγ, gdzie Hγ=x∈Rn⁢|⁢x∙γ≤0. Pokażemy teraz, że S=W.

Z warunku 1) wynika inkluzja S⊂W.

Niech b∉S. Badamy zadanie

M⁢a⁢x⁢⁢x0=b∙x

∀1≤i≤t⁢⁢αi∙x≤0.

Ponieważ wektory αi rozpinają przestrzeń Rn więc obszar dopuszczalny jest wielościanem o jedynym wierzchołku p=θ. Warunek b∉S oznacza, na mocy twierdzenia o dualności, twierdzenie 8.4, że p nie jest punktem optymalnym tego zadania. Zatem istnieje krawędź poprawiająca. Niech γ będzie unormowanym wektorem kierunkowym tej krawędzi. Wówczas:

1) γ∈W implikuje ∀1≤i≤t⁢αi∙γ≤0.

2) γ jest wektorem krawędzi więc istnieje n-1 liniowo niezależnych półprzestrzeni opisujących - wektorów αi1,αi2,…,αin-1 w zbiorze α1,α2,…,αt, takich że ∀1≤j<n⁢⁢αij∙γ=0.

3) γ∙γ=1.

Dodatkowo γ∙b≥0 więc b∉Hγ a zatem również b∉W.

Wykazaliśmy, że S=W jest wielościanem.

∎

Lemat ten można sformułować jako: ”Każdy wypukły i skończenie generowany stożek jest wielościanem”.

Pewna odmiana powyższego lematu jest nazywana ”Fundamentalnym twierdzeniem o nierównościach liniowych” i pochodzi z prac Farkasa [1894, 1898], Minkowskiego [1896], Karatheodoryego [1911] i Weyla [1935].

Twierdzenie 10.1 (Fundamentalne twierdzeniem o nierównościach liniowych)

Niech α1,α2,…,αt i β będą wektorami z przestrzeni Rn. Wówczas albo:

I) β jest nieujemną kombinacją liniową liniowo niezależnych wektorów z α1,α2,…,αt.

albo

II) Istnieje hiperprzestrzeń V=x∈Rn⁢|⁢γ∙x=0, zawierająca m-1 liniowo niezależnych wektorów z α1,α2,…,αt takich,

że γ∙β<0 i γ∙α1≥0,γ∙α2≥0,…,γ∙αt≥0,

gdzie m=d⁢i⁢m⁢⁢l⁢i⁢n⁢α1,α2,…,αt,β.

Algorytm szukania hiperprzestrzeni.

Krok 1. Jeżeli β∉l⁢i⁢n⁢α1,α2,…,αt to jako V można wziąć dowolną hiperprzestrzeń zawierającą l⁢i⁢n⁢α1,α2,…,αt i nie zawierającą β.

Krok 2. Przyjmijmy, że Rn=l⁢i⁢n⁢α1,α2,…,αt. Wybieramy dowolny liniowo niezależny podzbiór D=αi1,αi2,…,αin z wektorów α1,α2,…,αt.

Następnie wykonujemy następującą iterację:

i) Zapisujemy β=∑j=1n⁢aij⁢αij. Jeżeli ai1,ai2,…,ain≥0 to stop jesteśmy w przypadku I).

ii) W przeciwnym przypadku wybieramy najmniejszy indeks h spośród i1,i2,…,in taki,

że ah<0. Następnie budujemy hiperprzestrzeń H=x⁢|⁢γ∙x=0=l⁢i⁢n⁢D∖αh,

gdzie γ tak normalizujemy by γ∙αh=1. (Wtedy γ∙β=ah<0).

iii) Jeżeli γ∙α1≥0,γ∙α2≥0,…,γ∙αt≥0 jesteśmy w przypadku II).

iv) W przeciwnym przypadku wybieramy najmniejszy indeks s taki, że γ∙αs<0.

Teraz zamieniamy zbiór D na D∖αh∪αs i powtarzamy iterację.

Dowód poprawności i skończoności algorytmu.

Przyjmijmy oznaczenia:

Di zbiór wektorów używanych w i-tej iteracji.

Jeżeli proces nie kończy się to, wobec skończoności zbioru wektorów α, dla pewnych k<l otrzymamy Dk=Dl.

Niech r będzie największym indeksem, takim, że wektor αr jest dodawany przy pewnej iteracji Dq a wyrzucany przy iteracji Dp. (k≤q≤l, k≤p≤l). Niech Dp=αi1,αi2,…,αin i β=∑j=1n⁢aij⁢αij.

Zaczynamy q-tą iterację:

ii) Ponieważ nie jesteśmy w przypadku I) wybieramy najmniejszy indeks h spośród i1,i2,…,in taki, że ah<0. Następnie budujemy hiperprzestrzeń H=x⁢|⁢γ∙x=0=l⁢i⁢n⁢D∖αh, gdzie γ tak normalizujemy by γ∙αh=1. Ponieważ αh jest kiedyś dodawany więc h<r. Otrzymujemy γ∙β=ah<0.

iv) Teraz r jest najmniejszym indeksem takim, że γ∙αr<0. Czyli i<r⇒γ∙αi≥0

Reasumując 0>γ∙β=γ∙∑j=1n⁢aij⁢αij=∑j=1n⁢aij⁢γ∙αij≥0 gdyż:

ij<r⇒γ∙αij≥0 oraz aij≥0,

ar<0 i γ∙ar<0,

ij>r⇒γ∙αij=0 bo αij∈Dp∩Dq z wyboru r.

Otrzymaliśmy sprzeczność.

∎

Powyższy dowód poprawności i skończoności algorytmu można znaleźć w [12] Twierdzenie 7.1.

Z fundamentalnego twierdzenia można łatwo wyprowadzić lemat Farkasa, twierdzenia o dualności i twierdzenia strukturalne.

Twierdzenie 10.2

Każdy podzbiór Rn postaci

S=⁢∑i=1t⁢ri⁢pi+∑j=1k⁢sj⁢αj⁢|⁢∑i=1t⁢ri=1,⁢ri≥0,⁢sj≥0 jest wielościanem.

Bez zmniejszenia ogólności możemy przyjąć, że d⁢i⁢m⁢⁢S=n. Niech pi¯=1,pi∈Rn+1 oraz αj¯=0,αj∈Rn+1. Tworzymy stożek S¯={θ+∑i=1tripi¯+∑j=1ksjαj¯;ri≥0,sj≥0}. Niech H={(x0,x1,…,xn)∈Rn+1;x0=1}. Wtedy S≈S¯∩H. Ponadto d⁢i⁢m⁢⁢S¯=d⁢i⁢m⁢⁢S+1=n+1. Na mocy poprzedniego lematu stożek S¯ jest wielościanem więc S też jest wielościanem.

∎
Twierdzenie 10.3

Niech W⊂Rn będzie wielościanem z wierzchołkiem. Niech p1,p2,…,pt będzie zbiorem wszystkich wierzchołków W, oraz α1,α2,…,αk będzie zbiorem wszystkich krawędzi nieskończonych W

S=∑i=1tri⁢pi+∑j=1ksj⁢αj⁢|⁢∑i=1tri=1,ri≥0,sj≥0

Wtedy S=W

1) S⊂W

Niech p=∑i=1tri⁢pi wtedy p∈W, bo W jest wypukły.

Ponieważ każda krawędź zawiera wierzchołek więc ∀j∃i⁢∀t⁢pi+t⁢αj∈W.

Zatem ∀t⁢∀pi⁢pi+tβ∈W

Na mocy poprzedniego lematu

β=∑j=1ksj⁢αj jest wektorem takim, że ∀t⁢p+t⁢β∈W Co daje tezę.

2) W⊂S:

Przypuśćmy, że W≠S i będziemy dochodzić sprzeczności.

Niech q∈W∖S.

S jako wielościan jest zbiorem wypukłym i domkniętym.

Istnieje taka półprzestrzeń  H, że q∈H i S∩H≠∅.

W∩H jest wielościanem zawartym w W, zatem istnieje wierzchołek p wielościanu H∩W. p nie jest wierzchołkiem W, bo S zawierał wszystkie wierzchołki (a nawet krawędzie). p leży na brzegach n liniowo niezależnych półprzestrzeni opisujących W∩H, więc leży na brzegach n-1 półprzestrzeni opisujących W. Stąd p leży na krawędzi W

- sprzeczność.

∎
Twierdzenie 10.4

Jeżeli W jest wielościanem, różnym od zbioru pustego, to istnieją takie punkty p1,p2,…,pt oraz wektory α1,α2,…,αk,

że W=∑i=1tri⁢pi+∑j=1ksj⁢αj⁢|⁢∑i=1tri=1∧ri≥0∧sj≥0.

Niech p będzie punktem wielościanu W. Definiujemy zbiór wektorów

V=α∈Rn⁢|⁢∀r∈R⁢p+r⁢α∈W

.

Zauważmy, że V jest przestrzenią liniową. Wprost z definicji wynika własność α∈V⇒r⁢α∈V. Dodatkowo z własności wielościanów mamy

α∈V⇒∀q∈W⁢q+α∈W

A więc dla α,β∈V zachodzi p+α+β=p+α+β∈W.

Podsumowując

∀α∈V∀q∈W⁢q+α∈W.

Niech S=W∩p+V⊥ będzie wielościanem powstałym z przecięcia W z podprzestrzenią prostopadłą do V. Zbiór S jest niepusty bo zawiera punkt p ale nie zawiera prostej. Zatem S ma wierzchołek i na mocy poprzedniego twierdzenia istnieją takie punkty p1,p2,…,pt oraz wektory α1,α2,…,αk,

że S=∑i=1tri⁢pi+∑j=1ksj⁢αj⁢|⁢∑i=1tri=1∧ri≥0∧sj≥0.

A stąd W=∑i=1tri⁢pi+∑j=1ksj⁢αj⁢+∑z=1maz⁢βz⁢+∑z=1mbz⁢-βz⁢,

gdzie ∑i=1tri=1∧ri≥0∧sj≥0,∧az≥0,∧bz≥0, oraz wektory β1,β2,…,βm tworzą bazę przestrzeni V.

∎
Definicja 10.1

Niech p1,p2,…,pt będzie zbiorem punktów z przestrzeni Rn. Wielościanem klasycznym w Rn nazywamy zbiór:

S=C⁢o⁢n⁢v⁢⁢p1,p2,…,pt=∑i=1tri⁢pi⁢|⁢∑i=1tri=1∧ri≥0

Twierdzenie 10.5

Niech ∅≠W będzie wielościanem w Rn z wierzchołkiem. Wtedy równoważne są warunki:

1)  W jest wielościanem klasycznym.

2)  W jest ograniczony (tzn. ∃p∃rK(p,r)⊃W).

3)  W nie ma krawędzi nieskończonych.

  3)⇒1) - wynika z poprzedniego twierdzenia

1)⇒2) - oczywiste

2)⇒3) - oczywiste.

∎

Metody dowodu i część idei pochodzi z następujących twierdzeń Karatheodory'ego (oryginalnie po grecku - K⁢α⁢ρ⁢α⁢θ⁢ϵ⁢δ⁢ω⁢ρ⁢η, po angielsku - Carathéodory )

Twierdzenie 10.6

Niech q będzie punktem n- wymiarowego stożka

S=p+∑j=1ksj⁢α⁢j|⁢sj≥0

wówczas można przedstawić jako sumę punktu p i co najwyżej n wektorów.

Twierdzenie 10.7

Niech q będzie nieujemnym rozwiązaniem układu t równań liniowych o n zmiennych A⁢X=b. Wówczas z macierzy A można wybrać takie liniowo niezależne kolumny ki1,ki2,…,kit, że układ ki1,ki2,…,kit⁢X=b też ma nieujemne rozwiązanie. ( istnieje niezerowe rozwiązanie bazowe układu A⁢X=b.)

Twierdzenie 10.8

Niech q będzie punktem n- wymiarowego wielościanu

W=∑i=1tri⁢pi+∑j=1ksj⁢αj⁢|⁢∑i=1tri=1,ri≥0,sj≥0.

Wówczas q jest kombinacją wypukłą co najwyżej n+1 punktów i wektorów rozpinających ten wielościan.

Ćwiczenie 10.1

Niech X=2,5,-2,3,1,3,3,7,1,2. Wiedząc, że punkt

1,4∈C⁢o⁢n⁢v⁢⁢X , 1,4=15⁢2,5+15⁢-2,3+15⁢1,3+15⁢3,7+15⁢1,2. Przedstaw 1,4 punkt jako kombinację wypukłą trzech punktów ze zbioru X.

Ćwiczenie 10.2

Niech X=1,3,3,5,5,4 zaś Y=1,1,2,1 Wiedząc, że punkt 1,4=13⁢1,3+13⁢3,5+13⁢5,4+1,2+1,1∈C⁢o⁢n⁢v⁢⁢X+S⁢t⁢⁢Y , przedstaw 1,4 punkt jako kombinację wypukłą trzech elementów ze zbioru X∪Y. ( S⁢t⁢⁢Y=a⁢1,2+b⁢1,1⁢|⁢a,b≥0).

Ćwiczenie 10.3

Wiedząc, że punkt p=1,1,1,1,1 jest dopuszczalnym rozwiązaniem układu A⁢x=b, gdzie A=111122-21015-62-12 i b=622 znajdź wszystkie bazowe rozwiązania dopuszczalne.

Uzasadnij, że otrzymane punkty leżą na jednej płaszczyźnie ale nie są współliniowe -( są wierzchołkami czworokąta).

Przedstaw p=1,1,1,1,1 jako kombinację wypukłą trzech z otrzymanych punktów.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.