Теорема Вейля — Мінковського: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
|||
Рядок 11:
=== Твердження для поліедральних конусів ===
[[Опуклий конус]] <math>P</math> є поліедральним тоді і тільки тоді коли він є скінченно породженим.
Із відповідних визначень твердження можна подати у матричній формі. Опуклий конус можна записати як <math>P = \{x\ |\ Ax \leqslant 0\}</math> для деякої [[Матриця (математика)|матриці]] <math>A</math> розмірності <math>m \times n</math> тоді і тільки тоді коли існує матриця <math>B</math> розмірності <math>n \times k,</math> що <math>P = \{x\ |\ x = By,\ y = \R^k, y \geqslant 0\}.</math>
=== Твердження для опуклих поліедрів ===
Для [[Опуклий політоп|опуклого поліедра]] <math>P</math> (який задається системою нерівностей <math>Ax \leqslant b</math>) існують такі <math>r</math> векторів <math>x_1, \ldots, x_r</math> і <math>s</math> векторів <math>x_{r+1}, \ldots, x_{r+s},</math> що довільну точку <math>x \in P</math> можна записати як:
: <math>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, \sum_{i=1}^r \alpha_i = 1. </math>
Рядок 25:
Нехай задано, що <math>P = \{x\ |\ x = By,\ y = \R^k, y \geqslant 0\}</math> для деякої матриці <math>B</math> розмірності <math>n \times k.</math> Потрібно довести, що існує деяка матриця <math>A</math> розмірності <math>m \times n</math>, що також <math>Ax \leqslant 0</math> для всіх <math>x \in P</math> і тільки для них. Дана частина теореми називається '''теоремою Вейля'''.
Теорема Вейля є простим наслідком застосування [[Метод Фур'є — Моцкіна|методу Фур'є — Моцкіна]]. Для цього початкову систему рівнянь і нерівностей треба переписати як еквівалентну систему нерівностей виду:
: <math>x - By \leqslant 0 ,\ - x + By \leqslant 0,\ -y \leqslant 0.</math>
Після ''k'' кроків застосування методу Фур'є — Моцкіна одержується система необхідного виду <math>Ax \leqslant 0.</math>
Для доведення оберненого твердження, яке також називається просто '''теоремою Мінковського''' нехай для деякої множини <math>X \subset \R^n</math> через <math>X^d</math> позначено двоїсту множину тобто множину таких <math>y \in \R^n</math> для яких <math>y^T x \leqslant 0,\ \forall x \in X.</math>
Якщо <math>P = \{x\ |\ Ax \leqslant 0\}</math> то із [[Лема Фаркаша|леми Фаркаша]] випливає, що <math>P^d</math> є множиною всіх невід'ємних [[Лінійна комбінація|лінійних комбінацій]] стовпців матриці <math>A^T</math>, тобто <math>P^d = \{y\ |\ y = A^Tz,\ z = \R^m, z \geqslant 0\}</math> і також <math>(P^d)^d = P.</math> Із доведеної теореми Вейля випливає існування матриці <math>B</math> для якої <math>P^d </math> є множиною розв'язків нерівностей <math>B^Ty \leqslant 0.</math> Тоді кожна невід'ємна лінійна комбінація стовпців матриці <math>B</math> належить <math>(P^d)^d = P</math> і згідно леми Фаркаша <math>P</math> є множиною всіх таких комбінацій, тобто <math>P = \{x\ |\ x = Bz,\ z = \R^k, z \geqslant 0\},</math> що завершує доведення.
== Див. також ==
| |||