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

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

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

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

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

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

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

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

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

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

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

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

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.

Наслідок ред.

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

Доведення ред.

Доведення для конусів ред.

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

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

x-By\leqslant 0,\ -x+By\leqslant 0,\ -y\leqslant 0.

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

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

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

Доведення для опуклих поліедрів ред.

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також ред.

Література ред.

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