Demostrar que un poliedro contiene un punto extremo si y solo si no contiene una línea usando una matriz de restricciones estrictas
Quiero probar que un poliedro$P = \{x\in\mathbb{R}^n\;:\;Ax\leq b\}$tiene un punto extremo si y solo si no contiene una línea, pero quiero hacerlo de una manera particular (conozco una demostración por inducción sobre$n$lo que generaliza este resultado para cualquier conjunto convexo cerrado, pero no es así como quiero hacer la prueba aquí). Específicamente, quiero utilizar el resultado de que:
$x$es un punto extremo de$P$si y solo si$\text{rank}(A^=) = n$, dónde$A^=$es la matriz de restricciones estrictas/activas de$x$.
Ya se como probar que si$P$contiene una línea entonces$P$no tiene puntos extremos, pero mi pregunta es sobre lo contrario. Tengo un boceto informal de una prueba, pero agradecería alguna ayuda para hacerlo riguroso. quiero demostrar que si$P$no contiene puntos extremos, entonces debe contener una línea. Aquí está mi idea aproximada:
Dejar$x\in P$. Sabemos que no es extremo, por lo tanto existe$d_1\in\mathbb{R}^n$tal que$x + td_1\in P$por$t\in (-\varepsilon_1, \varepsilon_1)$para lo suficientemente pequeño$\varepsilon_1$. O$x + td_1$es una línea contenida en$P$, en cuyo caso hemos terminado, o$x \pm td_1$tiene una restricción activa/estricta para algunos$t = t_1$. WLOG asume el caso '+', es decir, es$x + t_1d_1$que tiene una restricción activa. Por suposición,$x + t_1d_1$no es un punto extremo, y por lo tanto existe$d_2\in\mathbb{R}^n$que no está en$\text{span}(d_1)$tal que$(x + t_1d_1) \pm td_2\in P$por$t\in (-\varepsilon_2, \varepsilon_2)$para lo suficientemente pequeño$\varepsilon_2$. O$P$contiene la linea$(x + t_1d_1) + td_2$en cuyo caso hemos terminado, o existe$t = t_2$tal que$(x + t_1d_1) \pm t_2d_2$que tiene una restricción activa. Nuevamente WLOG asume el caso '+'. Ya que$d_2$no está dentro$\text{span}(d_1)$entonces la restricción activa de antes todavía está activa, y ahora también está activa una nueva restricción. Iteramos este proceso, de modo que encontremos un$d_3\in\mathbb{R}^n$no en$\text{span}(d_1, d_2)$tal que$(x + t_1d_1 + t_2d_2) \pm td_3$está contenido en$P$Para pequeños$t$y esto es una línea en$P$o hay$t_3$tal que$x + t_1d_1 + t_2d_2 + t_3d_3$tiene una restricción activa. Ya que$d_3\notin\text{span}(d_1, d_2)$, las dos restricciones activas originales seguirán estando activas, por lo que ahora hay una tercera restricción activa, etc. En algún momento habremos encontrado una línea o tendremos$x + t_1d_1 + \cdots + t_nd_n$que tiene$n$restricciones activas. Pero entonces esto debería implicar que la matriz de restricciones activas$A^=$porque este punto es rango$n$, lo que implicaría que$x + t_1d_1 + \cdots + t_nd_n$es extremo, lo que contradice la hipótesis. Por lo tanto, en alguna iteración de este proceso necesariamente habremos encontrado una dirección$d_i$tal que la línea en esa dirección estaba contenida en$P$.
Mi intuición me dice que algo como esto debería funcionar, pero estoy luchando para que sea riguroso. Específicamente, afirmo que cada$d_i$no está en el lapso de la anterior$d_1,\dots, d_{i - 1}$, pero no sé cómo garantizar que esto sea cierto. En segundo lugar, afirmo que dado que cada$d_i$no está en el lapso de la anterior$d_1,\dots, d_{i - 1}$entonces las restricciones que estaban activas antes aún permanecen activas después de viajar en la dirección$d_i$. Esto parece que debería ser cierto, pero no estoy seguro de cómo probarlo. Finalmente, según mi argumento debería haber al menos$n$restricciones activas si terminamos iterando$n$veces, pero en realidad no sé cómo probar que el rango de$A^=$en realidad es igual a$n$en este caso (lo que nos da la ansiada contradicción si hemos llegado a este punto). Tal vez sea el caso de que$\text{rank}(A^=)$sigue siendo estrictamente menor que$n$, aunque tenemos$n$restricciones activas. Espero que esto sea imposible, pero no estoy seguro de cómo probarlo.
Si alguien pudiera ayudar a hacer que estos puntos sean rigurosos para que esto se convierta en una prueba válida, o en su lugar muestre por qué esta prueba no puede funcionar, estaría muy agradecido.
Respuestas
Estoy bastante seguro de que su prueba puede hacerse rigurosa. En cada etapa de su procedimiento, deje$\ A_j^=\ $Sea la matriz de restricciones estrictas y$\ A_j^<\ $la matriz de restricciones de holgura para$\ \displaystyle x_j=x+\sum_{i=1}^jt_id_i\ $. Porque$\ x_j \ $no es un punto extremo, el rango de$\ A_j^=\ $es menos que$\ n\ $, para que puedas elegir$\ d_{j+1}\ $yacer en su núcleo. Entonces todas las restricciones con matriz$\ A_j^=\ $permanecerá apretado por$\ x_j+td_{j+1}\ $(independientemente de si$\ d_{j+1}\in\text{span}\left(d_1,d_2,\dots,d_j\right)\ $O no). Si$\ x_j+td_{j+1}\ $no es una línea, entonces una o más de las restricciones con matriz$\ A_j^<\ $debe estar apretado para$\ x_{j+1}=x_j+t_{j+1}d_{j+1}\ $. Por lo tanto$\ A_j^=\ $debe ser una submatriz estricta de$\ A_{j+1}^=\ $. Ya que$\ A\ $tiene solo un número finito de filas, su procedimiento debe terminar con una línea$\ x_k+td_{k+1}\ $para algunos$\ k\ $, o con$\ A_k^==A\ $, y por lo tanto$\ Ax_k=b\ $. En este último caso, dado que$\ x_k\ $no es un punto extremo, entonces el rango de$\ A\ $debe ser menor que$\ n\ $y por lo tanto tener un núcleo no vacío. Si$\ d\ $es cualquier miembro distinto de cero del núcleo, entonces$\ x_k+td\ $será una línea en$\ P\ $.