# The extreme points of $\overline{\mathrm{conv}(A)}$ are in $\overline{A}$

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!

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

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 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)$$.)

• 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! – astrobarrel Sep 2 '19 at 7:40
• @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. – Mirko Sep 2 '19 at 12:45