Extreme points in the intersection of hyperplanes and hypercube

381 Views Asked by At

Let $A$ be any $c \times n$ matrix such that $c < n$ and let $b$ be any $c\times 1$ vector. It is also known that $A$ and $b$ are element-wise positive. Consider the set defined as \begin{align} \mathcal{S}=\{x~|~Ax\leq b~,~x\in[0,1]^n\} \end{align} where $[0,1]^n$ is the standard hypercube. If $\mathcal{S}$ is non-empty with at least two points, it is easy to see that $\mathcal{S}$ is a closed convex set. I am interested in the extreme points of $\mathcal{S}$. Extreme points are the points which can never be contained inside a non-degenerate line in $\mathcal{S}$ (can be thought of as corners). Another way to say is, they can never be written as convex-combinations of two other points in $\mathcal{S}$. Is the following statement true?

Question: if $e$ is an extreme point of $\mathcal{S}$, the number of components in vector $e$ such that $0<e_i<1$ is upper-bounded by $c$.

1

There are 1 best solutions below

2
On BEST ANSWER

Vertices are basic feasible solutions, hence the claim is true.

A basic feasible solution satisfies $n$ linearly independent active constraint.

Let $M$ corresponds to the indices of the linearly independent inequalities that are active from $Ax \le b$. Let $x$ be a basic solution and $x_{B(1)}, \ldots x_{B(k)}$ that satisfies $0<x_{B(i)}<1$. Let $J$ denotes the indices that attains $x_i=1$, then we reduces the problem to

$$\sum_{j =1}^Ka_{iB(j)}x_{B(j)} =b_i-\sum_{j \in J}a_{ij}, \forall i \in M$$

and we know that it has a unique solution. The columns corresponding to $B(k)$ must be linearly independent. Hence $K \le c$.