Dimostrare che un poliedro contiene un punto estremo se e solo se non contiene una linea utilizzando la matrice dei vincoli stretti
Voglio dimostrare che un poliedro$P = \{x\in\mathbb{R}^n\;:\;Ax\leq b\}$ha un punto estremo se e solo se non contiene una linea, ma voglio farlo in un modo particolare (sono a conoscenza di una dimostrazione per induzione su$n$che generalizza questo risultato per qualsiasi insieme convesso chiuso, ma non è così che voglio procedere con la dimostrazione qui). Nello specifico voglio utilizzare il risultato che:
$x$è un punto estremo di$P$se e solo se$\text{rank}(A^=) = n$, dove$A^=$è la matrice dei vincoli stretti/attivi di$x$.
So già come dimostrarlo se$P$contiene una riga allora$P$non ha punti estremi, ma la mia domanda riguarda il contrario. Ho uno schizzo informale di una prova, ma gradirei un aiuto per renderlo rigoroso. Voglio mostrare che se$P$non contiene punti estremi, allora deve contenere una linea. Ecco la mia idea di massima:
Permettere$x\in P$. Sappiamo che non è estremo, quindi esiste$d_1\in\mathbb{R}^n$tale che$x + td_1\in P$per$t\in (-\varepsilon_1, \varepsilon_1)$per sufficientemente piccolo$\varepsilon_1$. O$x + td_1$è una riga contenuta in$P$, nel qual caso abbiamo finito, o$x \pm td_1$ha un vincolo attivo/stretto per alcuni$t = t_1$. WLOG assume il caso '+', cioè lo è$x + t_1d_1$che ha un vincolo attivo. Per ipotesi,$x + t_1d_1$non è un punto estremo, e quindi esiste$d_2\in\mathbb{R}^n$che non c'entra$\text{span}(d_1)$tale che$(x + t_1d_1) \pm td_2\in P$per$t\in (-\varepsilon_2, \varepsilon_2)$per sufficientemente piccolo$\varepsilon_2$. O$P$contiene la riga$(x + t_1d_1) + td_2$nel qual caso abbiamo finito, o esiste$t = t_2$tale che$(x + t_1d_1) \pm t_2d_2$che ha un vincolo attivo. Anche in questo caso WLOG assume il caso '+'. Da$d_2$non c'è$\text{span}(d_1)$quindi il vincolo attivo di prima è ancora attivo e ora è attivo anche un nuovo vincolo. Iteriamo questo processo, in modo da trovare a$d_3\in\mathbb{R}^n$Non in$\text{span}(d_1, d_2)$tale che$(x + t_1d_1 + t_2d_2) \pm td_3$è contenuto in$P$per piccolo$t$e questa è una linea in entrata$P$o c'è$t_3$tale che$x + t_1d_1 + t_2d_2 + t_3d_3$ha un vincolo attivo. Da$d_3\notin\text{span}(d_1, d_2)$, i due vincoli attivi originali saranno ancora attivi, quindi ora c'è un terzo vincolo attivo, ecc. Ad un certo punto avremo trovato una linea o avremo$x + t_1d_1 + \cdots + t_nd_n$che ha$n$vincoli attivi. Ma allora questo dovrebbe implicare che la matrice dei vincoli attivi$A^=$perché questo punto è rango$n$, il che lo implicherebbe$x + t_1d_1 + \cdots + t_nd_n$è estremo, il che contraddice l'ipotesi. Quindi, quindi, a qualche iterazione di questo processo avremo necessariamente trovato una direzione$d_i$tale che la linea in quella direzione fosse contenuta$P$.
La mia intuizione mi dice che qualcosa del genere dovrebbe funzionare, ma sto lottando per renderlo rigoroso. Nello specifico, affermo che ciascuno$d_i$non è nell'arco del precedente$d_1,\dots, d_{i - 1}$, ma non so come garantire che sia vero. In secondo luogo, sostengo che poiché ciascuno$d_i$non è nell'arco del precedente$d_1,\dots, d_{i - 1}$quindi i vincoli che erano attivi prima rimangono attivi anche dopo aver viaggiato in direzione$d_i$. Sembra che dovrebbe essere vero, ma non sono sicuro di come dimostrarlo. Infine, secondo la mia argomentazione, avrei dovuto almeno$n$vincoli attivi se finiamo per iterare$n$volte, ma in realtà non so come dimostrare che il grado di$A^=$è effettivamente uguale a$n$in questo caso (che ci dà la contraddizione desiderata se siamo arrivati a questo stadio). Forse è il caso che$\text{rank}(A^=)$è ancora rigorosamente inferiore a$n$, anche se abbiamo$n$vincoli attivi. Spero che questo sia impossibile, ma non sono sicuro di come provarlo.
Se qualcuno potesse aiutare a rendere rigorosi questi punti in modo che diventino una prova valida, o invece mostri perché questa dimostrazione non può funzionare, sarei molto grato.
Risposte
Sono abbastanza sicuro che la tua dimostrazione possa essere resa rigorosa. In ogni fase della tua procedura, lascia$\ A_j^=\ $essere la matrice di vincoli stretti e$\ A_j^<\ $la matrice dei vincoli di flessibilità per$\ \displaystyle x_j=x+\sum_{i=1}^jt_id_i\ $. Perché$\ x_j \ $non è un punto estremo, il grado di$\ A_j^=\ $è meno di$\ n\ $, quindi puoi scegliere$\ d_{j+1}\ $mentire nel suo nocciolo. Quindi tutti i vincoli con matrix$\ A_j^=\ $rimarrà stretto per$\ x_j+td_{j+1}\ $(indipendentemente dal fatto che$\ d_{j+1}\in\text{span}\left(d_1,d_2,\dots,d_j\right)\ $o no). Se$\ x_j+td_{j+1}\ $non è una linea, quindi uno o più dei vincoli con matrice$\ A_j^<\ $deve essere stretto per$\ x_{j+1}=x_j+t_{j+1}d_{j+1}\ $. Perciò$\ A_j^=\ $deve essere una sottomatrice stretta di$\ A_{j+1}^=\ $. Da$\ A\ $ha solo un numero finito di righe, la procedura deve terminare con una riga$\ x_k+td_{k+1}\ $per alcuni$\ k\ $, o con$\ A_k^==A\ $, e quindi$\ Ax_k=b\ $. In quest'ultimo caso, poiché$\ x_k\ $non è un punto estremo, quindi il rango di$\ A\ $deve essere inferiore a$\ n\ $e quindi hanno un kernel non vuoto. Se$\ d\ $è un qualsiasi membro diverso da zero del kernel, quindi$\ x_k+td\ $sarà una linea in$\ P\ $.