Powłoki wypukłe zbiorów

Definicja 7.1   Mówimy, że podzbiór $W \subset {\bf R}^n$ jest wypukły ^7.3 jeżeli dla każdych dwóch elementów $x \in W$ i $y \in W$ odcinek je łączący:

$$[x,y]= \{ \alpha x+ \beta y: \alpha , \beta \geq 0, \alpha + \beta =1\}$$

jest zawarty w $W$.

Przykład 7.3   Jest oczywistym, że jedynymi podzbiorami wypukłymi ${\bf R}$ sa przedziały.
W ${\bf R}^2$ zbiory $S_1$ i $S_2$ przedstawione na rysunku 7.3.1 są wypukłe, zaś $S_3$ nie jest zbiorem wypukłym.

Banalnie prosty do udowodnienia jest następujący wniosek którego dowód wobec tego pozostawiamy czytelnikowi.

Wniosek 7.1   Niech $\{ W_i: i \in I\}$ będzie rodziną zbiorów wypukłych. Wtedy przecięcie $\bigcap_{i\in I}W_i$ jest także zbiorem wypukłym.$\Box$

Wniosek , jakkolwiek by nie był prosty do udowodnienia jest odpowiedzialny za bardzo ważne pojęcie powłoki wypukłej zbioru.

Definicja 7.2   Niech $X$ będzie dowolnym podzbiorem ${\bf R}^n$. Powłoką wypukłą $X$ nazywamy najmniejszy (w sensie zawierania zbiorów) zbiór wypukły $W \subset {\bf R}^n$ zawierający $X$. Piszemy wtedy

$$W = conv(X)$$

Przykład 7.4   Dla zbioru $S_3$ z rysunku 7.3.1 powłoka wypukła przedstawiona jest na rysunku 7.3.2.

Wniosek 7.2   Niech $X$ będzie dowolnym zbiorem zawartym w ${\bf R}^n$ i niech $\cal{W}$ będzie rodziną wszystkich zbiorów wypukłych zawierających $X$. Wtedy

$$conv(X) = \bigcap_{W \in \cal{W}}W$$

Dowód. Ponieważ $conv(X) \in \cal{W}$ $\bigcup_{W\in\cal{W}}W \subset conv(X)$. Z drugiej strony, skoro $conv(X)$ jest najmniejszym, w sensie zawierania zbiorów, zbiorem wypukłym zawierającym $X$, zachodzi $conv(X) \subset W$ dla każdego $W \in \cal{W}$. Stąd zaś $conv(X) \subset \bigcap_{W \in \cal{W}}W$.

Wniosek 7.3   Dla dowolnego zbioru $X \subset {\bf R}^n$ zachodzi związek $conv(X)=\{\alpha_1{\bf v}_1 + ... + \alpha_k{\bf v}_k: k \in {\bf N};{\bf v}_1... ..., {\bf v}_k \in X; \alpha_1,..., \alpha_k \geq 0; \alpha_1+...+\alpha_k =1\}$.

Dowód. Jest oczywiste, że zbiór $A=\{\alpha_1{\bf v}_1 + ... + \alpha_k{\bf v}_k: k \in {\bf N};{\bf v}_1,..., {\bf v}_k \in X; \alpha_1,...,\alpha_k \geq 0;\alpha_1+...+\alpha_k =1\}$ zawiera $X$ (aby otrzymać wszystkie elementy zbioru $X$ wystarczy położyć we wzorze na $A$ $k=1$ i $\alpha_1 =1$).
Łatwo także wykazać, że $A$ jest zbiorem wypukłym. Rzeczywiście, weźmy ${\bf u,v}\in A$. Wykażemy, że dla wszystkich $\alpha , \beta \in {\bf R}, \alpha ,\beta \geq 0$ i takich, że $\alpha + \beta =1$, $\alpha {\bf u} + \beta {\bf v} \in A$.
Skoro ${\bf u,v}\in A$, to istnieją $k,l \in {\bf N}$ oraz $\alpha_1,...,\alpha_k, \beta_1,..., \beta_l \geq 0$ oraz ${\bf u}_1,...,{\bf u}_k,{\bf v}_1,...,{\bf v}_l \in X$ takie, że $\alpha_1+...+\alpha_k=\beta_1+...+\beta_l=1$ i $u=\alpha_1{\bf u}_1+...+\alpha_k{\bf u}_k, v=\beta_1{\bf v}_1+...+\beta_l{\bf v}_l$.
Wtedy

$\alpha {\bf u} + \beta {\bf v} = \alpha (\alpha_1 {\bf u}_1+...+\alpha_k{\bf u}... .....+\alpha \alpha_k{\bf u}_k+\beta \beta_1{\bf v}_1+...+ \beta \beta_l{\bf v}_l$

Tak więc $\alpha {\bf u} + \beta {\bf v}$ jest kombinacją wektorów ${\bf u}_1,...,{\bf u}_k,{\bf v}_1,...,{\bf v}_l \in X$. Co więcej, współczynniki tej kombinacji są oczywiście nieujemne i $\alpha \alpha_1+...+\alpha \alpha_k + \beta \beta_1 + ... + \beta \beta_l = \alpha (\alpha_1+...+\alpha_k)+ \beta (\beta_1 + ... \beta_l ) = \alpha + \beta =1$. Czyli $\alpha {\bf u} + \beta {\bf v} \in A.$
Dla udowodnienia prawdziwości wniosku pozostaje jeszcze wykazać, że A jest najmniejszym zbiorem wypukłym zawierającym X czyli, że dla każdego zbioru wypukłego $W$ zawierającego $X$ zachodzi $A \subset W$.
Niech $W$ będzie zbiorem wypukłym, $W\supset X$ i niech ${\bf u}\in A$. Istnieją wobec tego $k\geq 1(k\in{\bf N}), {\bf u}_1,...,{\bf u}_k \in X, \alpha_1,...,\alpha_k \geq 0,$ takie, że $\alpha_1+ ... + \alpha_k =1$ i ${\bf u}=\alpha_1{\bf u}_1+...+\alpha_k{\bf u}_k$. Korzystając z indukcji matematycznej ze względu na $k$ wykażemy, że ${\bf u} \in W$.
Dla $k=1$ zachodzi uczywiście $u \in X$ i wobec $W\supset X$ zachodzi także $u \in W$. Przypuśćmy, że $k>1$ i nasza teza jest prawdą dla $k-1$, to znaczy że każda kombinacja $\beta_1{\bf v}_1+...+\beta_{k-1}{\bf v}_{k-1}$ w której ${\bf v}_1,...,{\bf v}_{k-1} \nolinebreak \in X,\linebreak \nolinebreak \alpha_1,...,\alpha_k\geq 0, \alpha_1+...+\alpha_k = 1$, należy do $W$.
Możemy założyć, że $\alpha_k \neq 1$ (w przeciwnym przypadku ${\bf u}=1{\bf u}_k={\bf u}_k \in X$). Mamy

$$u=\alpha_1{\bf u}_1+...+\alpha_{k-1}{\bf u}_{k-1}+\alpha_k{\bf u}_k =$$

$$(1-\alpha_k) (\frac{\alpha_1}{1-\alpha_k} {\bf u}_1+...+\frac{\alpha_{k-1}}{1-\alpha_k}{\bf u}_{k-1})+\alpha_k{\bf u}_k$$

Oczywiście $\frac{\alpha_i}{1-\alpha_k} \geq 0$ dla $i=1,...,k-1$. Co więcej,

$$\frac{\alpha_1}{1-\alpha_k}+...+\frac{\alpha_{k-1}}{1-\alpha_... .... +\alpha_{k-1}}{1-\alpha_k}= \frac{1-\alpha_k}{1-\alpha_k}=1$$

Stąd i z założenia indukcyjnego ${\bf v}=\frac{\alpha_1}{1-\alpha_k}{\bf u}_1+...+\frac{\alpha_{k-1}}{1-\alpha_k}{\bf u}_{k-1} \in W$.
Ponieważ $W$ jest z założenia zbiorem wypukłym

$${\bf u}=(1-\alpha_k){\bf v}+\alpha_k{\bf u}_k \in W$$

co kończy dowód wniosku . Wniosek posłuży nam do wykazania poniżej twierdzenia Carathéodory'ego które mówi, że w przestrzeni $n$ wymiarowej $k$ we wniosku można zastąpić przez $n+1$.

Twierdzenie 7.4 (Carathéodory)   Dla dowolnego zbioru $X \subset {\bf R}^n$ zachodzi związek

$$conv(X) = \{ \alpha_1{\bf v}_1+ ... \alpha_k{\bf v}_k: k\leq n+1, {\bf v}_1,...,{\bf v}_k \in X,$$

$$\alpha_1,...,\alpha_k >0, \alpha_1+...+\alpha_k=1\}$$

Dowód. Z wniosku wynika, że jeśli istnieją $k$, $\alpha_1,...,\alpha_k$ oraz
${\bf v}_1,...,{\bf v}_k \in \nolinebreak X$ spełniające $\alpha_i\geq 0\ (i=1...,k), \ \sum^k_{i=1}\alpha_i=1$, takie, że ${\bf u}=\alpha_1{\bf v}_1+ ... \alpha_k{\bf v}_k$ to ${\bf u}\in conv(X)$ (w szczególności wtedy gdy $k \leq n+1$).
Wystarczy więc wykazać, że jeśli ${\bf u}\in conv(X)$, to istnieje nie więcej niż $n+1$ wektorów ${\bf u}_1,...,{\bf u}_k$ i skalarów $\alpha_1,...,\alpha_k,\ \alpha_i>0\ (i=1,...,k),\ \sum^k_{i=1}\ \alpha_i=1$, takich, że ${\bf u}=\alpha_1{\bf u}_1+ ... \alpha_k{\bf u}_k$. Dzięki wnioskowi wiemy, że istnieje $l$, wektory ${\bf v}_1,...,{\bf v}_l \in X$ oraz współczynniki $\beta_j>0, \ j=1,...,l, \beta_1+...+\beta_l=1$ takie, że ${\bf u}=\beta_1{\bf v}_1+...+\beta_l{\bf v}_l$.
Zauważmy teraz, że równania

$$\left\{ \begin{array}{lcr} \sum^l_{i=1}\beta_i{\bf v}_i &... ...{\bf u}\\ \sum^l_{i=1}\beta_i & = & 1 \end{array} \right.$$ (7.1)

dają nam układ $k+1$ równań rzeczywistych liniowych, których zmiennymi są $\beta_1,...,\beta_l$ a współczynnikami współrzędne wektorów ${\bf v}_1,...,{\bf v}_l$ (i jedynki w ostatnim równaniu), zaś wyrazami wolnymi są współrzędne wektora ${\bf u}$ (i jedynka w ostatnim równaniu).
Nasz nieoceniony wniosek zapewnia nam, że układ () jest niesprzeczny. Z twierdzenia wynika więc, że ma nieujemne (!) rozwiązanie w którym zmiennych bazowych jest $n+1$ (tyle ile równań). Pamiętamy także, że zmienne niebazowe w rozwiązaniu bazowym przyjmują wartość zero. To kończy dowód twierdzenia .