Convex Hulls and Topology

Theorem. (Carathéodory’s theorem) Suppose that $A \subset X$ and its convex hull $\text{co}(A)$ has finite dimension $m$ . Then each point $x\in\text{co}(A)$ is the convex combination of at most $m+1$ points in $A$ .

Proof. For each $x \in \text{co}(A)$ , we can write $x = \sum_{j=0}^{n}\lambda_{j}x_{j}$ , where $\lambda_{j} > 0$ and $x_{j} \in A$ (distinct points). I claim that $n\leq m$ . Suppose $n > m$ . Set $B := \left\{x_{0},\cdots,x_{n}\right\}$ . Then since $B \subset A$ , we have that

$\displaystyle\dim(\text{aff}(B)) \leq\dim(\text{aff}(A))=m\leq n-1$ ,

which implies that $x_{1} - x_{0},\cdots,x_{n}-x_{0}$ are linearly dependent in the translated linear space giving $\text{aff}(A)$ . Hence, there exist coefficients $\alpha_{1},\cdots,\alpha_{n} \in \mathbb{R}$ , not all zero, such that $\sum_{j=1}^{n}\alpha_{j}(x_{j} - x_{0}) = 0$ . Rearranging, we obtain

$\displaystyle0=\underbrace{-\left(\sum_{j=1}^{n}\alpha_{j}\right)}_{:= \alpha_{0}}x_{0}+\sum_{j=1}^{n}\alpha_{j}x_{j}$

Observe that $\sum_{j=0}^{n}\alpha_{j} = 0$ , so there exists some $k, 0 \leq k \leq n$ , such that $\alpha_{k} > 0$ . Therefore we can choose $t > 0$ such that $\beta_{j} := \lambda_{j} - t\alpha_{j} \geq 0$ , for $0 \leq j \leq n$ , and $\beta_{j} = 0$ for at least one $j$ . Hence,

$\displaystyle x=\sum_{j=0}^{n}\lambda_{j}x_{j}=\sum_{j=0}^{n}(\beta_{j}+t\alpha_{j})x_{j}=\sum_{j=0}^{n}\beta_{j}x_{j}+t\sum_{j=0}^{n}\alpha_{j}x_{j}=\sum_{{j \neq k}}\beta_{j}x_{j}$ ,

since $\sum_{j=0}^{n}\alpha_{j}x_{j} = 0$ by construction. Since $\sum_{j=0}^{n}\alpha_{j} = 0$ , we obtain that

$\displaystyle\sum_{j=0}^{n}\beta_{j} = \sum_{j=0}^{n}\lambda_{j} + t\sum_{j=0}^{n}\alpha_{j} = 1$ ,

which implies that $x$ is a convex combination of $n-1$ points in $A$ . $\Box$

Lemma. If $U$ is a convex set in a linear normed space, then both $\text{int}(U)$ and $\overline{U}$ are convex.

Proof. Suppose $x,y \in \overline{U}$ . Then there exist sequences $(x_{n})_{n=1}^{\infty}, (y_{n})_{n=1}^{\infty} \subset U$ such that $x_{n} \rightarrow x, y_{n} \rightarrow y$ . For $\lambda \in [0,1]$ , we then have that

$\displaystyle\lambda x+(1-\lambda) y=\lim_{n\rightarrow\infty }\lambda x_{n}+(1-\lambda)y_{n}\in\overline{U}$

To see that $\text{int}(U)$ is convex, let $x,y \in U$ and choose $\epsilon > 0$ such that $u \in B_{\epsilon}(0) \Rightarrow x+u, y+u \in U$ . Since $\text{int} U \subset U$ , $\lambda x + (1-\lambda)y \in U$ , so that, for $u \in B_{\epsilon}(0)$ ,

$\displaystyle\lambda x+(1-\lambda)y+u=\lambda (x+u)+(1-\lambda)(y+u)\in U$ ,

since $x+u,y+u \in U$ and $U$ is convex by hypothesis. $\Box$

Lemma. If $U$ is an open set in a linear normed space $X$ , then $\text{co}(U)$ is open. If $X$ is finite dimensional and $K \subset X$ is compact, then $\text{co}(K)$ is compact.

Proof. Let $x =\sum_{j=0}^{m}\lambda_{j}x_{j}$ be the convex combination of points in $U$ . For each $j = 0,\cdots,m$ , there exists $r_{j} > 0$ such that $B_{r_{j}}(x_{j}) \subset U$ . Choose $\epsilon > 0$ such that $\epsilon \leq \min_{0 \leq j \leq m} x_{j}$ . For $u \in B_{\epsilon}(0), x_{j} + u \in U \ \forall j$ , and therefore

$\displaystyle x+u=\sum_{j=0}^{m}\lambda_{j}x_{j}+\left(\sum_{j=0}^{m}\lambda_{j}\right)u=\sum_{j=0}^{m}\lambda_{j}(x_{j}+u)\in\text{co}(U)$

Now suppose that $X$ is a $n$ -dimensional linear normed space and $K \subset X$ is compact. Define a function $f$ by

$\begin{array}{lcl}\displaystyle f:\left\{(\lambda_{0},\cdots,\lambda_{n},x_{0},\cdots,x_{n})\in\mathbb{R}^{n+1}\times K^{n+1}:x_{j}\in K,\lambda_{j}\in[0,1], \sum_{j=0}^{n}\lambda_{j}=1\right\}\rightarrow X,\\\displaystyle f(\lambda_{0},\cdots,\lambda_{n},x_{0},\cdots,x_{n}):=\sum_{j=0}^{n}\lambda_{j}x_{j}\end{array}$

$f$ is evidently a continuous map, and by Carathéodory’s theorem, the image of $f$ is $\text{co}(K)$ . By repeated application of the Bolzano-Weierstrass theorem, we see that the domain of $f$ is compact. Hence, the image of $f$ is compact, which shows that $\text{co}(K)$ is compact. $\Box$

While the convex hull of an open set is again open, as shown above, the convex hull of a closed subset of a linear normed space need not be closed. Indeed, consider the set in $\mathbb{R}^{2}$ given by $E: \left\{(0,0)\right\}\cup\left\{(1,n)\in\mathbb{Z}^{2}: n\geq 0\right\}$ . It is evident that $E^{c}$ is open, hence $E$ is closed. I claim that

$\displaystyle\text{co}(E)=\left\{(x,y)\in\mathbb{R}^{2}: 0\leq x\leq 1, 0\leq y<\infty\right\}\setminus\left\{(0,y)\in\mathbb{R}^{2}: y>0\right\}=:F$

To see that $F$ is closed, we show that $F^{c}$ is not open. The point $(0,1)\notin F$ , but for any $\epsilon > 0$ given, we can choose $n\in\mathbb{Z}^{\geq 1}$ sufficiently large so that $\frac{1}{n}<\epsilon$ and therefore the convex combination

$\displaystyle\left|\frac{n-1}{n}(0,0)+\frac{1}{n}(1,n)-(0,1)\right|<\epsilon$

We now show that $F$ is convex. Fix $(x_{1},y_{1}),(x_{2},y_{2})\in F$ and let $\lambda\in[0,1]$ . Then

$\displaystyle\min\left\{x_{1},x_{2}\right\}\leq\lambda x_{1}+(1-\lambda)x_{2}\leq\max\left\{x_{1},x_{2}\right\},\indent\min\left\{y_{1},y_{2}\right\}\leq\lambda y_{1}+(1-\lambda)y_{2}\leq\max\left\{y_{1},y_{2}\right\}$

which implies that $\lambda (x_{1},y_{1})+(1-\lambda)(x_{2},y_{2})\in F$ . Hence, $\text{co}(E)\subset F$ . For the reverse inclusion, fix a convex combination $\sum_{k=1}^{n}\lambda_{k}(x_{k},y_{k})$ . Since $x_{k}\in\left\{0,1\right\}$ , it is immediate that $\sum_{k=1}^{n}\lambda_{k}x_{k}\in [0,1]$ . Analogously,

$\displaystyle\sum_{k=1}^{n}\lambda_{k}y_{k}=\sum_{{1\leq k\leq n}\atop{\lambda_{k}\neq 0}}\lambda_{k}y_{k}\geq 0$ ,

with equality if and only if all the $\lambda_{k}$ are zero.

It’s worth mentioning that every closed set in $\mathbb{R}$ has closed convex hull. This result is immediate from an elementary lemma.

Lemma. Let $E\subsetneq\mathbb{R}$ be a nonempty closed, convex subset. Then exactly one of the following holds:

$E= [a,b]$ , where $-\infty<a\leq b<\infty$ ;

$E=(-\infty,b]$ , where $-\infty<b<\infty$ ;

$E=[a,\infty)$ , where $-\infty<a<\infty$ .

Proof. Fix a nonempty closed, convex subset $E\subsetneq\mathbb{R}$ . Define $a:=\inf E$ and $b:=\sup E$ . Suppose first that $E$ is bounded, so that $a$ and $b$ are both finite. Since $E$ is closed, $a\in E$ and $b\in E$ , so that $E=[a.b]$ .

Now suppose that $E$ is unbounded. If $a=\inf E$ is finite, then $\sup E=\infty$ and $E=[a,\infty)$ . If $b=\sup E$ is finite, then $\inf E=-\infty$ and $E=(-\infty,b]$ . $\Box$

It is not a coincidence that we had to consider a closed set whose convex hull was unbounded in order to demonstrate that the convex hull of a closed set need not be closed. Indeed, a consequence of Carathéodory’s theorem is that the convex hull of a compact set $K$ in a finite-dimensional normed space is also compact. Since the Heine-Borel theorem equates compactness with closed and bounded (in finite-dimensional spaces), a closed set $E$ such that $\text{co}(E)$ is not closed is necessarily unbounded.

About these ads

One Response to Convex Hulls and Topology

Pingback: Helly’s Theorem and Applications | Math by Matt