# Extreme point compact convex set.

The Krein-Milman theorem shows that a compact convex set in a Hausdorff locally convex topological vector space is the convex hull of its extreme points.

It seems this implies that a compact convex set in such a space must have an extreme point.

I am interested in whether there is a very simple elementary argument that shows that a compact convex set must have an extreme point.

I have such an argument, but since it uses compactness of the unit ball, it is not so good if the space is infinite dimensional.

In point of fact, I am using this in R^n, but if there is a way to put it that can generalize to infinite dimensions then that would seem preferable for the students.

-
This is a very easy question, but one I would considering answering only if the poster identified himself/herself. –  Bill Johnson Feb 18 '10 at 2:21
Is my identity not visible in my profile? I am Andrew Mullhaupt. It appears, based on the answers that nobody has what I asked for: A very simple elementary argument. Although I suppose the point is I thought "elementary" would rule out appealing to any of the machinery that appears to be required (Hahn-Banach, AOC, Zorn). This is OK. I will simply keep to the finite dimensional case in my exposition. –  Andrew Mullhaupt Feb 18 '10 at 2:50
Andrew, no, your identity isn't visible in your profile. We can see your user name, age, and affiliation, when you were last seen, and how long you've been a member, but not your real name. Not everyone chooses to use their real name as their username, but I believe it's encouraged for one reason and another. –  Tom Leinster Feb 18 '10 at 3:01
No, it was not, Andrew, as only your affiliation shows. As you can see from the comments, proving the existence of extreme points is essentially the same as proving the entire theorem. This is, in fact, used for proving many other theorems (e.g., that in a separable conjugate space, every weak* closed bounded convex set is the normed closure of the convex hull of its extreme points). –  Bill Johnson Feb 18 '10 at 3:07
Well I'll change my screen name if that is more comfortable here. –  Andrew Mullhaupt Feb 18 '10 at 3:44

In fact, the standard proof of Krein–Milman first proves the existence of an extreme point. Note (or recall) that a face $F$ of a convex set $K$ is defined by the requirement that, if $tx+(1-t)y\in F$ for $0<t<1$ and $x,y\in K$, then $x,y\in F$. Hence an extreme point is just a singleton face. The existence of an extreme point is shown by using Zorn's lemma (or Hausdorff maximality lemma) to show the existence of a minimal, nonempty, closed face. Use Hahn–Banach to show the minimal face is a singleton: If a continuous linear functional separates two points in $F$, then the set where it achieves its maximum in $F$ is a smaller face. (And to get started, note that $K$ is a face in itself, so faces do indeed exist.)

-
Well that works, but it's not as simple as I hoped. Can one avoid appealing to Hahn-Banach, Zorn's, AOC? In finite dimensions the closed ball is a compact set with every boundary point as an extreme point. Then the minimal closed ball which contains a compact convex set K has nonempty intersection with the boundary of the ball (circumscribing sphere). Any such point z is an extreme point of K. (Any segment in K which meets z is a segment in the ball which meets z, so z is an endpoint of the segment, hence extreme in K.) –  Andrew Mullhaupt Feb 18 '10 at 2:38
No, in the infinite dimensional case I don't really see any way to simplify this. As you say, in a finite dimensional space your proof works. It clearly also works for a compact convex set in a Banach space whose unit vectors are extreme points of the unit ball, such as Hilbert spaces or $L^p$ spaces with $1<p<\infty$. Compactness of the unit ball is not necessary. (Just take an element of $K$ with maximal norm.) –  Harald Hanche-Olsen Feb 18 '10 at 2:45
Yes I see your point that I don't need compactness of the unit ball. The infinite dimensional spaces that appear in this field are normally Hilbert spaces, Hardy spaces, and sometimes L^p, so maybe this argument is not a total loss in infinite dimensions. –  Andrew Mullhaupt Feb 18 '10 at 3:24
It is known that Krein-Milman (KM) cannot be proved in ZF, so some choice is required. On the other hand, ZF+KM is strictly weaker than ZFC. And, interestingly, adding Hahn-Banach gets us equivalence... In ZF, AC is equivalent to KM+HB. –  Gerald Edgar Feb 18 '10 at 10:45
@Gerald: Interesting. Du you have a reference? –  Harald Hanche-Olsen Feb 18 '10 at 12:06

The main question is what generality you want. As soon as you have just one strictly convex function in the space, any point where it attains its maximum on $K$ is an extreme point. If we were talking about separable normed spaces, the construction of such function would be trivial: $F(x)=\sum_j 2^{-j}(1+\|x_j\|)^{-1}\|x-x_j\|$ where $x_j$ is any countable dense set would work just fine. In a strictly convex normed space $F(x)=\|x\|$ would be an even simpler example. The problem is that you want it in an abstract locally convex topological linear space, so some form of AC seems, indeed, inavoidable.

-
I should have been clear that I was looking for a simplicity/generality trade off. I just didn't want to use a needlessly finite dimensional proof just because it's a finite dimensional matter at hand, short of using high caliber results which are out of scope. I like your suggestion. –  Andrew Mullhaupt Feb 18 '10 at 3:42
This whole thing reminds me of a story my advisor told me once. The time is late fifties; a graduate student is ready to defend his thesis and is talking to one of the professors from the thesis committee: P: I regret to say it but, since you used the Hahn-Banach theorem in your thesis, I'll have to vote against it. S: But, but, but... But I used it only in a separable space! P: Hmm... You say only in separable? Well, I guess I can let it slip then... –  fedja Feb 18 '10 at 14:48
This question was for a mathematical preliminary section in some lecture notes I am writing. If I use it, how should I cite the example you gave? –  Andrew Mullhaupt Feb 19 '10 at 18:01
As folklore. I doubt I am the first (or even the fifty first) to mention it :). –  fedja Feb 19 '10 at 19:40
BTW, the general case follows from the separable case because the linear span of a compact set is always separable. –  Sergei Ivanov Sep 17 '10 at 9:21

The beef of the Krein-Milman theorem is the fact that each face of your compact convex set K has an extreme point; the statement about the (closed) convex hull then follows from a swift application of Hahn-Banach. Now notice that a face of K is itself compact and convex. So the difficulty of proving the Krein-Milman theorem is pretty much equal to the difficulty of proving that every compact convex set has an extreme point.

-
Yes it seems clear that nobody has an "elementary" proof that there is an extreme point, so I suspect there probably isn't one. –  Andrew Mullhaupt Feb 18 '10 at 2:39

What is easy is going from "there is at least one extreme point" to "closed convex hull of extreme points". So what you are asking for is essentially the proof of the whole thing.

-
It seems to me that zenpharaoh's comment is legitimate: One can deduce from the Krein&ndash;Milman theorem that a non-empty, compact, convex set has extreme points. (Whether one should so deduce it is another question, of course.) I don't remember the proof&mdash;is it really that easy to prove the implication that you mention? –  L Spice Feb 18 '10 at 2:32
Yes, it is that easy. If the closed convex hull $K_0$ of the extreme boundary is not all of $K$, separate $K_0$ from some other point in $K$ with a linear functional and consider the face on which this functional takes its maximum. –  Harald Hanche-Olsen Feb 18 '10 at 2:36
Ah, yes, easy in the presence of Hahn-Banach! I apologise for the abominable formatting in my previous sub-comment. I can never remember how much Markdown is allowable in them, as opposed to in 'major' comments. –  L Spice Feb 18 '10 at 2:49

See Prof. Greg Hjorth's Measure theory notes 2010. It contains a full proof.

-

Here is Greg's proof of the Krein-Milman theorem (only the existence part). My apologies about the TeX: i don't know what does or doesn't work on this site, so I've excluded the begin…end environments, but placed headings to guide the reader.

Proposition 1: Let $A\subseteq V$ be a non-empty compact convex set of an hausdorff locally convex semi-topological vector space (over some field which contains the reals topologically). Then $A$ has an extreme point.

Specifically we shall show that every non-empty convex open-in-$A$ proper subset $U^{-}$, has an extension to a convex open-in-$A$ proper subset $U^{+}\supseteq U^{-}$, for which $A\setminus U^{+}=\{e\}$ some extreme point $e$.

Proof (Prop 1): If $A$ is a singleton, we are done. So suppose otherwise. First notice we can separate two points by a convex open set, $U$, yielding $U^{-}=U\cap A$ a convex proper subset open in $A$. So fix such a set $U^{-}$.

Now let $\mathbb{P}:=\{W:U^{-}\subseteq W\mbox{ convex proper subset open in }A\}$.
We claim that the p.o. $(\mathbb{P},\subseteq)$ has the Zorn property.
Clearly the union of any chain of convex subsets open in $A$,
is again a convex subset open in $A$. Suppose \it{per contra} that
a union of a chain $\mathcal{C}\subseteq\mathbb{P}$ is equal to $A$.
Then since $A$ is compact, there must be a finite sub(chain) $\mathcal{C}'\subseteq\mathcal{C}$
for which $\operatorname{max}(\mathcal{C}')=\bigcup\mathcal{C}'=A$, which contracts
the properties of members of $\mathbb{P}$. Thus $\mathbb{P}$ is non-empty
and has the Zorn property. So fix $U^{+}$ open such that $U^{+}\cap A\in\mathbb{P}$ maximal.

\textbf{Sub-claim 1:}
$U^{+}\cap A\subset\operatorname{cl}_{A}U^{+}$ strictly.\\
\textbf{Proof (sub-claim 1):}
Let $x\in U^{+}\cap A$ and $y\in A\setminus U^{+}$.
Consider the map (here we need the underlying field to contain the reals topologically)\\
\begin{math}\begin{array}[t]{lrclll}
&f &: &\mathbb{F} &\to &V\\
&&: &s &\mapsto &s~x+(1-s)~y\\
\end{array}\end{math}\\
which is continuous and affine.
Thus the set $S:=\{s\in[0,1]:s\mapsto s~x+(1-s)~y\in U^{+}\cap A\} =[0,1]\cap f^{-1}U^{+}\cap f^{-1}A)$
is a convex. The set $f^{-1}A$ is closed convex and contains $0,1$,
thus contains $[0,1]$. So $S=[0,1]\cap f^{-1}U^{+}$ which is convex open
in $[0,1]$. Since $0\notin S$ and $1\in S$, then $S=(a,1]$ some $a\in[0,1)$.
Clearly $f(a)=lim_{s\searrow a}f(s)$ which is a limit of vectors from $U^{+}\cap A$,
and thus lies in $\operatorname{cl}U^{+}$. It also clearly lies in $A$,
since $f^{-1}A\supseteq[0,1]$. We also have $f(a)\notin U^{+}$.
Thus $\operatorname{cl}_{A}U^{+}\setminus U^{+} =A\cap\operatorname{cl}U^{+}\setminus U^{+} \supseteq\{f(a)\}$.
Thus the containment is strict.
QED (sub-claim 1)

\textbf{Sub-claim 2:}
If $W\subseteq A$ is convex, then $U^{+}\cup W$ is convex.\\
\textbf{Proof (sub-claim 2):}
Fix $x\in U^{+}\cap A,t\in(0,1)$. Consider the map\\
\begin{math}\begin{array}[t]{lrclll}
&T &: &V &\to &V\\
&&: &y &\mapsto &t~x+(1-t)~y\\
\end{array}\end{math}\\
This is continuous and affine. By the proposition below,
we also see that $T(\operatorname{cl}(U^{+}))\subseteq U^{+}$.
So $A\cap T^{-1}U^{+}$ is convex, open in $A$, and contains $A\cap\operatorname{cl}(U^{+})$
which strictly contains $U^{+}\cap A$ by Claim 1. Thus by maximality of $U^{+}$ in $\mathbb{P}$,
$A\cap T^{-1}U^{+}\overset{\mbox{\tiny must}}{=}A$. In particular, $T^{-1}U^{+}\supseteq A$,
and so $TW\subseteq TA\subseteq U^{+}$. Utilising such maps as $T$,
we see that a convex-linear combination of any pair of
elements from $U^{+}\cup W$ is contained in $U^{+}\cup W$.
QED (sub-claim 2)

\textbf{Sub-claim 3:}
$A\setminus U^{+}$ is a singleton.\\
\textbf{Proof (sub-claim 3):}
Else, let $x_{1},x_{2}\in A\setminus U^{+}$ distinct.
Let $W$ be a convex open set separating $x_{1}$ from $x_{2}$.
Then by Claim 3, $U^{+}\cap A\cup W\cap A$ is convex open in $A$.
Since $x_{1}\in W\setminus U^{+}$, this convex set is strictly large than
$U^{+}\cap A$. By maximality of $U^{+}$ in $\mathbb{P}$,
we have that $U^{+}\cap A\cup W\cap A=A\ni x_{2}$. But this contradicts
the fact that $x_{2}\notin U^{+}\cup W$.
QED (sub-claim 3)

At last, we claim that the point $e\in A\setminus U^{+}$ is extreme in A.
Consider $x,y\in A$
and $t\in(0,1)$ for which $tx+(1-t)y=e$. Case by case, we see
that if $x,y\in U^{+}$ then $e=tx+ty\in U^{+}$.
If $x\in A\setminus U^{+}$, $y=\frac{e-tx}{1-t}=\frac{e-te}{1-t}=e=x$.
If $y\in A\setminus U^{+}$, then $x=e=y$ similarly.
Thus $e$ is extreme.


QED(Prop 1)

Proposition 2: Let $A\subseteq V$ be a convex subset of a semi-topological space, and $x,y$ be vectors lying respectively in the closure and interior of $A$. Then for any $t\in(0,1)$, we have $tx+(1-t)y\in A$.

Proof: Let $U$ be an open neighbourhood of $y$, contained in $A$. Observe that $x-t^{-1}(1-t)(U-y)$ is an open neighbourhood of $x$, and thus meets $A$, say at $x'$. Thus $x\in x'+t^{-1}(1-t)(U-y)$ implying $tx+(1-t)y\in tx'+(1-t)U \subseteq tA+(1-t)A \subseteq A$, since $A$ is convex. QED(Prop 2)

-
The idea was to try and get a proof that a convex set has an extreme point without using any of the "transcendental" lemmata - like Axiom of Choice, Zorn's Lemma, Hahn-Banach, etc. In complete generality, it appears that Krein Milman requires at least one of these big guns. On the other hand, we also found that my simple proof works in most of the spaces I care about, and the other proof (construct any strictly convex function in the space) is even simpler and can work in all the spaces I care about; I used that approach in my notes. –  Andrew Mullhaupt Sep 17 '10 at 8:48

just suppose that point x is the point in the compact set that has the largest norm (Euclidean norm, L2). Let's now prove that it is actually a extreme point because otherwise we can choose x = 1/2 ( y + z) where y, z are points not identical to x. But because x has the largest norm, one can prove that under condition y and z has norm less or equal than x, but x is the middle point of the segment [y, z], it leads to the conclusion that x = y = z, which contradicts!

-
False: look at the unit ball of $\ell_\infty^n$ –  Yemon Choi Jan 4 at 0:04
Your argument only works if the norm is strictly convex –  Yemon Choi Jan 4 at 0:53
L2 by default.... –  dragonxlwang Jan 5 at 1:02
The question is asking about general Banach spaces. The problem is trivial for Hilbert space. –  Yemon Choi Jan 5 at 3:11