Zagadnienia

10.1 Twierdzenia strukturalne 2

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 $\alpha _{1},\alpha _{2},...,\alpha _{t}$ będą wektorami. Wówczas zbiór $S=\{\sum _{{i=1}}^{t}\ r_{i}\alpha _{i}\ |\ r_{i}\geq 0\}$ jest wielościanem.

Niech $dim\, S=n$ . Dzięki twierdzeniu 2.4 bez zmniejszenia ogólności możemy przyjąć, że $S\subset\mathbb{R}^{n}$ .

Wybieramy wszystkie wektory $\gamma\in\mathbb{R}^{n}$ spełniające warunki:

1) $\forall _{{1\leq i\leq t}}\ \ \alpha _{{i}}\bullet\gamma\leq 0$ .

2) Istnieje $n-1$ liniowo niezależnych wektorów $\alpha _{{i_{1}}},\alpha _{{i_{2}}},...,\alpha _{{i_{{n-1}}}}$ w zbiorze $\{\alpha _{1},\alpha _{2},...,\alpha _{t}\}$ , takich że $\forall _{{1\leq j<n}}\ \ \alpha _{{i_{{j}}}}\bullet\gamma=0$ .

3) $\ \gamma\bullet\gamma=1$

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

Niech $W=\bigcap _{{\,\gamma}}\ H_{{\gamma}}$ , gdzie $H_{{\gamma}}=\{ x\in R^{n}\ |\ x\bullet\gamma\leq 0\}$ . Pokażemy teraz, że $S=W$ .

Z warunku 1) wynika inkluzja $S\subset W$ .

Niech $b\notin S$ . Badamy zadanie

$Max\ x_{0}=b\bullet x$

$\forall _{{1\leq i\leq t}}\ \ \alpha _{{i}}\bullet x\leq 0$ .

Ponieważ wektory $\alpha _{i}$ rozpinają przestrzeń $\mathbb{R}^{n}$ więc obszar dopuszczalny jest wielościanem o jedynym wierzchołku $p=\theta$ . Warunek $b\notin 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 $\gamma$ będzie unormowanym wektorem kierunkowym tej krawędzi. Wówczas:

1) $\gamma\in W$ implikuje $\forall _{{1\leq i\leq t}}\ \alpha _{{i}}\bullet\gamma\leq 0$ .

2) $\gamma$ jest wektorem krawędzi więc istnieje $n-1$ liniowo niezależnych półprzestrzeni opisujących - wektorów $\alpha _{{i_{1}}},\alpha _{{i_{2}}},...,\alpha _{{i_{{n-1}}}}$ w zbiorze $\{\alpha _{1},\alpha _{2},...,\alpha _{t}\}$ , takich że $\forall _{{1\leq j<n}}\ \ \alpha _{{i_{{j}}}}\bullet\gamma=0$ .

3) $\gamma\bullet\gamma=1$ .

Dodatkowo $\gamma\bullet b\geq 0$ więc $b\notin H_{{\gamma}}$ a zatem również $b\notin 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 $\alpha _{1},\alpha _{2},...,\alpha _{t}$ i $\beta$ będą wektorami z przestrzeni $\mathbb{R}^{n}$ . Wówczas albo:

I) $\beta$ jest nieujemną kombinacją liniową liniowo niezależnych wektorów z $\alpha _{1},\alpha _{2},...,\alpha _{t}$ .

albo

II) Istnieje hiperprzestrzeń $V=\{ x\in\mathbb{R}^{n}\ |\ \gamma\bullet x=0\}$ , zawierająca $m-1$ liniowo niezależnych wektorów z $\alpha _{1},\alpha _{2},...,\alpha _{t}$ takich,

że $\gamma\bullet\beta<0$ i $\gamma\bullet\alpha _{1}\geq 0,\gamma\bullet\alpha _{2}\geq 0,...,\gamma\bullet\alpha _{t}\geq 0$ ,

gdzie $m=dim\, lin\{\alpha _{1},\alpha _{2},...,\alpha _{t},\beta\}$ .

Algorytm szukania hiperprzestrzeni.

Krok 1. Jeżeli $\beta\not\in lin\{\alpha _{1},\alpha _{2},...,\alpha _{t}\}$ to jako $V$ można wziąć dowolną hiperprzestrzeń zawierającą $lin\{\alpha _{1},\alpha _{2},...,\alpha _{t}\}$ i nie zawierającą $\beta$ .

Krok 2. Przyjmijmy, że $\mathbb{R}^{n}=lin\{\alpha _{1},\alpha _{2},...,\alpha _{t}\}$ . Wybieramy dowolny liniowo niezależny podzbiór $D=\{\alpha _{{i_{1}}},\alpha _{{i_{2}}},...,\alpha _{{i_{n}}}\}$ z wektorów $\alpha _{1},\alpha _{2},...,\alpha _{t}$ .

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

i) Zapisujemy $\beta=\sum _{{j=1}}^{n}\ a_{{i_{j}}}\alpha _{{i_{j}}}$ . Jeżeli $a_{{i_{1}}},a_{{i_{2}}},...,a_{{i_{n}}}\geq 0$ to stop jesteśmy w przypadku I).

ii) W przeciwnym przypadku wybieramy najmniejszy indeks $h$ spośród $i_{1},i_{2},...,i_{n}$ taki,

że $a_{h}<0$ . Następnie budujemy hiperprzestrzeń $H=\{ x\ |\ \gamma\bullet x=0\}=lin(D\setminus\{\alpha _{h}\})$ ,

gdzie $\gamma$ tak normalizujemy by $\gamma\bullet\alpha _{h}=1$ . (Wtedy $\gamma\bullet\beta=a_{h}<0$ ).

iii) Jeżeli $\gamma\bullet\alpha _{1}\geq 0,\gamma\bullet\alpha _{2}\geq 0,...,\gamma\bullet\alpha _{t}\geq 0$ jesteśmy w przypadku II).

iv) W przeciwnym przypadku wybieramy najmniejszy indeks $s$ taki, że $\gamma\bullet\alpha _{s}<0$ .

Teraz zamieniamy zbiór $D$ na $\left(D\setminus\{\alpha _{h}\}\right)\cup\{\alpha _{s}\}$ i powtarzamy iterację.

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

Przyjmijmy oznaczenia:

$D_{i}$ 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 $\alpha$ , dla pewnych $k<l$ otrzymamy $D_{k}=D_{l}$ .

Niech $r$ będzie największym indeksem, takim, że wektor $\alpha _{r}$ jest dodawany przy pewnej iteracji $D_{q}$ a wyrzucany przy iteracji $D_{p}$ . ( $k\leq q\leq l$ , $k\leq p\leq l$ ). Niech $D_{p}=\{\alpha _{{i_{1}}},\alpha _{{i_{2}}},...,\alpha _{{i_{n}}}\}$ i $\beta=\sum _{{j=1}}^{n}\, a_{{i_{j}}}\alpha _{{i_{j}}}$ .

Zaczynamy q-tą iterację:

ii) Ponieważ nie jesteśmy w przypadku I) wybieramy najmniejszy indeks $h$ spośród $i_{1},i_{2},...,i_{n}$ taki, że $a_{h}<0$ . Następnie budujemy hiperprzestrzeń $H=\{ x\ |\ \gamma\bullet x=0\}=lin(D\setminus\{\alpha _{h}\})$ , gdzie $\gamma$ tak normalizujemy by $\gamma\bullet\alpha _{h}=1$ . Ponieważ $\alpha _{h}$ jest kiedyś dodawany więc $h<r$ . Otrzymujemy $\gamma\bullet\beta=a_{h}<0$ .

iv) Teraz $r$ jest najmniejszym indeksem takim, że $\gamma\bullet\alpha _{r}<0$ . Czyli $i<r\Rightarrow\gamma\bullet\alpha _{i}\geq 0$

Reasumując $0>\gamma\bullet\beta=\gamma\bullet\left(\sum _{{j=1}}^{n}\ a_{{i_{j}}}\alpha _{{i_{j}}}\right)=\sum _{{j=1}}^{n}\ a_{{i_{j}}}\gamma\bullet\alpha _{{i_{j}}}\geq 0$ gdyż:

$i_{j}<r\Rightarrow\gamma\bullet\alpha _{{i_{j}}}\geq 0$ oraz $a_{{i_{j}}}\geq 0$ ,

$a_{r}<0$ i $\gamma\bullet a_{r}<0$ ,

$i_{j}>r\Rightarrow\gamma\bullet\alpha _{{i_{j}}}=0$ bo $\alpha _{{i_{j}}}\in D_{p}\cap D_{q}$ 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 $R^{n}$ postaci

$S=\{\ \sum _{{i=1}}^{t}\ r_{i}p_{i}+\sum _{{j=1}}^{k}\ s_{j}\alpha _{j}\ |\ \sum _{{i=1}}^{t}\ r_{i}=1,\ r_{i}\geq 0,\ s_{j}\geq 0\}$ jest wielościanem.

Bez zmniejszenia ogólności możemy przyjąć, że $dim\ S=n$ . Niech $\overline{p_{i}}=(1,p_{i})\in R^{{n+1}}$ oraz $\overline{\alpha _{j}}=(0,\alpha _{j})\in R^{{n+1}}$ . Tworzymy stożek $\overline{S}=\{\theta+\sum _{{i=1}}^{t}\ r_{i}\overline{p_{i}}+\sum _{{j=1}}^{k}\ s_{j}\overline{\alpha _{j}}\ ;\ \ r_{i}\geq 0,\ s_{j}\geq 0\}$ . Niech $H=\{(x_{0},x_{1},...,x_{n})\in R^{{n+1}}\ ;\ x_{0}=1\}$ . Wtedy $S\approx\overline{S}\cap H$ . Ponadto $dim\ \overline{S}=dim\ S+1=n+1$ . Na mocy poprzedniego lematu stożek $\overline{S}$ jest wielościanem więc $S$ też jest wielościanem.

∎

Twierdzenie 10.3

Niech $W\subset R^{{n}}$ będzie wielościanem z wierzchołkiem. Niech $p_{{1}},p_{{2}},...,p_{{t}}$ będzie zbiorem wszystkich wierzchołków $W$ , oraz $\alpha _{{1}},\alpha _{{2}},...,\alpha _{{k}}$ będzie zbiorem wszystkich krawędzi nieskończonych $W$

$S=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\,|\ \sum _{{i=1}}^{{t}}r_{{i}}=1,r_{{i}}\geq 0,s_{{j}}\geq 0\right\}$

Wtedy $S=W$

1) $S\subset W$

Niech $p=\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}$ wtedy $p\in W$ , bo $W$ jest wypukły.

Ponieważ każda krawędź zawiera wierzchołek więc $\forall _{j}\exists _{{i}}\quad\forall _{{t}}\quad p_{{i}}+t\alpha _{j}\in W$ .

Zatem $\forall _{{t}}\quad\forall _{{p_{i}}}\quad p_{i}+t_{{\beta}}\in W$

Na mocy poprzedniego lematu

$\beta=\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}$ jest wektorem takim, że $\forall _{{t}}\quad p+t\beta\in W$ Co daje tezę.

2) $W\subset S$ :

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

Niech $q\in W\setminus S$ .

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

Istnieje taka półprzestrzeń $H$ , że $q\in H$ i $S\cap H\neq\emptyset$ .

$W\cap H$ jest wielościanem zawartym w $W$ , zatem istnieje wierzchołek $p$ wielościanu $H\cap 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\cap 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 $p_{{1}},p_{{2}},...,p_{{t}}$ oraz wektory $\alpha _{{1}},\alpha _{{2}},...,\alpha _{{k}}$ ,

że $W=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\ |\ \sum _{{i=1}}^{{t}}r_{{i}}=1\wedge r_{{i}}\geq 0\wedge s_{{j}}\geq 0\right\}$ .

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

$V=\{\alpha\in\mathbb{R}^{n}\ |\ \forall _{{r\in\mathbb{R}}}\ p+r\alpha\in W\}$

Zauważmy, że $V$ jest przestrzenią liniową. Wprost z definicji wynika własność $\alpha\in V\Rightarrow r\alpha\in V$ . Dodatkowo z własności wielościanów mamy

$\alpha\in V\Rightarrow\forall _{{q\in W}}\ q+\alpha\in W$

A więc dla $\alpha,\beta\in V$ zachodzi $p+(\alpha+\beta)=(p+\alpha)+\beta\in W$ .

Podsumowując

$\forall _{{\alpha\in V}}\forall _{{q\in W}}\ q+\alpha\in W.$

Niech $S=W\cap\left(p+V^{\bot}\right)$ 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 $p_{{1}},p_{{2}},...,p_{{t}}$ oraz wektory $\alpha _{{1}},\alpha _{{2}},...,\alpha _{{k}}$ ,

że $S=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\ |\ \sum _{{i=1}}^{{t}}r_{{i}}=1\wedge r_{{i}}\geq 0\wedge s_{{j}}\geq 0\right\}$ .

A stąd $W=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\ +\sum _{{z=1}}^{{m}}a_{{z}}\beta _{{z}}\ +\sum _{{z=1}}^{{m}}b_{{z}}(-\beta _{{z}})\ \right\}$ ,

gdzie $\sum _{{i=1}}^{{t}}r_{{i}}=1\wedge r_{{i}}\geq 0\wedge s_{{j}}\geq 0,\wedge a_{{z}}\geq 0,\wedge b_{{z}}\geq 0$ , oraz wektory $\beta _{{1}},\beta _{{2}},...,\beta _{{m}}$ tworzą bazę przestrzeni $V$ .

∎

Definicja 10.1

Niech $\{ p_{1},p_{2},...,p_{t}\}$ będzie zbiorem punktów z przestrzeni $R^{n}$ . Wielościanem klasycznym w $R^{{n}}$ nazywamy zbiór:

$S=Conv\ \{ p_{1},p_{2},...,p_{t}\}=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}\ |\ \sum _{{i=1}}^{{t}}r_{{i}}=1\wedge r_{{i}}\geq 0\right\}$

Twierdzenie 10.5

Niech $\emptyset\neq W$ będzie wielościanem w $R^{{n}}$ z wierzchołkiem. Wtedy równoważne są warunki:

1) W jest wielościanem klasycznym.

2) W jest ograniczony $($ tzn. $\exists _{{p}}\quad\exists _{{r}}\quad K(p,r)\supset W)$ .

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

$\ \ 3)\Rightarrow 1)$ - wynika z poprzedniego twierdzenia

$\qquad\qquad 1)\Rightarrow 2)$ - oczywiste

$\qquad\qquad 2)\Rightarrow 3)$ - oczywiste.

∎

Metody dowodu i część idei pochodzi z następujących twierdzeń Karatheodory'ego (oryginalnie po grecku - $K\alpha\rho\alpha\theta\epsilon\delta\omega\rho\eta$ , po angielsku - Carathéodory )

Twierdzenie 10.6

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

$S=\left\{ p+\sum _{{j=1}}^{{k}}s_{{j}}\alpha{}_{{j}}\ |\ s_{{j}}\geq 0\right\}$

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 $AX=b$ . Wówczas z macierzy $A$ można wybrać takie liniowo niezależne kolumny $[k_{{i_{{1}}}},k_{{i_{{2}}}},...,k_{{i_{{t}}}}]$ , że układ $[k_{{i_{{1}}}},k_{{i_{{2}}}},...,k_{{i_{{t}}}}]X=b$ też ma nieujemne rozwiązanie. ( istnieje niezerowe rozwiązanie bazowe układu $AX=b$ .)

Twierdzenie 10.8

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

$W=\left\{\sum _{{i=1}}^{{t}}r_{{i}}p_{{i}}+\sum _{{j=1}}^{{k}}s_{{j}}\alpha _{{j}}\,|\ \sum _{{i=1}}^{{t}}r_{{i}}=1,r_{{i}}\geq 0,s_{{j}}\geq 0\right\}$ .

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=\{\left(2,5\right),\left(-2,3\right),\left(1,3\right),\left(3,7\right),\left(1,2\right)\}$ . Wiedząc, że punkt

$(1,4)\in Conv\, X$ , $\left(1,4\right)=\frac{1}{5}\left(2,5\right)+\frac{1}{5}\left(-2,3\right)+\frac{1}{5}\left(1,3\right)+\frac{1}{5}\left(3,7\right)+\frac{1}{5}\left(1,2\right)$ . Przedstaw $(1,4)$ punkt jako kombinację wypukłą trzech punktów ze zbioru $X$ .

Ćwiczenie 10.2

Niech $X=\{\left(1,3\right),\left(3,5\right),\left(5,4\right)\}$ zaś $Y=\{\left(1,1\right),\left(2,1\right)\}$ Wiedząc, że punkt $(1,4)=\frac{1}{3}\left(1,3\right)+\frac{1}{3}\left(3,5\right)+\frac{1}{3}\left(5,4\right)+\left(1,2\right)+\left(1,1\right)\in Conv\, X+St\, Y$ , przedstaw $(1,4)$ punkt jako kombinację wypukłą trzech elementów ze zbioru $X\cup Y$ . ( $St\, Y=\{ a\left(1,2\right)+b\left(1,1\right)\;|\; a,b\geq 0\}$ ).

Ćwiczenie 10.3

Wiedząc, że punkt $p=(1,1,1,1,1)$ jest dopuszczalnym rozwiązaniem układu $Ax=b$ , gdzie $A=\left[\begin{array}[]{ccccc}1&1&1&1&2\\ 2&-2&1&0&1\\ 5&-6&2&-1&2\end{array}\right]$ i $b=\left[\begin{array}[]{c}6\\ 2\\ 2\end{array}\right]$ znajdź wszystkie bazowe rozwiązania dopuszczalne.