4
$\begingroup$

Let $A$ be a subset of $\mathbb{R}^n$ and let $e$ be an extreme point of $\overline{\mathrm{conv}(A)}$. Prove that $e \in \overline{A}$.

The problem is intuitive, but I cannot prove it. Thanks in advance for any help!

$\endgroup$
  • 1
    $\begingroup$ Can you show that the extreme points of $conv(\bar{A})$ are all in $\bar{A}$? $\endgroup$ – pseudocydonia Aug 29 '19 at 4:06
  • $\begingroup$ Sure! Does this help? $\endgroup$ – astrobarrel Aug 29 '19 at 5:31
2
+50
$\begingroup$

Suppose that $p\not\in\overline{A}$ and take some $r>0$ such that the ball $B=B(p,r)$ misses $\overline{A}$. Assume also that $p\in\overline{\mathrm{conv}(A)}$. Let $S$ be the boundary of $B$, that is $S=\{x:||x-p||=r\}$. Using compactness of $S$ we are going to show that $p$ is not an extreme point of $\overline{\mathrm{conv}(A)}$. (This shows that if $e$ is an extreme point of $\overline{\mathrm{conv}(A)}$ then $e\in\overline{A}$.)

Take a sequence of points $p_k$ in $B$ converging to $p$ as $k\to\infty$, and such that $p_k\in\mathrm{conv}(A)$ for each $k$. For each $k$ pick a finite set $F_k\subseteq A$ such that $p_k\in\mathrm{conv}(F_k)$. Since we work in $\Bbb R^n$ we may assume that each $F_k$ has at most $n+1$ many points. Then there is some $m\le n+1$ such that there are infinitely many $k$ such that $F_k$ has exactly $m$ many points. By passing to a subsequence (throwing out the remaining $k$'s and respective $p_k$'s) we may assume that $F_k$ has exactly $m$ many points for every $k$, say $F_k=\{x_{k,j}:1\le j\le m\}$. Write $p_k= \lambda_{k,1}x_{k,1}+...+\lambda_{k,m}x_{k,m}$, a convex combination with suitable $\lambda_{k,1},...,\lambda_{k,m}$.

For each $k$ and each $j$ with $1\le j\le m$ let $s_{k,j}$ be the intersection with $S$ of the line segment joining $p_k$ and $x_{k,j}$. If $S_k=\{s_{k,j}:1\le j\le m\}$ then $S_k\subseteq\mathrm{conv}(A)$ (since each $s_{k,j}$ is a convex combination of $p_k\in\mathrm{conv}(A)$ and $x_{k,j}\in A$).

Lemma. $p_k=\mu_{k,1}s_{k,1}+...+\mu_{k,m}s_{k,m}$ a convex combination with suitable $\mu_{k,1},...,\mu_{k,m}$.
Proof. There are some $0<t_{k,j}<1$ for $1\le j\le m$ such that $s_{k,j}=(1-t_{k,j})p_k+t_{k,j}x_{k,j}$. Then $x_{k,j}=\frac{s_{k,j}-(1-t_{k,j})p_k}{t_{k,j}}$, hence $p_k= \lambda_{k,1}x_{k,1}+...+\lambda_{k,m}x_{k,m}=$ $\lambda_{k,1}\frac{s_{k,1}-(1-t_{k,1})p_k}{t_{k,1}}+... +\lambda_{k,m}\frac{s_{k,m}-(1-t_{k,m})p_k}{t_{k,m}}$. Solving for $p_k$ we obtain
$p_k[1+\lambda_{k,1}\frac{(1-t_{k,1})}{t_{k,1}}+... +\lambda_{k,m}\frac{(1-t_{k,m})}{t_{k,m}}]= \frac{\lambda_{k,1}}{t_{k,1}}s_{k,1}+... +\frac{\lambda_{k,m}}{t_{k,m}}s_{k,m}$, and
$p_k[1+\frac{\lambda_{k,1}}{t_{k,1}}-\lambda_{k,1}+... +\frac{\lambda_{k,m}}{t_{k,m}}-\lambda_{k,m}]= p_k[\frac{\lambda_{k,1}}{t_{k,1}}+... +\frac{\lambda_{k,m}}{t_{k,m}}] = \frac{\lambda_{k,1}}{t_{k,1}}s_{k,1}+... +\frac{\lambda_{k,m}}{t_{k,m}}s_{k,m}$.
Thus $p_k =[\frac{\lambda_{k,1}}{t_{k,1}}s_{k,1}+... +\frac{\lambda_{k,m}}{t_{k,m}}s_{k,m}]/[\frac{\lambda_{k,1}}{t_{k,1}}+... +\frac{\lambda_{k,m}}{t_{k,m}}]$. That is, coefficients $\mu_{k,j}=[\frac{\lambda_{k,j}}{t_{k,j}}]/[\frac{\lambda_{k,1}}{t_{k,1}}+... +\frac{\lambda_{k,m}}{t_{k,m}}]$ for $1\le j\le m$ work.

We may pick convergent subsequences several times (throwing out some $k$'s each time), first so that we may assume that the sequence $\{s_{k,1}:k\ge1\}$ is convergent to some $s_1\in S$, then we may assume that the sequence $\{\mu_{k,1}:k\ge1\}$ is convergent to some $\mu_1\in[0,1]$, then we may assume that the sequence $\{s_{k,2}:k\ge1\}$ is convergent to some $s_2\in S$, etc. In the end we may assume that for each fixed $j$ with $1\le j\le m$ the sequence $\{s_{k,j}:k\ge1\}$ is convergent to some $s_j\in S$, and the sequence $\{\mu_{k,j}:k\ge1\}$ is convergent to some $\mu_j\in[0,1]$. Since $p_k\to p$ we also have that $p=\mu_1s_1+...+\mu_m s_m\ ,$ a convex combination. If $T=\{s_1,...,s_m\}$ then $T\subset S\cap\overline{\mathrm{conv}(A)}$, and in particular $p\in\mathrm{conv}(T)\subset\overline{\mathrm{conv}(A)}$ (using that $\overline{\mathrm{conv}(A)}$ is convex). But $p$ is not an extreme point of $\mathrm{conv}(T)$ (and therefore $p$ cannot be an extreme point of $\overline{\mathrm{conv}(A)}$ either), which could be shown by induction on $m$. If $m=2$ then $p$ is an interior point of the line segment joining $s_1$ and $s_2$. If $m=3$ and $p$ does not lie on the line segment joining $s_2$ and $s_3$ then there is a point $q$ on this line segment so that $p$ is an interior point of the line segment joining $s_1$ and $q$. Etc, for $m\ge4$. (Or, we may just use that since $T$ is finite, all extreme points of $\mathrm{conv}(T)$ must be contained in $T$, and therefore in $S$, but $p\not\in S$. It could also be seen, though it is not needed for the proof, that $T$ is exactly the set of extreme points of $\mathrm{conv}(T)$, using that each point of $S$ is an extreme point for $\mathrm{conv}(S)$.)

$\endgroup$
  • $\begingroup$ That is just awsome! Thanks so much. I only read it once, but for now everything seems clear. I'll read it again later, anyway! $\endgroup$ – astrobarrel Sep 2 '19 at 7:40
  • $\begingroup$ @astrobarrel You are very welcome, thank you for reading my answer, I have been generously rewarded! I read it once more myself, there is one minor thing that I may or may not bother to correct: One cannot rule out (as my answer is written) that $x_{k,j}\in S$ sometimes, so $s_{k,j}=x_{k,j}$. One could correct this two ways: (a) At the beginning take $r$ small enough so that $\overline{B}$ misses $\overline{A}$ (which I realize I was assuming implicitly), or (b) don't bother with $r$, but instead replace the inequality $0<t_{k,j}<1$ with $0<t_{k,j}\le1$, then everything seems to formally work. $\endgroup$ – Mirko Sep 2 '19 at 12:45

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.