Докажите, что многогранник содержит крайнюю точку тогда и только тогда, когда он не содержит прямой, используя матрицу жестких ограничений
Я хочу доказать, что многогранник $P = \{x\in\mathbb{R}^n\;:\;Ax\leq b\}$ имеет крайнюю точку тогда и только тогда, когда он не содержит строки, но я хочу сделать это особым образом (я знаю доказательство индукцией по $n$который обобщает этот результат для любого замкнутого выпуклого множества, но здесь я не хочу проводить доказательство). В частности, я хочу использовать результат, который:
$x$ крайняя точка $P$ если и только если $\text{rank}(A^=) = n$, где $A^=$ матрица жестких / активных ограничений $x$.
Я уже знаю, как доказать, что если $P$ содержит строку, тогда $P$не имеет крайностей, но мой вопрос об обратном. У меня есть неофициальный набросок доказательства, но я был бы признателен за помощь в его строгости. Я хочу показать, что если$P$не содержит крайних точек, то должен содержать линию. Вот моя приблизительная идея:
Позволять $x\in P$. Мы знаем, что это не крайность, поэтому существует$d_1\in\mathbb{R}^n$ такой, что $x + td_1\in P$ для $t\in (-\varepsilon_1, \varepsilon_1)$ для достаточно малых $\varepsilon_1$. Либо$x + td_1$ это строка, содержащаяся в $P$, и в этом случае мы закончили, или $x \pm td_1$ имеет активное / жесткое ограничение для некоторых $t = t_1$. WLOG принимает случай «+», т.е.$x + t_1d_1$который имеет активное ограничение. По предположению,$x + t_1d_1$ не является крайней точкой, поэтому существует $d_2\in\mathbb{R}^n$ которого нет в $\text{span}(d_1)$ такой, что $(x + t_1d_1) \pm td_2\in P$ для $t\in (-\varepsilon_2, \varepsilon_2)$ для достаточно малых $\varepsilon_2$. Либо$P$ содержит строку $(x + t_1d_1) + td_2$ в этом случае мы закончили, или существует $t = t_2$ такой, что $(x + t_1d_1) \pm t_2d_2$который имеет активное ограничение. Снова WLOG принимает случай «+». поскольку$d_2$ не в $\text{span}(d_1)$тогда активное ограничение, которое было раньше, все еще активно, и теперь активно новое ограничение. Мы повторяем этот процесс, чтобы найти$d_3\in\mathbb{R}^n$ не в $\text{span}(d_1, d_2)$ такой, что $(x + t_1d_1 + t_2d_2) \pm td_3$ содержится в $P$ для маленьких $t$ и либо это строка в $P$ или есть $t_3$ такой, что $x + t_1d_1 + t_2d_2 + t_3d_3$имеет активное ограничение. поскольку$d_3\notin\text{span}(d_1, d_2)$, исходные два активных ограничения будут по-прежнему активны, поэтому теперь есть третье активное ограничение и т. д. В какой-то момент мы либо найдем линию, либо у нас будет $x + t_1d_1 + \cdots + t_nd_n$ который имеет $n$активные ограничения. Но тогда это должно означать, что матрица активных ограничений$A^=$ для этой точки ранг $n$, что означало бы, что $x + t_1d_1 + \cdots + t_nd_n$экстремально, что противоречит гипотезе. Таким образом, на некоторой итерации этого процесса мы обязательно найдем направление$d_i$ так, чтобы линия в этом направлении содержалась в $P$.
Моя интуиция подсказывает мне, что что-то вроде этого должно сработать, но я изо всех сил стараюсь сделать это строго. В частности, я утверждаю, что каждый$d_i$ не входит в рамки предыдущего $d_1,\dots, d_{i - 1}$, но я не знаю, как гарантировать, что это правда. Во-вторых, я утверждаю, что поскольку каждый$d_i$ не входит в рамки предыдущего $d_1,\dots, d_{i - 1}$ тогда ограничения, которые были активны до этого, остаются активными после движения в направлении $d_i$. Кажется, это должно быть правдой, но я не знаю, как это доказать. Наконец, по моим доводам, я должен был иметь хотя бы$n$ активные ограничения, если мы закончим повторение $n$ раз, но я действительно не знаю, как доказать, что ранг $A^=$ фактически равно $n$в этом случае (что дает нам желаемое противоречие, если мы дошли до этой стадии). Может быть, дело в том, что$\text{rank}(A^=)$ все еще строго меньше, чем $n$, хотя у нас есть $n$активные ограничения. Я надеюсь, что это невозможно, но не знаю, как это доказать.
Если бы кто-то мог помочь сделать эти пункты строгими, чтобы это стало действительным доказательством, или вместо этого показало бы, почему это доказательство не работает, я был бы очень признателен.
Ответы
Я почти уверен, что ваше доказательство можно сделать строгим. На каждом этапе процедуры позвольте$\ A_j^=\ $ - матрица жестких ограничений и $\ A_j^<\ $ матрица ограничений запаса хода для $\ \displaystyle x_j=x+\sum_{i=1}^jt_id_i\ $. Потому что$\ x_j \ $ не крайняя точка, ранг $\ A_j^=\ $ меньше чем $\ n\ $, так что вы можете выбрать $\ d_{j+1}\ $лежать в его ядре. Тогда все ограничения с матрицей$\ A_j^=\ $ останется напряженным для $\ x_j+td_{j+1}\ $ (несмотря на погоду $\ d_{j+1}\in\text{span}\left(d_1,d_2,\dots,d_j\right)\ $или нет). Если$\ x_j+td_{j+1}\ $ не является строкой, то одно или несколько ограничений с матрицей $\ A_j^<\ $ должен быть трудным для $\ x_{j+1}=x_j+t_{j+1}d_{j+1}\ $. Следовательно$\ A_j^=\ $ должна быть строгой подматрицей $\ A_{j+1}^=\ $. поскольку$\ A\ $ имеет только конечное количество строк, ваша процедура должна заканчиваться либо строкой $\ x_k+td_{k+1}\ $ для некоторых $\ k\ $, или с $\ A_k^==A\ $, и, следовательно $\ Ax_k=b\ $. В последнем случае, поскольку$\ x_k\ $ не крайняя точка, то ранг $\ A\ $ должно быть меньше чем $\ n\ $и, следовательно, иметь непустое ядро. Если$\ d\ $ - любой ненулевой член ядра, то $\ x_k+td\ $ будет линия в $\ P\ $.