Prouver qu'un polyèdre contient un point extrême si et seulement s'il ne contient pas de droite à l'aide d'une matrice de contraintes strictes
Je veux prouver qu'un polyèdre$P = \{x\in\mathbb{R}^n\;:\;Ax\leq b\}$a un point extrême si et seulement s'il ne contient pas de ligne, mais je veux le faire d'une manière particulière (j'ai connaissance d'une preuve par induction sur$n$qui généralise ce résultat pour tout ensemble convexe fermé, mais ce n'est pas ainsi que je veux faire la preuve ici). Plus précisément, je veux utiliser le résultat suivant :
$x$est un point extrême de$P$si et seulement si$\text{rank}(A^=) = n$, où$A^=$est la matrice des contraintes serrées/actives de$x$.
Je sais déjà comment prouver que si$P$contient une ligne alors$P$n'a pas de points extrêmes, mais ma question porte sur l'inverse. J'ai une esquisse informelle d'une preuve, mais j'apprécierais de l'aide pour la rendre rigoureuse. Je veux montrer que si$P$ne contient pas de points extrêmes, alors il doit contenir une ligne. Voici mon idée approximative:
Laisser$x\in P$. Nous savons que ce n'est pas extrême, donc il existe$d_1\in\mathbb{R}^n$tel que$x + td_1\in P$pour$t\in (-\varepsilon_1, \varepsilon_1)$pour suffisamment petit$\varepsilon_1$. Soit$x + td_1$est une ligne contenue dans$P$, auquel cas nous avons terminé, ou$x \pm td_1$a une contrainte active/serrée pour certains$t = t_1$. WLOG assume le cas '+', c'est-à-dire qu'il est$x + t_1d_1$qui a une contrainte active. Par hypothèse,$x + t_1d_1$n'est pas un point extrême, et donc il existe$d_2\in\mathbb{R}^n$qui n'est pas dans$\text{span}(d_1)$tel que$(x + t_1d_1) \pm td_2\in P$pour$t\in (-\varepsilon_2, \varepsilon_2)$pour suffisamment petit$\varepsilon_2$. Soit$P$contient la ligne$(x + t_1d_1) + td_2$auquel cas nous avons fini, ou il existe$t = t_2$tel que$(x + t_1d_1) \pm t_2d_2$qui a une contrainte active. Encore une fois, WLOG assume le cas '+'. Depuis$d_2$n'est pas dans$\text{span}(d_1)$alors la contrainte active d'avant est toujours active, et maintenant une nouvelle contrainte est également active. Nous itérons ce processus, de sorte que nous trouvons un$d_3\in\mathbb{R}^n$pas dedans$\text{span}(d_1, d_2)$tel que$(x + t_1d_1 + t_2d_2) \pm td_3$est contenu dans$P$pour les petits$t$et soit c'est une ligne dans$P$ou il y a$t_3$tel que$x + t_1d_1 + t_2d_2 + t_3d_3$a une contrainte active. Depuis$d_3\notin\text{span}(d_1, d_2)$, les deux contraintes actives d'origine seront toujours actives, et il y a donc maintenant une troisième contrainte active, etc. À un moment donné, nous aurons soit trouvé une ligne, soit nous aurons$x + t_1d_1 + \cdots + t_nd_n$qui a$n$contraintes actives. Mais alors cela devrait impliquer que la matrice des contraintes actives$A^=$car ce point est de rang$n$, ce qui impliquerait que$x + t_1d_1 + \cdots + t_nd_n$est extrême, ce qui contredit l'hypothèse. Donc, à une certaine itération de ce processus, nous aurons nécessairement trouvé une direction$d_i$telle que la ligne dans cette direction était contenue dans$P$.
Mon intuition me dit que quelque chose comme ça devrait fonctionner, mais j'ai du mal à rendre cela rigoureux. Plus précisément, j'affirme que chaque$d_i$n'est pas dans la durée de ce qui précède$d_1,\dots, d_{i - 1}$, mais je ne sais pas comment garantir que cela est vrai. Deuxièmement, je prétends que puisque chaque$d_i$n'est pas dans la durée du précédent$d_1,\dots, d_{i - 1}$alors les contraintes qui étaient actives avant restent actives après avoir parcouru la direction$d_i$. Cela semble être vrai, mais je ne sais pas comment le prouver. Enfin, d'après mon argument, j'aurais dû au moins$n$contraintes actives si nous finissons par itérer$n$fois, mais je ne sais pas vraiment comment prouver que le rang de$A^=$est en fait égal à$n$dans ce cas (ce qui nous donne la contradiction recherchée si nous en sommes arrivés à ce stade). C'est peut-être le cas que$\text{rank}(A^=)$est toujours strictement inférieur à$n$, même si nous avons$n$contraintes actives. J'espère que c'est impossible, mais je ne sais pas comment le prouver.
Si quelqu'un pouvait aider à rendre ces points rigoureux afin que cela devienne une preuve valide, ou montre à la place pourquoi cette preuve ne peut pas fonctionner, je serais très reconnaissant.
Réponses
Je suis à peu près sûr que votre preuve peut être rendue rigoureuse. A chaque étape de votre procédure, laissez$\ A_j^=\ $être la matrice des contraintes fortes et$\ A_j^<\ $la matrice des contraintes d'écart pour$\ \displaystyle x_j=x+\sum_{i=1}^jt_id_i\ $. Car$\ x_j \ $n'est pas un point extrême, le rang de$\ A_j^=\ $est inférieur à$\ n\ $, vous pouvez donc choisir$\ d_{j+1}\ $reposer dans son noyau. Alors toutes les contraintes de matrice$\ A_j^=\ $restera serré pendant$\ x_j+td_{j+1}\ $(indépendamment du fait que$\ d_{j+1}\in\text{span}\left(d_1,d_2,\dots,d_j\right)\ $ou non). Si$\ x_j+td_{j+1}\ $n'est pas une ligne, alors une ou plusieurs des contraintes de matrice$\ A_j^<\ $doit être serré pour$\ x_{j+1}=x_j+t_{j+1}d_{j+1}\ $. Par conséquent$\ A_j^=\ $doit être une sous-matrice stricte de$\ A_{j+1}^=\ $. Depuis$\ A\ $n'a qu'un nombre fini de lignes, votre procédure doit se terminer soit par une ligne$\ x_k+td_{k+1}\ $pour certains$\ k\ $, ou avec$\ A_k^==A\ $, et donc$\ Ax_k=b\ $. Dans ce dernier cas, puisque$\ x_k\ $n'est pas un point extrême, alors le rang de$\ A\ $doit être inférieur à$\ n\ $et donc avoir un noyau non vide. Si$\ d\ $est un membre non nul du noyau, alors$\ x_k+td\ $sera une ligne dans$\ P\ $.