6
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ This is a very easy question, but one I would considering answering only if the poster identified himself/herself. $\endgroup$ Feb 18, 2010 at 2:21
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 18, 2010 at 2:50
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 18, 2010 at 3:01
  • $\begingroup$ 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). $\endgroup$ Feb 18, 2010 at 3:07
  • $\begingroup$ Well I'll change my screen name if that is more comfortable here. $\endgroup$ Feb 18, 2010 at 3:44

7 Answers 7

8
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 18, 2010 at 3:42
  • 1
    $\begingroup$ 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... $\endgroup$
    – fedja
    Feb 18, 2010 at 14:48
  • $\begingroup$ 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? $\endgroup$ Feb 19, 2010 at 18:01
  • $\begingroup$ As folklore. I doubt I am the first (or even the fifty first) to mention it :). $\endgroup$
    – fedja
    Feb 19, 2010 at 19:40
  • 2
    $\begingroup$ BTW, the general case follows from the separable case because the linear span of a compact set is always separable. $\endgroup$ Sep 17, 2010 at 9:21
6
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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.) $\endgroup$ Feb 18, 2010 at 2:38
  • 1
    $\begingroup$ 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.) $\endgroup$ Feb 18, 2010 at 2:45
  • 3
    $\begingroup$ 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. $\endgroup$ Feb 18, 2010 at 10:45
  • 3
    $\begingroup$ @Gerald: Interesting. Du you have a reference? $\endgroup$ Feb 18, 2010 at 12:06
  • 1
    $\begingroup$ @Gerald: HB does not imply AC, I infer from your remark that KM does not imply HB as well as KM does not imply AC. Without HB does "nonempty compact convex set has an extreme point" (EP) still imply KM? It appears KM always implies EP. My work does not avoid Hahn-Banach, I'm just asking out of curiosity. Having opened the can of worms, I might as well get to the bottom of it. $\endgroup$ Feb 18, 2010 at 21:11
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes it seems clear that nobody has an "elementary" proof that there is an extreme point, so I suspect there probably isn't one. $\endgroup$ Feb 18, 2010 at 2:39
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – LSpice
    Feb 18, 2010 at 2:32
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 18, 2010 at 2:36
  • $\begingroup$ 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. $\endgroup$
    – LSpice
    Feb 18, 2010 at 2:49
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

Here is Greg's proof of the Krein-Milman theorem (only the existence part).

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.

Sub-claim 1: $U^{+}\cap A\subset\operatorname{cl}_{A}U^{+}$ strictly.

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{array}[t]{lrclll} &f &: &\mathbb{F} &\to &V\\ &&: &s &\mapsto &s~x+(1-s)~y\\ \end{array}$$

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)

Sub-claim 2: If $W\subseteq A$ is convex, then $U^{+}\cup W$ is convex.

Proof (sub-claim 2): Fix $x\in U^{+}\cap A,t\in(0,1)$. Consider the map

$$\begin{array}[t]{lrclll} &T &: &V &\to &V\\ &&: &y &\mapsto &t~x+(1-t)~y\\ \end{array}$$

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{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)

Sub-claim 3: $A\setminus U^{+}$ is a singleton.

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)

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Sep 17, 2010 at 8:48
-4
$\begingroup$

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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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