Zbiory wypukłe w $\mathbb{R}^{n}$

Rozważmy rodzinę zbiorów wypukłych w $\mathbb{R}^{n}:\big\{A_{\alpha} \subset\mathbb{R}^{n}:\alpha\in \mathcal{A} \big\}$. Wtedy zachodzi takie twierdzenie

4.1   Twierdzenie Przecięcie dowolnej rodziny zbiorów wypukłych i domknię-tych jest zbiorem wypukłym.

$\lhd$ Niech

$$A\,:=\,\underset{\alpha\in \mathcal{A}}{\bigcap} A_{\alpha},$$ (4.1)

i załóżmy, że punkty $a,b\in A$. Wtedy oczywiście dla $\forall \alpha\in \mathcal{A}$, $a,b\in A_{\alpha}$. Ponieważ zbiory $A_{\alpha}, \,\alpha\in \mathcal{A}$ są wypukłe, mamy dla wszystkich
$\alpha\in \mathcal{A}$ $at\,+\,(1-t)b\in A_{\alpha}$, tj. dla $t\in [0,1]$ $at\,+\,(1-t)b\in A$, co dowodzi prawdziwości twierdzenia $\rhd$

4.2   Wniosek Niech $A_{\alpha}=\big\{x\in \mathbb{R}^{n}:<a_{\alpha},x>\leq\beta_{\alpha},\beta_{\alpha}\in \mathbb{R} \big\}$, gdzie $\alpha\in \mathcal{A}$. Wtedy zbiór

$$A\,:=\,\underset{\alpha\in \mathcal{A}}{\bigcap} A_{\alpha}$$ (4.2)

jest wypukły i domknięty, ponieważ każdy zbiór $A_{\alpha}$ jest też wypukły.

4.3   Definicja Zbiór $A\subset\mathbb{R}^{n}$ () nazywamy poliedrem domkniętym.

W przypadku gdy jądra $J(A_{\alpha})\subset A_{\alpha}$ są niepuste oraz przecięcie $J(A)\neq\varnothing$ i $\underset{\alpha\in \mathcal{A}}{\bigcap} J(A_{\alpha})\,supset\,J(A)$, wtedy jądro $J(A)$ jest otwartym i wypukłym zbiorem w $\mathbb{R}^{n}$

4.4   Twierdzenie Jeśli $A\subset\mathbb{R}^{n}$ jest wypukłym zbiorem z niepustym jądrem $J(A)$, wtedy $\overline{J(A)}\,=\,\overline{A}$.

$\lhd$ Ponieważ $J(A)\subset A$, to $\overline{J(A)}\,\subseteq\, \overline{A}$. Niech teraz $a\in J(A)$, $b\in\overline{A}$. Ponieważ każdy punkt odcinka $[a,b)\subset\mathbb{R}^{n}$ należy do $J(A)$, to w każdym sąsie-dztwie punktu $b\in\overline{A}$ istnieją punkty z $J(A)$. To znaczy, że $b\in\overline{J(A)}$, skąd $\overline{J(A)}\,\supseteq\, \overline{A}$, albo $\overline{J(A)}\,=\,\overline{A}$ $\rhd$

4.5   Twierdzenie Caratheodory'ego Niech $S\subset \mathbb{R}^{n}$ będzie niepustym zbiorem. Wtedy każdy punkt z powłoki wypukłej $conv(S)$ jest wypukłą kombinacją liniową $(n+1)$-liczby punktów, lub mniejszej ilości.

4.6   Lemat Radona Każdy zbiór z $(n+2)$ punktów, lub więcej w $\mathbb{R}^{n}$ może być rozdzielony na dwa niepuste podzbiory, wypukłe powłoki które mają wspólny punkt.

$\lhd$ Niech $\big\{\overrightarrow{a_{j}}\in \mathbb{R}^{n}:j=\overline{1,m}, \,m\geq n+2 \big\}$ będą wektorami z $\mathbb{R}^{n}$ parami różnymi. Rozważmy następujący układ równań liniowych:

$$\sum_{j=1}^{m}a_{ji}\xi_{j}\,=\,0,\qquad <e,\xi>\,=\,0,\quad i=\overline{1,n},$$ (4.3)

gdzie $e=(1,\ldots,1)\in \mathbb{R}^{m}, \xi \in \mathbb{R}^{m}$.
Liczba równań w () jest mniejsza niż ilość niewiadomych, tak więc istnieje niezerowy wektor liczb

$$\xi \,=\,(\xi_{1},\xi_{2},\ldots,\xi_{m})\,\in\,\mathbb{R}^{m},$$

wśród których są dodatnie, na przykład $\xi_{j}\geq 0,\,j=\overline{0,\tau}$, oraz ujemne
$\xi_{j}< 0,\,j=\overline{\tau + 1,m}$. Wtedy z () otrzymujemy, że

$$\sum^{\tau}_{j=1}\xi_{j}\,=\,-\sum^{m}_{j=\tau+1}\xi_{j}\,>\,0,$$ (4.4)

gdzie zachodzi nierówność ostra !
Zapiszmy teraz pierwsze $n$ - równań z () w postaci

$$\sum^{\tau}_{i=1}\xi_{i}\boldsymbol{\overrightarrow{a_{i}}}\,+\,\sum^{m}_{j=\tau+1} \xi_{j}\boldsymbol{\overrightarrow{a_{j}}}\,=\,0,$$ (4.5)

skąd

$$\boldsymbol{\overrightarrow{a}}\,:=\,\sum_{i=1}^{\tau}\frac{\xi_{... ... +1}^{m} \Big(-\frac{\xi_{j}}{\xi}\Big)\, \boldsymbol{\overrightarrow{a_{j}}},$$ (4.6)

gdzie

$$\xi\,:=\,\sum_{j=\tau +1 }^{m}\xi_{j}\,>\,0.$$ (4.7)

Wykorzystując (), widzimy z (), że wektor $\overrightarrow{a}\in \mathbb{R}^{n}$ () jest kombinacją wypukłą punktów $\overrightarrow{a_{i}}\in \mathbb{R}^{n},\,i=\overline{1,\tau}$, oraz kombinacją wypukłą wektorów $\overrightarrow{a_{j}}\in \mathbb{R}^{n},\,j=\overline{\tau+1,m}$.
To znaczy, że $\overrightarrow{a}\in conv(\overrightarrow{a_{1}},\ldots, \overrightarrow{a_{\tau}})\,\cap\,conv(\overrightarrow{a_{\tau + 1}},\ldots, \overrightarrow{a_{m}})$, co dowodzi lemat $\rhd$
Dowód twierdzenia Caratheodory'ego:

$\lhd$ Dla każdego punktu $\overrightarrow{x}\in conv(S)$ istnieją wektory $\overrightarrow{x_{j}}\in S,\,j=\overline{1,m}$, takie, że

$$\overrightarrow{x}\,=\,\sum^{m}_{j=1}\lambda_{j}x_{j},\qquad \lambda_{j}\,\geq\,0, \quad \sum^{m}_{j=1}\lambda_{j}\,=\,1.$$ (4.8)

Jeśli $m\leq n+1$, to twierdzenie jest już udowodnione.
Gdy $m\geq n+2$, to dla $\overrightarrow{x}\in conv(S)$ spełnione są warunki lematu Radona, tj. istnieje liczba $\tau\in \mathbb{Z}_{+}$, taka że zbiory $S_{+}=\big\{\overrightarrow{x_{1}},\ldots,\overrightarrow{x_{\tau}} \big\}$ i $S_{-}=\big\{\overrightarrow{x_{\tau +1 }},\ldots, \overrightarrow{x_{m}}\big\}$ są rozłączne oraz istnieje taki punkt $\overrightarrow{y}\in conv(S_{+})\,\cap\,conv(S_{-})$, tj.

$$\overrightarrow{y}\,=\,\sum^{\tau}_{j=1}\alpha_{j}\overrightarrow{x_{j}}\,=\, \sum^{m}_{j=\tau +1}\alpha_{j}\overrightarrow{x_{j}},$$ (4.9)

gdzie $\alpha_{j}\geq 0,\,\sum^{\tau}_{j=1}\alpha_{j}\,=\,1\,=\, \sum^{m}_{j=\tau +1}\alpha_{j}$. Niech $\alpha_{j}>0$ dla $j=\overline{\tau +1,m}$. Wtedy wśród liczb dodatnich $\gamma_{j}=\lambda_{j}/\alpha_{j},\,j=\overline{\tau +1,m}$, istnieje najmniejsza, tj. niech $\gamma := min\big\{\lambda_{j}/ \alpha_{j}: j=\overline{\tau +1,m} \big\}\,\Longrightarrow$ równa na przykład liczbie $\lambda_{m}/\alpha_{m}$
Wówczas mamy:

$$\boldsymbol{\overrightarrow{x}}\,=\,\sum^{\tau}_{i=1}(\lambda_{i}... ...\tau +1}(\lambda_{i}\,-\,\gamma\alpha_{j})\boldsymbol{\overrightarrow{x_{j}}},$$ (4.10)

gdzie wszystkie liczby $(\lambda_{i}\,-\,\gamma\alpha_{j})\geq 0,\,j=\overline{\tau +1,m}$. To znaczy oczywiście, że wektor $\overrightarrow{x}\in conv(S)$ jest przedstawiony w postaci nieujemnej kombinacji liniowej punktów $\big\{x_{j}\in S: j=\overline{1,m} \big\}$. Ponieważ liczba $\lambda_{m}\,-\,\gamma\alpha_{m}\equiv 0$, to z () mamy, że

$$\boldsymbol{\overrightarrow{x}}\,=\,\sum^{\tau}_{i=1}(\lambda_{i}... ...\tau +1}(\lambda_{i}\,-\,\gamma\alpha_{j})\boldsymbol{\overrightarrow{x_{j}}},$$ (4.11)

tj. $\overrightarrow{x}\in conv(S\setminus \{x_{m}\})$ co przeczy założeniu $\overrightarrow{x}\in conv(S)\setminus conv(S\setminus \{x_{m}\})$. Tak więc zawsze istnieją punkty $\overrightarrow{x_{j}}\in S,\,j=\overline{1,m+1}$, że
$\overrightarrow{x}\in conv\Big(\big\{\overrightarrow{x_{j}}\in S : j=\overline{1,m+1} \big\}\Big)$, co dowodzi twierdzenie $\rhd$
Stosownie do zastosowań obrzarów wypukłych, najczęściej cytowanym jest twierdzenie Helley'a (1913)

4.7   Twierdzenie Helley'a Niech $S$ będzie skończoną rodziną podzbiorów wypukłych w $\mathbb{R}^{n}$, złożoną z nie mniej niż $(n+1)$ zbiorów. Jeśli każde z $(n+1)$ zbiorów z tej rodziny mają punkt wspólny, to istnieje punkt wspólny dla wszystkich zbiorów z rodziny $S$ Twierdzenie zachodzi też kiedy rodzina $S$ jest nieskończona, a wszystkie zbiory z $S$ są domknięte i chociaż jeden zbiór jest zwarty.

$\lhd$ Niech rodzina $S$ zawiera w sobie $m\geq n+1$ zbiorów wypukłych $V_{j}\in S$, $j=\overline{1,m}$. Stosujemy metodę indukcji matematycznej:

$$S\,=\,\big\{V_{j}\in \mathbb{R}^{n}:\, j=\overline{1,m} \big\},\quad m\geq n+1.$$

Przypuszczamy, że twierdzenie jest prawdziwe dla dowolnej rodziny $(m-1)$ zbiorów, $m-1\geq n+1$, a nasza rodzina ma $m\geq n+1$ zbiorów. Niech $S_{j}$ jest rodziną zbiorów wypukłych, otrzymaną z $S$ za wyjątkiem zbioru $V_{j}$ :

$$S_{j}\,=\,\big\{ V_{i}\in S :i\neq j,\,i=\overline{1,m}, j=\overline{1,m}\big\}$$

Na mocy indukcji rodzina $S_{j}$ ma dokładnie $(m-1)$ zbiorów, tj. dla każdego $j=\overline{1,m}$ istnieje punkt $p_{j}\in \bigcap_{i\neq j}^{m} V_{i},\,j=\overline{1,m}$. Do zbioru wektorów
$\big\{p_{1},p_{2},\ldots,p_{m}\in \mathbb{R}^{m}\big\}$ można zastosować twierdzenie Radona, ponieważ
$m\geq n+2$. Wtedy istnieją dwa niepuste podzbiory $\big\{p_{1},\ldots,p_{\tau}\big\}$ oraz
$\big\{p_{\tau +1 }, \ldots,p_{m}\big\}$, takie że przecięcie $conv\Big(\big\{p_{1},\ldots,p_{\tau}\big\}\Big)\,\cap\,conv\Big(\big\{p_{\tau +1 }, \ldots,p_{m}\big\}\Big)$ jest niepuste! Niech wówczas $p\in conv\Big(\big\{p_{1},\ldots,p_{\tau}\big\}\Big)\,\cap\,conv\Big(\big\{p_{\tau +1 }, \ldots,p_{m}\big\}\Big)$. Ponieważ $p_{1},\ldots,p_{\tau}\in V_{j}$, gdzie $j=\overline{\tau +1,m}$,
to $conv\{p_{1},\ldots,p_{\tau}\}\subseteq V_{\tau+1}\cap\ldots \cap V_{m}$.
Podobnie $conv\{p_{\tau +1},\ldots,p_{m}\}\subseteq V_{1}\cap\ldots \cap V_{\tau}$.
Tak więc $p\in %%\cap V_{2} conv\Big(\big\{p_{1},\ldots,p_{\tau}\big\}\Big)\,\cap\,conv... ...big\{p_{\tau +1 }, \ldots,p_{m}\big\}\Big)\,\subseteq\,\bigcap^{m}_{j=1}V_{j}$,
co należało dowieść $\rhd$

$\lhd$ W przypadku gdy rodzina $S$ jest nieskończona, $S=\big\{V_{j}\subset \mathbb{R}^{n} :j\in \mathbb{Z}_{+} \big\}$, $V_{j}=\overline{V}_{j},\,j\in \mathbb{Z}_{+}$, przypuśćmy, że $V_{0}=\overline{V}_{0}$ jest zbiorem zwartym. Wtedy jeżeli z $S$ wybierzemy dowolną skończoną podrodzinę $\big\{V_{j_{k}}:k=\overline{1,s},\,s\geq n+1 \big\}$, to na mocy Tw. Helley'a dla skończonej rodziny zbiorów wypukłych przecięcie

$$\bigcap_{k=1}^{s}\,\big(V_{0}\,\cap\,V_{j_{k}}\big)\,\neq\,\varnothing$$

jest niepuste! Tak więc rodzina wszystkich zbiorów

$$F_{j}\,=\,V_{0}\,\cap\,V_{j},\qquad j\in \mathbb{Z}_{+},$$

stanowi rodzinę centrowaną podzbiorów domkniętych i wypukłych w zbiorze $V_{0}$! Ponieważ zbiór $V_{0}\subset \mathbb{R}^{n}$ jest zwarty, otrzymujemy natychmiast, że $\underset{j\in \mathbb{Z}_{+}}{\bigcap}F_{j}\neq \varnothing$. Ale wówczas też $\underset{j\in \mathbb{Z}_{+}}{\bigcap}V_{j}\neq \varnothing$ $\rhd$

Jako ciekawy dla zastosowań wniosek sformułujemy następujące twierdzenie.

4.8   Twierdzenie Jeżeli zbiór wypukły jest pokryty przy pomocy otwartych lub domkniętych półprzestrzeni $P_{j}$, gdzie $z\in \mathbb{Z}_{+}$ jest skończone! Wtedy ten zbiór jest pokryty przy pomocy jakichkolwiek $(n+1)$ lub mniej z tych półprzestrzeni.

$\lhd$ Niech teraz zbiór $V \subset \mathbb{R}^{n}$ jest taki, że $\bigcup_{j=1}^{s}P_{j}\supset V,\,s<\infty$. Odpowiednie dopełnienia $Q_{j}=\mathbb{R}^{n}\setminus P_{j},\,j=\overline{1,s}$, są też półprzestrzeniami w $\mathbb{R}^{n}$, i przecięcia $V_{j}:=V\cap Q_{j}$ są wypukłymi zbiorami. Odpowiednie przecięcie $\bigcap_{j=1}^{s} V_{j}=\varnothing$, ponieważ $V\subset \bigcup^{s}_{j=1}P_{j}$:

$$\bigcap_{j=1}^{s}V_{j}\,=\,\bigcap_{j=1}^{s}V \cap\big(\mathbb{R... ...nus P_{j}\,=\,V\setminus \big(\bigcup^{s}_{j=1}P_{j} \big)\,=\,\varnothing .$$

Stąd na mocy Tw. Helley'a koniecznie istnieje nie mniej niż $(n+1)$ zbiorów $V_{j_{k}},\,k=\overline{1,n+1}$, takich których przecięcie jest również puste.
Wtedy oczywiście półprzestrzenie $P_{j_{k}},\, k=\overline{1,n+1}$, pokrywają zbiór $V$, tj. $V\subset \bigcup^{n+1}_{k=1}P_{j_{k}}$, ponieważ $\,\,\bigcap^{n+1}_{k=1}V_{j_{k}}=V \setminus \big(\bigcup^{s}_{k=1}P_{j_{k}} \big)=\varnothing$ $\rhd$