Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Exactly which parts of the quote don't make sense to you? –  Mike Spivey Aug 21 '11 at 20:18
    
@ 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. –  Tav Aug 21 '11 at 20:23
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
@ Mike Spivey: thanks a lot for explaining so well. I gather this is an equivalent characterization of extreme points. –  Tav Aug 22 '11 at 4:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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