I have been working on the following problem for a whole day:
Let $F$ be a face of polyhedron $P$ in $R^d$. Let $H\subset R^d$ be a halfspace containing F. Show there exists a halfspace $H'$ containing P such that $H'\bigcap aff(F)=H\bigcap aff(F)$.
Please share with me some ideas. Thanka a lot.
My thoughts:
We may let $P=\{x:Ax\leq b\}$ where $A\in R^{m\times d}$.
And the face $F$ of P can be represented as $F=\{ x\in P: A_I x = b_I\}$ such that $aff(F)=\{x:A_I x=b_I\}$ .Here $I$ is a subset of $\{1,...,m\}$ and $A_I$ consists of the rows $\{a_i^T:i\in I\}$.
As $F$ is an exposed face of P, $F=P\bigcap L$ for some hyperplane $L=\{x:w^T x =\beta\}$. Moerover, $P \subset H_L=\{x:w^Tx\leq \beta\}$.
Let $H=\{x:h^Tx\leq \alpha\}$ and $G=\{x:h^T x\leq \alpha\}$, then we may consider the halfspace $H'$ being of the form $H(t)=\{x:(tw+(1-t)h)^T x \leq t\beta +(1-t)\alpha\},\tag{0}$ i.e., a convex combination of $H_L$ and $H$.
The reason for this sort of halfspace is that we always have $L(t)\bigcap aff(F)=G\bigcap aff(F),\forall 0<t<1\tag{1}.$
And this is a necessary condition for $H(t)\bigcap aff(F)=H\bigcap aff(F).$ In fact it is sufficient since either $H(t)\bigcap aff(F)=H\bigcap aff(F) \quad or \quad (-H(t))\bigcap aff(F)=H\bigcap aff(F)\tag{2}$ where $-H(t)=\{x:(tw+(1-t)h)^T x \geq t\beta +(1-t)\alpha\}$.
So now the goal is to prove that there exists $t\in (0,1)$, such that $P \in H(t)$ under the conditions:
- $H(1)$ contains $P$;
- $H(0)$ contains $F$, a face of $P$, but does contain $P$;
- For all $t \in (0,1)$, $H(t)$ contains $P$.
I got stucked here. So please share with me some ideas. Thank a lot.