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
    @ 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