1
$\begingroup$

If I have a bounded set $F$ in $N$ dimensional space and another set $G$ where every element $g$ in $G$ has $h'g=c$ and also must exist in $F$. $H$ is a vector in the $N$ dimensional space and $c$ is any constant $1\times 1$ matrix (scalar). $h$ is a vector of appropriate dimension.

How can I prove every extreme point of $G$ lies on the boundary of $F$?

That is to say if $x$ and $y$ are extreme points in $F$ then $xλ + (1-λ)y = g$

  • 2
    @Mark: what do you mean h'g=c ?2010-10-14
  • 0
    h'g=c is a constraint for some arbitrary value of c2010-10-14
  • 0
    @Mark, please see the discussion in the faq of how to typeset mathematics using TeX: http://meta.math.stackexchange.com/questions/463/2010-10-14
  • 0
    The two statements "every extreme point of G lies on the boundary of F" and "if x and y are extreme points in F then xλ + (1-λ)y = g" are not the same thing. Do you mean the former or the latter?2010-10-14
  • 0
    How are they not the same? If F is a polyhedron and X and Y are extreme points, isn't every point on the boundary a convex combination of extreme points?2010-10-14
  • 0
    Yes, but not every convex combination of extreme points is on the boundary. In fact, since F is bounded, every point in F - on the boundary or not - is a convex combination of its extreme points. In addition, it might take more than two extreme points to get a representation of a particular boundary point.2010-10-14
  • 0
    Oh I see what you mean, in that case I meant on the boundary, so the extreme points must be "next to" one another.2010-10-14
  • 2
    Best to define extreme points negatively. For a convex set $S$, $x$ is not an extreme point of $S$ if there exist $y,z \in S$ and $0 < \lambda < 1$ such that $x=\lambda y + (1-\lambda) z$.2010-10-14

1 Answers 1

1

I'll prove that every point of $G$ in the interior of $F$ is not an extreme point of $G$. I'll assume that $N>1$.

LEMMA. There is a vector $v\neq 0$ such that $h'v=0$.

Proof. Since $N>1$ there is a vector $u$ which is not a multiple of $h$. Let $$v=u-\left({{h'u}\over{h'h}}\right)h$$ Then $h'v=0$. Since $u$ is not a multiple of $h$, $v\neq 0$.

Answer. Suppose $x \in G$ and $x$ is also in the interior of $F$. Let $v$ be as in the lemma above. Then there is a small enough $\lambda$ such that $(x \pm \lambda v) \in F$. But $h'(x \pm \lambda v)=h'x$ so $(x \pm \lambda v) \in G$. But, $$x= {(x + \lambda v) \over 2} + {(x - \lambda v) \over 2}$$ So $x$ is not an extreme point of $G$.