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

Теорема Вейля — Мінковського — твердження у математиці щодо різних форм запису поліедральних конусів та опуклих поліедрів. Існує кілька різних форм теореми, які відомі також і під багатьма іншими назвами, зокрема теорема про вільний базис, теорема про представлення поліедрів та ін.

Необхідні означення

Множина розв'язків системи нерівностей ${\displaystyle Ax\leqslant b,}$ де ${\displaystyle A}$ є дійсною матрицею розмірності ${\displaystyle m\times n}$ називається опуклим поліедром або опуклим політопом. Термінологія може відрізнятися у різних джерелах, іноді опуклим політопом називають відповідну множину, якщо вона є обмеженою, а для загального випадку використовується термін опуклий поліедр, іноді у загальному випадку використовується термін опуклий політоп.

У випадку однорідної системи нерівностей ${\displaystyle Ax\leqslant 0}$ множина розв'язків називається поліедральним конусом. Поліедральний конус ${\displaystyle P}$ є опуклим конусом, тобто для ${\displaystyle x,y\in P}$ і невід'ємних дійсних чисел ${\displaystyle \alpha ,\beta }$ лінійна комбінація ${\displaystyle \alpha x+\beta y\in P.}$

Довільний опуклий конус ${\displaystyle P}$ називається скінченнопородженим, якщо існують такі елементи ${\displaystyle x_{1},\ldots ,x_{n}\in P,}$ що кожен елемент ${\displaystyle x\in P}$ є невід'ємною лінійною комбінацією цих елементів, тобто ${\displaystyle x=\sum _{i=1}^{n}\alpha _{i}x_{i},}$ де всі ${\displaystyle \alpha _{i}\geqslant 0.}$

Твердження теореми

Твердження для поліедральних конусів

Опуклий конус ${\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 змінних, яка і визначає опуклий поліедр.

Представлення поліедрів

Варіант теореми Вейля — Мінковського для поліедрів стверджує, що довільний поліедр є сумою опуклої оболонки деяких своїх точок і деякого скінченно породженого опуклого конуса. Деякі додаткові твердження, які уточнюють точки і вектори у такому представленні також іноді називають на честь Мінковського, Вейля, а також Фаркаша, Моцкіна та ін.

Точка поліедра називається вершиною (або екстремальною точкою), якщо вона не є серединою деякого відрізка, що повністю належить поліедру. Також для довільного поліедра можна ввести множини:

${\displaystyle L(P)=\{z\ |\ x+az\in P,\ \forall x\in P,a\in \mathbb {R} \}}$

${\displaystyle C(P)=\{z\ |\ x+az\in P,\ \forall x\in P,a\geqslant 0\}}$

Якщо ${\displaystyle P=\{x\ |\ Ax\leqslant b\}}$, то еквівалентно ${\displaystyle L(P)=\{z\ |\ Az=b\}}$ і ${\displaystyle C(P)=\{z\ |\ Az\leqslant b\}.}$

Поліедр має екстремальні точки тоді і тільки тоді, коли ${\displaystyle L(P)=\{0\}}$ і є обмеженим, тобто політопом, тоді і тільки тоді, коли ${\displaystyle C(P)=\{0\}.}$ Якщо ${\displaystyle L(P)=\{0\}}$ то у твердженні теореми Вейля — Мінковського для поліедрів можна розглядати суму опуклої комбінації вершин поліедра і конуса ${\displaystyle C(P).}$ Елементи ${\displaystyle C(P)}$ натомість можна записати через невід'ємну лінійну комбінацію скінченної кількості векторів, які є екстремальними у ${\displaystyle C(P)}$ у розімінні, що якщо ${\displaystyle x=ax_{1}+bx_{2},\ \ x_{1},x_{2}\in P,\ a,b\geqslant 0}$, то ${\displaystyle x=x_{1}=x_{2}.}$ Тобто у цьому випадку твердження теореми Вейля — Мінковського можна подати у виді, що довільний поліедр є сумою опуклої оболонки своїх вершин і опуклого конуса породженого своїми екстремальними векторами.

Якщо конус не має екстремальних точок, твердження теореми Вейля — Мінковського можна уточнити розглянувши мінімальні грані поліедра. Якщо ${\displaystyle P=\{x\ |\ Ax\leqslant b\}}$, то мінімальними гранями будуть множини розв'язків різних систем рівнянь виду ${\displaystyle A'z=b'}$, де ${\displaystyle A',b'}$ одержані із початкових систем вибором максимальної лінійно незалежної системи рядків матриці ${\displaystyle A'}$. Якщо кількість рівнянь у цій системі буде рівною розмірності простору то мінімальна грань буде екстремальною точкою, адже тоді очевидно ${\displaystyle L(P)=\{z\ |\ Az=b\}=\{0\}.}$ Якщо мінімальні грані не є вершинами то накожній з них можна вибрати довільну точку. Тоді поліедр буде сумою опуклої комбінації цих точок і конуса ${\displaystyle C(P).}$ Елементи ${\displaystyle C(P)}$ натомість можна записати, наприклад, як суму лінійної комбінації базиса лінійного простору ${\displaystyle L(P)}$ і невід'ємної лінійної комбінації екстремальних векторів конуса одержаного перетином ${\displaystyle C(P)}$ і ортогонального доповнення до ${\displaystyle L(P)}$.

Разом у випадку відсутності екстремальних точок у теоремі Вейля — Мінковського можна взяти опуклу комбінацію обраних точок мінімальних граней і невід'ємну лінійну комбінацію базисних векторів простору ${\displaystyle L(P)}$, їх від'ємних векторів і екстремальних векторів конуса одержаного перетином ${\displaystyle C(P)}$ і ортогонального доповнення до ${\displaystyle L(P)}$.

Див. також

• Лема Фаркаша
• Метод Фур'є — Моцкіна
• Опуклий конус
• Опуклий політоп

Література

• Komei Fukuda. Lecture: Polyhedral Computation, Spring 2016.
• Schrijver, Alexander (1998). Theory of Linear and Integer Programming. John Wiley & sons. ISBN .
• Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, т. 152, Berlin, New York: Springer-Verlag