Punkty skrajne.

Punkt $w\in V$ należący do zbioru wypukłego $V$ nazywamy skrajnym, gdy nie leży on wewnątrz niepustego odcinka z $V$. To znaczy, że gdy zachodzi równość $w=tx+(1-t)y$, gdzie $x,y\in V$ dla pewnego $t\in (0,1)$, to $x=y=w\in V$

5.1   Definicja Niech wektory $x_{j}\in \mathbb{R},$ dla $\,j=\overline{1,m}$. Wtedy powłokę wypukłą

$$conv\big\{x_{j}\in \mathbb{R}^{n}:j=\overline{1,m}\big\}\,=\,\bi... ...thbb{R}^{n}:\lambda_{j}\in \mathbb{R}_{+},\,\sum_{j=1}^{m}\lambda_{j}=1 \big\}$$ (5.1)

nazywamy m-wymiarowym wielościanem w $\mathbb{R}^{n}$.

Zachodzi takie twierdzenie.

5.2   Twierdzenie Wierzchołki wypukłego wielościanu $V$ są jego punktami skrajnymi.

Dowód jest wprost. Następne twierdzenie jest bardzo ważne dla praktyki.

5.3   Twierdzenie Minkowskiego Niepusty zwarty, wypukły zbiór w $\mathbb{R}^{n}$ zawiera punkty skrajne i stanowi wypukłą powłokę wszystkich swoich punktów skrajnych.

$\lhd$ Niech $V \subset \mathbb{R}^{n}$ jest niepustym, zwartym i wypukłym podzbiorem w $\mathbb{R}^{n}$ i $\tau=dim V$. Będziemy stosować indukcję matematyczną względem wymiaru $\tau=dim V$. Gdy $\tau = 1$, to $V$ jest odcinkiem, jego wierzchoLki są punktami skrajnymi. Niech teraz $\tau>1$. To znaczy, że twierdzenie jest prawdziwe dla każdego zwartego zbioru wypukłego w $\mathbb{R}^{n}$. Niech $\partial V$ będzie brzegiem zbioru $V$ i oczywiście nie jest pusty, ponieważ $V$ jest zbiorem domkniętym. Weźmy teraz punkt $g\in \partial V$. Wówczas istnieje funkcjonał $f:\mathbb{R}^{n}\longrightarrow \mathbb{R}$ taki, który oddziela zbiór $V$ oraz punkt $g\in \partial V$:

$$\sup_{y\in\,V}f(y)\,\leq\,f(g).$$ (5.2)

To oczywiście znaczy, że

$$V\,\subset \,\big\{y\in \mathbb{R}^{n}:\,f(y-g)\leq 0\big\}.$$ (5.3)

Nierówność () oczywiście równoważna jest, przy odwzorowaniu $f:\longrightarrow -f$, takiej:

$$f(g)\,\leq\,\inf_{y\in\,V}f(y).$$ (5.4)

Wtedy z () otrzymujemy, że

$$V\,\subset\,\big\{y\in \mathbb{R}^{n}: \,f(y-g)\geq 0 \big\}\,=\,\Pi^{+}_{g}.$$ (5.5)

jasne, że $\overline{\Pi}^{+}_{g}= \Pi^{+}_{g}\subset \mathbb{R}^{n}$, tj. $\Pi_{g}^{+}$ jest półprzestrzenią wypukłą i domkniętą. Zdefiniujmy teraz przecięcie

$$V_{g}\,:=\,V\cap \partial \Pi^{+}_{g},$$

gdzie

$$\partial \Pi^{+}_{g}\,:=\,\big\{y\in \mathbb{R}^{n} : \,f(y-g)=0\big\}.$$ (5.6)

Oczywiście $\partial \Pi^{+}_{g}$ jest brzegiem $\Pi^{+}_{g}$. Ponieważ $V$ jest zbiorem zwartym i wypukłym, to $V_{g}$ również jest zbiorem zwartym i wypukłym, tylko wymiaru mniejszego niż $\tau$, tj. $dim V_{g}< \tau$ ostro. Na mocy założenia indukcyjnego zbiór $V_{g}$ ma punkty skrajne oraz powłoka wypukła tych punktów generuje ten zbiór $V_{g}$. W szczególności punkt $g \in V_{g}$ jest kombinacją wypukłą niektórych z tych punktów. Wybierzmy teraz w $V_{g}$ jakikolwiek punkt skrajny $h\in E(V_{g})$, gdzie $E(V_{g})\subset V_{g}$ są punktami skrajnymi, i pokażemy, że ten punkt $h\in E(V)$, tj. jest też punktem skrajnym zbioru V.
Załóżmy, że $h=(1-\lambda)x+\lambda y,\,\lambda\in (0,1)$, oraz $x,y\in V$. Ponieważ $h\in \partial \Pi^{+}_{g}$, tj. brzegu opornej hiper-przestrzeni zbioru V, to zachodzi równość

$$f(h-g)\,=\,0,$$ (5.7)

skąd

$$(1-\lambda)\,f(x-g)\,+\,\lambda\,f(y-g)\,=\,0,$$ (5.8)

gdzie oczywiście $f(x-g)\geq 0$ oraz $f(y-g)\geq 0$. Ponieważ $\lambda \in (0,1)$, z () mamy, że dokładnie

$$f(x-g)\,=\,0\,=\,f(y-g).$$ (5.9)

Stąd wnioskujemy, że $x,y \in \partial \Pi^{+}_{g}\cap V = V_{g}$, co jest sprzeczne założeniu, że $h\in E(V_{g})$ jest punktem skrajnym, tj. $x=y=h \in E(V_{g})$.
Tak więc udowodniliśmy, że każdy punkt brzegowy zbioru $V$ jest liniową kombinacją wypukłą jego punktów skrajnych $E(V)$. Ponieważ każdy punkt tego zbioru $V$ należy do odcinka, którego punktami końcowymi są punkty brzegowe, to każdy punkt z $V$ jest wypukłą kombinacją liniową punktów skrajnych $E(V)$ $\rhd$

5.4   Uwaga To, że każdy punkt wewnętrzny jest liniową kombinacją wypukłą dwóch punktów brzegowych, zachodzi z tego, że każdy promień $[\overrightarrow{a,x}]$ przez punkty wewnętrzne $a,x\in V$ ma tylko jeden punkt przecięcia z granicą $\partial V$ zbioru $V$. Rzeczywiście, niech przecięcie tego promienia zawiera dwa punkty $z_{1}$ oraz $z_{2} \in \partial V$. Wtedy mamy dwie równości :

$$a+(x-a)t_{1}\,=\,z_{1}\in \partial V,$$

$$a+(x-a)t_{2}\,=\,z_{2}\in\partial V$$ (5.10)

gdzie z definicji $0<t_{1}<t_{2}$. Ponieważ zachodzą równości (), z tego że brzeg $\partial V$ jest brzegiem zbioru wypukłego $V$ otrzymujemy, że każdy punkt odcinka $(z_{1},z_{2})$ bedzie też punktem wewnętrznym, tj.

$$\lambda z_{1}\,+\,(1-\lambda)z_{2}\,=\,a\,+\,(x-a)\big[\lambda t... ...,+\,(1-\lambda)t_{1} \big]\,\in V\setminus \partial V, \quad \lambda \in (0,1)$$ (5.11)

Tak więc () oznacza, że cały odcinek $a+(x-a)\big[\lambda t_{2}\,+\,(1-\lambda)t_{1} \big],\,\lambda \in (0,1)$, jest przecięciem promienia $[\overrightarrow{a,x}]$ ze zbiorem $V$. Teraz zauważmy, że punkt brzegowy jest takim punktem, że w każdym jego otoczeniu są punkty wewnętrzne zbioru $V$ oraz zewnętrzne zbioru $\mathbb{R}^{n}\setminus V$. Ponieważ $t_{2}>t_{1}$, widzimy że punkt $z_{1}\in V$ jest jednocześnie punktem wewnętrznym, co przeczy założeniu, że $z_{1}\in \partial V$. To jest $t_{2}=t_{1}$, albo $z_{1}=z_{2}\in \partial V$.