How to Prove that hyperplane is facet defining?

436 Views Asked by At

I met the following statement without proof:

If the dimension of a polyhedron $P\subset\mathbb{R}^n$ is $d,$ then a valid for $P$ inequality $\alpha^T x ≤ b$ is facet defining for $P$ if and only if $P$ contains $d$ affinely independent points lying on the hyperplane $H(a;b)=\{x\in \mathbb{R}^n:\alpha^T x = b\} $.$

The proof of necessity is almost obvious:

If inequality $\alpha^T x ≤ b$ is facet defining for $P,$ therefore $\{x\in P:\alpha^T x = b\} $ is facet for $P.$ The dimension of every facet of P is $d − 1.$ This means that $P$ contains $d$ affinely independent points lying on the hyperplane $H(a;b).$

But how to prove sufficiency?

1

There are 1 best solutions below

5
On

The meaning of a "facet-defining" hyperplane of $\mathbb{R}^n$ for a polyhedron of dimension $d$ is not so obvious when $d<n$. Here I assume it is facet-defining iff the intersection of the hyperplane and the polyhedron has at least dimension $d-1$, and the polyhedron is entirely on one side of the hyperplane.

Suppose $P$ contains $d$ affinely independent points lying on the hyperplane $H(\alpha;b)$.
The convex hull $C$ of these $d$ points has dimension $d-1$.
A polyhedron being convex, $C \subset P$.
As all $d$ points verify $\alpha^Tx=b$, by linearity each point in $C$ verifies $\alpha^Tx=b$, so $C \subset H(\alpha;b)$.

So the intersection of $H(\alpha;b)$ and $P$ includes $C$, which is of dimension $d-1$: the intersection is at least of dimension $d-1$. And $P$ is entirely on one side of the hyperplane as we have the hypothesis that the inequality $\alpha^Tx \le b$ is valid for $P$.