Polyhedra proof. Is my solution correct?

41 Views Asked by At

My professor suggested that the following theorem is true, so I tried to prove it. Could you please let me know if my proof is correct, and/or make any suggestions on how the proof can be improved?

$\textbf{Theorem}: $ Let $P = \{x : Ax \le b \}$ be a polyhedron with at least one extreme point, and let $\hat x$ be any non-extreme point of the polyhedron . Prove that there exists an extreme point $e$ of $P$, and a $t > 0$, such that $\hat x + t (\hat x-e) \in P.$

$\textit{Proof:}$ Let \begin{align} &I = \{i : a_i^T \hat x = b_i \} \text{ denote the set of active constraints at } \hat x, \\ &J = \{j : a_j^T \hat x < b_j \} \text{ denote the set of inactive constraints at } \hat x. \end{align} Let $Q$ be the polyhedron $Q = \{x : Ax \le b, A_I x = b_I\}.$ Since $P$ has an extreme point, it does not contain a line, so $Q$ does not contain a line, therefore $Q$ has an extreme point, $e$.

Now $e$ is a BFS of $Q$, so there are $n$ linearly independent constraints of $Q$ which are tight at $e$, therefore there are $n$ linearly independent constraints of $P$ which are tight at $e$, so $e$ is a BFS of $P$.

Consider $p(t) = \hat x + t(\hat x - e).$ Since $\hat x$ and $e$ are in $Q$, we have $A_I \hat x = A_I e = b_I$, so \begin{align} &A_Ip(t) = A_I \hat x + t( A_I \hat x - A_I e) = b_I, \\ &A_Jp(t) = A_J \hat x + tA_J( \hat x - e). \end{align} Since $A_J \hat x < b$, we have, for some small $t$, that $p(t) \in P$, as desired.