User Tools
world:krein
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
world:krein [2026/04/10 15:48] rdouc [Krein-Milman, Choquet and Birkhoff-Von Neuman Theorems] |
world:krein [2026/04/11 08:26] (current) rdouc ↷ Page name changed from world:choquet to world:krein |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| {{page>:defs}} | {{page>:defs}} | ||
| - | ====== Krein-Milman, Choquet and Birkhoff-Von Neuman Theorems ====== | + | |
| + | ====== Krein-Milman and Birkhoff-Von Neuman Theorems ====== | ||
| <WRAP center round todo> | <WRAP center round todo> | ||
| Line 15: | Line 16: | ||
| <WRAP center round tip> | <WRAP center round tip> | ||
| - | **Theorem (Krein–Milman).** Let $E$ be a Euclidean space of dimension $n$ and $K \subset E$ convex, compact, non-empty. Then | + | **Theorem (Krein–Milman).** Let $E$ be an Euclidean space of dimension $n$ and $K \subset E$ convex and compact. Then |
| $$ | $$ | ||
| K = \mathrm{conv}(\mathrm{Extr}(K)). | K = \mathrm{conv}(\mathrm{Extr}(K)). | ||
| Line 27: | Line 28: | ||
| The proof proceeds by induction on $n$, the dimension of $E$. We assume the property is true for every Euclidean subspace of dimension $n-1$. Without loss of generality, we assume that $K$ is not reduced to a singleton. | The proof proceeds by induction on $n$, the dimension of $E$. We assume the property is true for every Euclidean subspace of dimension $n-1$. Without loss of generality, we assume that $K$ is not reduced to a singleton. | ||
| - | Let $x \in K$. Choose $y \in K \setminus \{x\}$ arbitrarily. Consider $[a,b]$ the maximal segment contained in $K$ and containing $[x,y]$. Since $a,b \in K$ and $x$ is a convex combination of $a,b$, it suffices to show that $a,b \in \mathrm{conv}(\mathrm{Extr}(K))$. We prove that $a \in \mathrm{conv}(\mathrm{Extr}(K))$ (the case $b \in \mathrm{conv}(\mathrm{Extr}(K))$ is similar). Since $a \in \partial K$, there exists a sequence $a_k \notin K$ converging to $a$ and for each $k$, we choose $u_k$ unitary such that for all $y \in K$, $\langle y-a_k,u_k \rangle \geq 0$. We can extract from $(u_k)$ a convergent subsequence on the unit sphere, and let $u$ be its limit. Passing to the limit yields $\langle y-a,u \rangle \geq 0$. Thus, defining $f(y)=\langle y-a,u \rangle$, we obtain that $a \in H_a=f^{-1}(0) \cap K=\mathrm{argmin}_{y\in K} f(y)$. The set $H_a$ is convex, compact, non-empty in a space of dimension $n-1$, and the induction hypothesis shows that $a \in \mathrm{conv}(\mathrm{Extr}(H_a))$. It remains to show that $\mathrm{Extr}(H_a) \subset \mathrm{Extr}(K)$. Indeed, since $f$ is linear, if $z \in \mathrm{Extr}(H_a)$ and $z=\lambda x + (1-\lambda) y$ with $x,y \in K$, then $f(z)=0=\lambda f(x) + (1-\lambda) f(y)$, hence $f(x)=f(y)=0$ (since $f\geq 0$ on $K$), which implies $x,y \in H_a$ and thus $\lambda \in \{0,1\}$ since $z \in \mathrm{Extr}(H_a)$. This shows that $z \in \mathrm{Extr}(K)$ and the proof is concluded. | + | Let $x \in K$. Choose $y \in K \setminus \{x\}$ arbitrarily. Consider $[a,b]$ a maximal segment contained in $K$ and containing $[x,y]$. Since $a,b \in K$ and $x$ is a convex combination of $a,b$, it suffices to show that $a,b \in \mathrm{conv}(\mathrm{Extr}(K))$. We prove that $a \in \mathrm{conv}(\mathrm{Extr}(K))$ (the case $b \in \mathrm{conv}(\mathrm{Extr}(K))$ is similar). Since $a \in \partial K$, there exists a sequence $a_k \notin K$ converging to $a$ and for each $k$, we choose $u_k$ unitary such that for all $y \in K$, $\langle y-a_k,u_k \rangle \geq 0$. We can extract from $(u_k)$ a convergent subsequence on the unit sphere, and let $u$ be its limit. Passing to the limit yields $\langle y-a,u \rangle \geq 0$. Thus, defining $f(y)=\langle y-a,u \rangle$, we obtain that $a \in H_a=f^{-1}(0) \cap K=\mathrm{argmin}_{y\in K} f(y)$. The set $H_a$ is convex, compact, non-empty in a space of dimension $n-1$, and the induction hypothesis shows that $a \in \mathrm{conv}(\mathrm{Extr}(H_a))$. It remains to show that $\mathrm{Extr}(H_a) \subset \mathrm{Extr}(K)$. Indeed, since $f$ is linear, if $z \in \mathrm{Extr}(H_a)$ and $z=\lambda x + (1-\lambda) y$ with $x,y \in K$, then $f(z)=0=\lambda f(x) + (1-\lambda) f(y)$, hence $f(x)=f(y)=0$ (since $f\geq 0$ on $K$), which implies $x,y \in H_a$ and thus $\lambda \in \{0,1\}$ since $z \in \mathrm{Extr}(H_a)$. This shows that $z \in \mathrm{Extr}(K)$ and the proof is concluded. |
| </hidden> | </hidden> | ||
| <WRAP center round todo> | <WRAP center round todo> | ||
| - | **Theorem (Choquet).** Let $E$ be a Euclidean space and $K \subset E$ convex compact such that $\mathrm{Extr}(K)$ is compact. Let $f : E \to \mathbb{R}$ be linear and continuous. Then $f$ attains its minimum on $K$ at a point of $\mathrm{Extr}(K)$. | + | **Corollary.** Let $E$ be an Euclidean space and $K \subset E$ convex and compact. Let $f : E \to \mathbb{R}$ be linear. Then $f$ attains its minimum on $K$ at a point of $\mathrm{Extr}(K)$. |
| </WRAP> | </WRAP> | ||
| Line 44: | Line 45: | ||
| B_n = \left\{ A = (a_{ij}) \in \mathcal{M}_n([0,1]) \mid \sum_{j=1}^n a_{ij} = 1,\ \sum_{i=1}^n a_{ij} = 1 \right\}. | B_n = \left\{ A = (a_{ij}) \in \mathcal{M}_n([0,1]) \mid \sum_{j=1}^n a_{ij} = 1,\ \sum_{i=1}^n a_{ij} = 1 \right\}. | ||
| $$ | $$ | ||
| - | Then $\mathrm{Extr}(B_n) = P_n$, the set of permutation matrices (i.e. matrices having exactly one $1$ in each row and each column). | + | Then $\mathrm{Extr}(B_n) = P_n$, the set of permutation matrices (i.e. matrices having exactly one $1$ in each row and each column and zeros everywhere else). |
| </WRAP> | </WRAP> | ||
world/krein.1775828924.txt.gz · Last modified: 2026/04/10 15:48 by rdouc
Page Tools
