I'm trying to prove the following theorem about linear programming from my textbook
Given a polyhedra $P=\{x\in \mathbb{R}^n|Ax\le b\}$ and a non-empty subset $F$ of $P$, then $F$ is a face of $P$ if and only if there exists a subsystem $A'x \le b^{'}$ of $Ax\le b$ such that $F=\{x\in P|A'x= b'\}$.
I think I've proved the if side as follows:
Suppose that $F=\{x\in P|A^{'}x= b'\}$ where $A^{'}x\le b'$ is a subsystem of $Ax\le b$. Let $1^T = \{1,1,\cdots,1\}$. Consider the vector $c^T=1^{T}A^{'}$ and $\delta= 1^Tb^{'}$. Left-multiply $A'x\le b'$ by $1^T$, we get $c^Tx\le \delta$ for all $x\in P$ and $c^Tx= \delta$ if $A^{'}x=b^{'}$. Then we have $\delta = \max_{x\in P} c^{T}x$ since $F=\{x\in P|A^{'}x= b'\}$ is non-empty. Thus, $\{x\in \mathbb{R}^{n}|c^Tx=\delta\}$ is a supporting hyperplane of $P$. Let $F^{'}=\{x\in P|c^Tx= \delta\}$. Obviously, $F^{'}$ is a face of $P$.
Next we prove that $F=F^{'}$. Obviously, $x\in F \Rightarrow x\in F^{'}$. For $x\in P\setminus F$, we have $Ax\le b$ and $A^{'}x \ne b^{'}$, thus $A^{'}x\le b^{'}$ and $A^{'}x \ne b^{'}$.Then there exsits a subscription $j$ such that $A^{'}_{j.}x < b^{'}_{j.}$, where subscription $j.$ means the $j$-th row vector of a matrix. Consequently $c^{T}x < \delta$, and we have $x\in P\setminus F^{'}$. $\square$
As for the only if side, I haven't came up with anything. Could you please
- verify the validity of my above proof;
- help me with the only if side.
Best Answer
The following is a proof for the only if side of your problem, which requires a good understanding of the duality theorems in linear programming, espeically the complementary slackness thoerem.
Proof$\;$ Suppose $F$ is a face of $P$ defined by $c^Tx\le \delta$, i.e., $F=\{x\in P|c^Tx =\delta\}$. Note that $F$ is the set of optimal solutions for linear programming: $$\max \;c^Tx :Ax \le b$$ There exists a dual optimal solution $y^*$ since $F\ne \emptyset$. Let $A'x\le b'$ be the subsystem of $Ax\le b$ which corresponds to non-zero entries in $y^*$. Define $F':= \{x\in P|A'x=b'\}$. For each $x\in F'$, $x$ and $y^*$ satisfy the complementary slackness conditions, so $F=F'$. $\square$