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$.
Best Answer
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<b_i$ 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$.