# Extreme points of a polyhedron and convex combination

Problem: Let $$x \in P, P$$ a polyhedron. Show that if $$x$$ cannot be written as a convex combination of other points in $$P$$, then $$x$$ is an extreme point of $$P$$.

Proof: We see that in $$x$$, (at least) $$n$$ valid inequalities defining the polyhedron have to be tight (else, there exists some v such that $$x ± λ$$ v ∈ P for some small $$λ$$ and some vector $$v$$). Let these valid inequalities be $$a_1x ≤ \beta_1,··· ,a_nx ≤ \beta_n$$. So the the objective function $$∑n_i=a_i$$ ai has objective value $$∑n_i=\beta _i$$ at $$x$$ and is strictly smaller for all other points.

Hello, I am having an hard time getting an intuitive understanding of linear programming. In this proof, I do not understand why the fact that $$x$$ can not be written as convex combinations of other points in $$P$$, implies that we can find $$n$$ valid inequalities tight on $$x$$.

Let $$P$$ be given by $$Ax\leq b$$ and assume you can find at most $$n-1$$ tight inequalities for extreme point $$x\in P$$, and let the submatrix of $$A$$ corresponding to them be $$A_x$$. Then there is a vector $$v$$ such that $$A_xv=0$$, since $$A_x$$ has rank at most $$n-1$$. (The intuition here is that $$x$$ lies in an at most $$n-1$$-dimensional affine subspace, so there's some direction $$v$$ you can move staying in that space.)
Now look at the remaining inequalities $$a_ix\leq b_i$$. Since they are not tight actually $$a_ix and there must be a $$\lambda>0$$ such that $$a_i(x+\lambda v)\leq b$$ and $$a_i(x-\lambda v)\leq b_i$$. But then $$A(x+\lambda v)\leq b$$ and $$A(x-\lambda v)\leq b$$, since $$A_xv=0$$. (The intuition here is that since the remaining inequalities are not tight, you must be able to move a step $$\lambda>0$$ in direction $$\pm v$$.) This contradicts that $$x$$ cannot be written as a convex combination of other points in $$P$$.
• Thank you for your detailed answer. To be clear, why does $A(x+\lambda v) \leq b$ and $A(x-\lambda v) \leq b$ contradicts that $x$ cannot be written as a convex combination of others points? – NotAbelianGroup Jun 10 at 6:40
• Because you have points $x'=x+\lambda v$, $x''=x-\lambda v$ both different from $x$ and both feasible ($Ax'\leq b$ and $Ax''\leq b$), and their convex combination $1/2x'+1/2x''=x$. – Marcus Ritt Jun 10 at 7:06