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

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

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

ред.

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

У випадку однорідної системи нерівностей   множина розв'язків називається поліедральним конусом. Поліедральний конус   є опуклим конусом, тобто для   і невід'ємних дійсних чисел   лінійна комбінація  

Довільний опуклий конус   називається скінченнопородженим, якщо існують такі елементи   що кожен елемент   є невід'ємною лінійною комбінацією цих елементів, тобто   де всі  

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

ред.

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

ред.

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

Із відповідних визначень твердження можна подати у матричній формі. Опуклий конус можна записати як   для деякої матриці   розмірності   тоді і тільки тоді коли існує матриця   розмірності   що  

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

ред.

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

 

Наслідок

ред.

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

Доведення

ред.

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

ред.

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

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

 

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

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

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

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

ред.

Нехай   є опуклим поліедром у просторі   Розглядаючи простір   і ввівши додаткову змінну можна розглянути поліедральний конус заданий нерівностями   Поліедр   є перетином цього конуса із гіперплощиною  

Згідно варіанту теореми для опуклих конусів кожна точка поліедрального конуса є невід'ємною лінійною комбінацією деякої скінченної множини векторів   і ці вектори можна вибрати і упорядкувати так, що у перших   із них останні координати будуть рівні 1, а в останніх   векторів остання координата є рівною 0. Тоді довільна точка конуса є невід'ємною лінійною комбінацією   Ця точка належить гіперплощині   тоді і тільки тоді, коли додатково   що завершує доведення теореми Мінковського для опуклих поліедрів.

Для теореми Вейля, нехай   є множиною усіх елементів виду   де всі точки належать простору   Розглядаючи простір   і ввівши додаткову змінну можна розглянути опуклий скінченнопороджений конус, що є невід'ємною лінійною комбінацією векторів   де перші n координат усіх цих векторів є рівними відповідним координатам векторів   остання координата векторів   є рівною 1, а остання координата векторів   є рівною 0. Тоді початковий поліедр є перетином скінченнопородженого конуса і гіперплощини  

Згідно із варіанту теореми для опуклих конусів. Скінченнопороджений конус також є множиною розв'язків деякої системи нерівностей   від n+1 змінної. Прийнявши   одержується система виду   від n змінних, яка і визначає опуклий поліедр.

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

ред.

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

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

 
 

Якщо  , то еквівалентно   і  

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

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

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

Див. також

ред.

Література

ред.
  • 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