Теорема Вейля — Мінковського

Опуклий конус ${\displaystyle P}$ є поліедральним тоді і тільки тоді коли він є скінченно породженим.

Із відповідних визначень твердження можна подати у матричній формі. Опуклий конус можна записати як ${\displaystyle P=\{x\ |\ Ax\leqslant 0\}}$ для деякої матриці ${\displaystyle A}$ розмірності ${\displaystyle m\times n}$ тоді і тільки тоді коли існує матриця ${\displaystyle B}$ розмірності ${\displaystyle n\times k,}$ що ${\displaystyle P=\{x\ |\ x=By,\ y=\mathbb {R} ^{k},y\geqslant 0\}.}$

Для опуклого поліедра ${\displaystyle P}$ (який задається системою нерівностей ${\displaystyle Ax\leqslant b}$) існують такі ${\displaystyle r}$ векторів ${\displaystyle \mathbf {x} _{1},\ldots ,\mathbf {x} _{r}}$ і ${\displaystyle s}$ векторів ${\displaystyle \mathbf {x} _{r+1},\ldots ,\mathbf {x} _{r+s},}$ що довільну точку ${\displaystyle x\in P}$ можна записати як:

${\displaystyle x=\sum _{i=1}^{r}\alpha _{i}\mathbf {x} _{i}+\sum _{j=1}^{s}\beta _{j}\mathbf {x} _{r+j},\quad \alpha _{i},\beta _{j}\geqslant 0,\sum _{i=1}^{r}\alpha _{i}=1.}$

Якщо опуклий поліедр ${\displaystyle P}$ є обмеженим, то він є опуклою комбінацією своїх вершин. Тобто кожна точка записується як ${\displaystyle x=\sum _{i=1}^{r}\alpha _{i}\mathbf {x} _{i},\quad \alpha _{i}\geqslant 0,\sum _{i=1}^{r}\alpha _{i}=1,}$ де всі ${\displaystyle x_{i}}$ є вершинами поліедра.

Нехай задано, що ${\displaystyle P=\{x\ |\ x=By,\ y=\mathbb {R} ^{k},y\geqslant 0\}}$ для деякої матриці ${\displaystyle B}$ розмірності ${\displaystyle n\times k.}$ Потрібно довести, що існує деяка матриця ${\displaystyle A}$ розмірності ${\displaystyle m\times n}$, що також ${\displaystyle Ax\leqslant 0}$ для всіх ${\displaystyle x\in P}$ і тільки для них. Дана частина теореми називається теоремою Вейля.

Теорема Вейля є простим наслідком застосування методу Фур'є — Моцкіна. Для цього початкову систему рівнянь і нерівностей треба переписати як еквівалентну систему нерівностей виду:

${\displaystyle x-By\leqslant 0,\ -x+By\leqslant 0,\ -y\leqslant 0.}$

Після k кроків застосування методу Фур'є — Моцкіна одержується система необхідного виду ${\displaystyle Ax\leqslant 0.}$

Для доведення оберненого твердження, яке також називається просто теоремою Мінковського нехай для деякої множини ${\displaystyle X\subset \mathbb {R} ^{n}}$ через ${\displaystyle X^{d}}$ позначено двоїсту множину тобто множину таких ${\displaystyle y\in \mathbb {R} ^{n}}$ для яких ${\displaystyle y^{T}x\leqslant 0,\ \forall x\in X.}$

Якщо ${\displaystyle P=\{x\ |\ Ax\leqslant 0\}}$ то із леми Фаркаша випливає, що ${\displaystyle P^{d}}$ є множиною всіх невід'ємних лінійних комбінацій стовпців матриці ${\displaystyle A^{T}}$, тобто ${\displaystyle P^{d}=\{y\ |\ y=A^{T}z,\ z=\mathbb {R} ^{m},z\geqslant 0\}}$ і також ${\displaystyle (P^{d})^{d}=P.}$ Із доведеної теореми Вейля випливає існування матриці ${\displaystyle B}$ для якої ${\displaystyle P^{d}}$ є множиною розв'язків нерівностей ${\displaystyle B^{T}y\leqslant 0.}$ Тоді кожна невід'ємна лінійна комбінація стовпців матриці ${\displaystyle B}$ належить ${\displaystyle (P^{d})^{d}=P}$ і згідно леми Фаркаша ${\displaystyle P}$ є множиною всіх таких комбінацій, тобто ${\displaystyle P=\{x\ |\ x=Bz,\ z=\mathbb {R} ^{k},z\geqslant 0\},}$ що завершує доведення.

Нехай ${\displaystyle P=\{x\ |\ Ax\leqslant b\}}$ є опуклим поліедром у просторі ${\displaystyle \mathbb {R} ^{n}.}$ Розглядаючи простір ${\displaystyle \mathbb {R} ^{n+1}}$ і ввівши додаткову змінну можна розглянути поліедральний конус заданий нерівностями ${\displaystyle Ax-bx_{n+1}\leqslant 0,\ -x_{n+1}\leqslant 0.}$ Поліедр ${\displaystyle P}$ є перетином цього конусу із гіперплощиною ${\displaystyle x_{n+1}=1.}$

Згідно варіанту теореми для опуклих конусів кожна точка поліедрального конуса є невід'ємною лінійною комбінацією деякої скінченної множини векторів ${\displaystyle \mathbf {x} _{1},\ldots ,\mathbf {x} _{r+s}}$ і ці вектори можна вибрати і упорядкувати так, що у перших ${\displaystyle r}$ із них останні координати будуть рівні 1, а в останніх ${\displaystyle s}$ векторів остання координата є рівною 0. Тоді довільна точка конуса є невід'ємною лінійною комбінацією ${\displaystyle x=\sum _{i=1}^{r}\alpha _{i}x_{i}+\sum _{j=1}^{s}\beta _{j}x_{r+j},\quad \alpha _{i},\beta _{j}\geqslant 0.}$ Ця точка належить гіперплощині ${\displaystyle x_{n+1}=1}$ тоді і тільки тоді, коли додатково ${\displaystyle \sum _{i=1}^{r}\alpha _{i}=1,}$ що завершує доведення теореми Мінковського для опуклих поліедрів.

Для теореми Вейля, нехай ${\displaystyle P}$ є множиною усіх елементів виду ${\displaystyle x=\sum _{i=1}^{r}\alpha _{i}\mathbf {x} _{i}+\sum _{j=1}^{s}\beta _{j}\mathbf {x} _{r+j},\quad \alpha _{i},\beta _{j}\geqslant 0,\sum _{i=1}^{r}\alpha _{i}=1,}$ де всі точки належать простору ${\displaystyle \mathbb {R} ^{n}.}$ Розглядаючи простір ${\displaystyle \mathbb {R} ^{n+1}}$ і ввівши додаткову змінну можна розглянути опуклий скінченнопороджений конус, що є невід'ємною лінійною комбінацією векторів ${\displaystyle {\tilde {\mathbf {x} }}_{i},{\tilde {\mathbf {x} }}_{r+j},}$ де перші n координат усіх цих векторів є рівними відповідним координатам векторів ${\displaystyle \mathbf {x} _{i},\mathbf {x} _{r+j},}$ остання координата векторів ${\displaystyle {\tilde {\mathbf {x} }}_{i},\ i=1,\ldots ,r}$ є рівною 1, а остання координата векторів ${\displaystyle {\tilde {\mathbf {x} }}_{r+j},\ j=1,\ldots ,s}$ є рівною 0. Тоді початковий поліедр є перетином скінченнопородженого конуса і гіперплощини ${\displaystyle x_{n+1}=1.}$

Згідно із варіанту теореми для опуклих конусів. Скінченнопороджений конус також є множиною розв'язків деякої системи нерівностей ${\displaystyle A'x\leqslant 0}$ від n+1 змінної. Прийнявши ${\displaystyle x_{n+1}=1}$ одержується система виду ${\displaystyle Ax\leqslant b}$ від n змінних, яка і визначає опуклий поліедр.