1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – NotAbelianGroup Jun 10 at 6:40
  • $\begingroup$ 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$. $\endgroup$ – Marcus Ritt Jun 10 at 7:06
  • $\begingroup$ Thank you very much! $\endgroup$ – NotAbelianGroup Jun 10 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.