Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja I – 10. Twierdzenia strukturalne 2 – MIM UW

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 \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.

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.