2
$\begingroup$

I know the algebraic notion of an extreme point. I am confused about the geometerical aspect of an extreme point in terms of the hyperplanes as mentioned below.

The point $x'$ lies on $n$ of the hyperplanes defining the polyhedron $P$, such that the rows of A associated with those hyperplanes are linearly independent. Thus, $x'$ satisfies $n$ linearly independent tight constraints.

I would be very grateful, if someone would please explain the text above.

  • 0
    Exactly which parts of the quote don't make sense to you?2011-08-21
  • 0
    @ Mike Spivey :I understand the fact that an extreme point lies on n binding hyperplanes. But can't figure out how the corresponding rows of the coefficient matrix will be linearly independent.2011-08-21

1 Answers 1

5

Suppose ${\bf x}'$ does not lie on $n$ linearly independent binding hyperplanes. (Remember that a hyperplane in $\mathbb{R}^n$ is a linear equation in $n$ variables.) Then the maximum number of linearly independent hyperplanes binding at ${\bf x}'$ is $r < n$. Let $G$ be the $r \times n$ matrix of constraint coefficients, and let $G{\bf x}' = {\bf g}$. Since the rank of $G$ is $r$, the nullspace of $G$ has dimension $n-r > 0$. Thus there exists some ${\bf d} \neq {\bf 0}$ such that $G{\bf d} = {\bf 0}$. Therefore $G({\bf x}' + {\bf d}) = G({\bf x}' - {\bf d}) = {\bf g}$, which means that both ${\bf d}$ and $-{\bf d}$ are feasible directions at ${\bf x}'$ (i.e., for a sufficiently small distance from ${\mathbf x}'$ in these directions we're still in $P$, as the only constraint hyperplanes to worry about sufficiently close to ${\bf x}'$ are those that are binding at ${\bf x}'$). Then there exists $\epsilon > 0$ such that ${\bf x}_1 = {\bf x}' + \epsilon {\bf d}$ and ${\bf x}_2 = {\bf x}' - \epsilon {\bf d}$ are both in $P$. Since ${\bf x}' = \frac{1}{2} {\bf x}_1 + \frac{1}{2} {\bf x}_2$, ${\bf x}'$ cannot be an extreme point.

Thus if ${\bf x}'$ is an extreme point, it must lie on $n$ linearly independent binding hyperplanes.

  • 0
    @ Mike Spivey: thanks a lot for explaining so well. I gather this is an equivalent characterization of extreme points.2011-08-22