Explain why for an extreme point some inequalities in the constraints become equalities

Question

Suppose we have a linear program $$ \max_x c^Tx\\ \text{subject to } Ax \leq b $$ where $\leq$ denotes pairwise inequality, i.e. $a^T_i x \leq b_i, i = 1,..., n$.

If $y$ is an extreme point, why is it that $Ay_i = b_i$ for several $i$'s?

Answer 1

Suppose on the contrary that $y$ is an extreme point and we have $$Ay<b.$$ Let $e$ denotes the all one vector.

We can choose a small $\epsilon>0$ such that

$$A(y+\epsilon e)<b$$

and $$A(y-\epsilon e)<b.$$

We see that $y+\epsilon e$ and $y-\epsilon e$ are both in the polyhedral and we have $$y=0.5(y+\epsilon e)+0.5 (y-\epsilon e)$$ which contradicts that $y$ is an extreme point.

Answer 2

The set of points $S$ in which the restriction holds forms a convex polytope.

Assume this polytope is finite: since the objective function is linear, the gradient is $\mathbf{c}$, which is a constant vector.

Now assume that $\mathbf{y}$ is a maximum but it is not in the border of $S$; then we can find a suitable $\epsilon>0$ such that $\mathbf{y}'=\mathbf{y}+ \epsilon \mathbf{c}$ is still inside $S$, but yields a greater value of the objective function (remember $\mathbf{c}$ points in the direction of maximum increase).

Therefore, by contradiction, if $\mathbf{y}$ is a maximum it must lie in the border of $S$. That means at least one restriction will hold with equality (you could have various equalities if the maximum is at a vertex of the convex polytope)

If the polytope is not finite, actually the statement holds unchanged. You just add the possibility of not having a solution to the problem, since if $\mathbf{c}$ points in a direction that, starting from a point $\mathbf{x_0}$ inside $S$, $\mathbf{x}+ \epsilon \mathbf{c}$ always stays inside $S$ for all $\epsilon>0$, you have no maximum.