# Proof verification for some properties of convex hulls

Let $$X$$ be a normed vector space and $$A$$ be a subset of $$X$$. $$\operatorname{conv}(A)$$ is called the intersection of all convex subsets of $$X$$ that contain $$A$$

a) Show that $$\operatorname{conv}(A)$$ is a convex set

b) Show that

$$\operatorname{conv}(A) = \bigg\{\sum_{i=1}^n\lambda _i x_i : \sum_{i=1}^n \lambda_i =1, \lambda_i\ge 0, x_i\in A, i=1,\cdots,n\bigg\}$$

c) If $$A$$ is compact then is $$\operatorname{conv}(A)$$ compact?

d) Show that if $$A\subseteq \mathbb{R}^n$$ is compact then $$\operatorname{conv}(A)$$ is compact

a) Take two elements $$a$$ and $$b$$ at the intersection of all convex subsets of $$X$$ that contain $$A$$. Now take $$\lambda a + (1-\lambda)b$$. It is contained in every of the subsets of $$X$$ that contain $$A$$, therefore it is contained in the intersection. Q.E.D.

b)

[$$\Leftarrow$$] Suppose by induction that $$\sum_{i=1}^n\lambda_i x_i$$ belongs to $$\operatorname{conv}(A)$$. We must prove that $$\sum_{i=1}^{k+1}\lambda_i x_i$$, with $$\sum_{i=1}^{k+1}=1$$ also belongs.

$$\sum_{i=1}^{k+1}\lambda_i x_i = \sum_{i=1}^{k}\lambda_i x_i + \lambda_{k+1}x_{k+1} = \sum_{i=1}^{k}\lambda_i x_i + (1-\sum_{i=1}^n\lambda_i)x_{k+1}$$

Now choose $$\delta$$ such that $$\delta\sum_{i=1}^{k}\lambda_i=1$$, then

$$\frac{\delta}{\delta} \left(\sum_{i=1}^{k}\lambda_i x_i + (1-\sum_{i=1}^n\lambda_i)x_{k+1}\right)= \left(\frac{1}{\delta}\sum_{i=1}^{k}(\delta\lambda_i) x_i + \frac{1}{\delta}(\delta-1)x_{k+1}\right) =\\ \frac{1}{\delta}x + \left(1-\frac{1}{\delta}\right)x_{k+1}$$

which is a combination of elements of $$A$$ that sums to $$1$$

[$$\Rightarrow$$] Can I just say that $$x\in\operatorname{conv}(A)$$, then $$x = 1x + 0\cdot everything$$ therefore it is a combination that sums to $$1$$ of elements of $$A$$?

c) A hint is provided: show that $$\operatorname{conv}(A\cup B)$$ is the image by a continuous function of the compact $$\{(\alpha,\beta; \alpha,\beta\ge 0, \alpha + \beta = 1)\}\times A\times B$$. I don't understand how to show this.

d) Any hints?

• Your part $b$ is correct. For part $c$, recall that the image of a compact set under a continuous function is also compact. I am not sure what part $d$ is asking (i.e it seems the same as part $c$. – rubikscube09 Mar 2 '19 at 22:11
• Part b is not correct; you cannot conclude on the basis that $x = 1x$ that $x$ belongs to the proposed convex hull, as $x$ may not belong to $A$. Instead, try proving that the proposed convex hull is convex. If it is, then it is a convex set containing $A$, so if $x$ is not in this set, it must not be in the convex hull of $A$. – Theo Bendit Mar 2 '19 at 23:07
• d) is proved in Rudin's Functional Analysis. – Kavi Rama Murthy Mar 2 '19 at 23:48
• An interesting side note on part (d): it does not hold true in more general vector spaces--see this SE post. – David M. Mar 8 '19 at 3:14
• @rubikscube09 Part (c) is asking about a general normed vector space $X$, while part (d) is specific to the case $X=\mathbb{R}^n$. – David M. Mar 8 '19 at 13:34

Part a and the first implication of part b are correct.

For the converse of part $$b$$, note that writing $$x = 1x+0$$ does not make it a member of the RHS of the second conclusion, which requires that each element of the combination be in $$A$$, while $$x \notin A$$ may be possible.

Therefore, since you have shown that $$\mbox{conv}(A)$$ contains the LHS, showing that the LHS is convex and contains $$A$$ will show that it contains $$\mbox{conv}(A)$$.

That the RHS contains $$A$$ follows from $$x = 1x$$, where $$\color{blue}{x \in A}$$. Now we need to show that the RHS is convex.

So pick two elements, $$\sum_{i=1}^n \lambda_i x_i$$ and $$\sum_{j=1}^m \mu_j y_j$$, and a $$t \in [0,1]$$. We get: $$t\left(\sum_{i=1}^n \lambda_ix_i\right) + (1-t)\left(\sum_{j=1}^m \mu_jy_j\right) = \sum_{k=1}^{n+m} \xi_kz_k$$

where : $$\xi_k = \begin{cases} t\lambda_k \quad \quad \ \ \quad \quad k \leq n \\ (1-t)\mu_{k-n} \quad k > n \end{cases}$$

and : $$z_k = \begin{cases} x_k \quad \quad k \leq n \\ y_{k-n} \quad \ k > n \end{cases}$$

so all the $$z_k \in A$$ and $$\sum_{k=1}^{m+n} \xi_k = \sum_{i=1}^n t\lambda_i + \sum_{j=1}^n (1-t)\mu_j = t + 1-t = 1$$. $$\xi_k \geq 0$$ for all $$k$$ is clear.

Therefore , the set on the RHS is convex and contains $$A$$. In particular, therefore it contains $$\mbox{conv}(A)$$, completing the proof.

For part $$c$$, the example given in the link above by David suffices : I will reproduce and elaborate on it upon the request of OP.

For part $$d$$, just think of closure first. Fix $$x_n \in \mbox{conv}(A), x_n \to x$$, all we need to show is that $$x \in A$$.

Which seems very easy to see, and then when you look at the structure of $$\mbox{conv}(A)$$, realize is not a very easy task. The point is, each $$x_n$$ is an arbitrary finite convex combination of vectors from $$A$$, but finiteness still is not good enough : we'd like there to be an upper bound on the number of vectors in the linear combination, while keeping $$\mbox{conv}(A)$$ intact. This can be done in $$\mathbb R^d$$ at least:

Caratheodory Convexity Theorem : In $$\mathbb R^n$$, every vector in $$\mbox{conv}(A)$$ can be written as a convex combination of (no more than) $$\color{blue}{n+1}$$ vectors from $$A$$!

I'll adapt the proof from the source. Fix $$x \in \mbox{conv}(A)$$, and define the set $$T = \{k : x$$ can be written as a convex combination of $$k$$ elements of $$A\}$$. So $$T$$ is a non-empty subset of the natural numbers, and hence has a smallest element, say $$k$$. If we show $$k \leq n+1$$ we are done.

If not, then pick $$x_1,...,x_k \in A$$ and $$\alpha_1,...,\alpha_k$$ with $$\sum_1^k \alpha_i = 1$$ and $$x = \sum_1^k \alpha_ix_i$$. Since $$k-1 > n$$ , the set $$\{x_i-x_1 : 2 \leq i \leq k\}$$ has $$k-1$$ elements and hence is linearly dependent. Therefore, we can find $$\lambda_1,...,\lambda_{k-1}$$ not all zero such that $$\sum_{1}^{k-1} \lambda_j (x_{j+1} - x_1) = 0$$.

Let $$C_1 = -\sum_{1}^{k-1} \lambda_i$$ and $$C_j = \lambda_{j-1}$$ for $$2 \leq j \leq k$$, note that all the $$C_i$$ cannot be zero (one of $$C_2,...,C_k$$ is non-zero), and we have : $$\sum_{i=1}^k C_i = C_1 + \sum_{j=2}^k C_j = - \sum \lambda_i + \sum\lambda_i = 0$$

and : $$\sum C_ix_i = \left(-\sum \lambda_i\right) x_1 + \sum \lambda_jx_j = \sum \lambda_j(x_j - x_1)= 0$$

by choice of $$\lambda_i$$.

Let us assume WLOG that $$C_j > 0$$ for some $$j$$ (that is, we know one of them is non-zero, so we are assuming that this one is also positive : you can see how the argument changes if it is negative). Set $$C = \min\left\{\frac{\alpha_i}{C_i} : C_i > 0\right\}$$ (a non-empty set by choice) and let $$\frac{\alpha_m}{C_m} = C > 0$$. (That is, this is the $$m$$ for which the minimum is attained). We make some observations :

• $$\alpha_i - CC_i \geq 0$$ for all $$i$$ and $$\alpha_m - CC_m =0$$ by assumption.

• We have : $$\sum_{i=1}^k (\alpha_i - CC_i) = \sum \alpha_i - C\sum C_i = 1-0 = 1$$

• Furthermore : $$\sum_{i=1}^k (\alpha_i - CC_i)x_i = \sum \alpha_ix_i - C\sum C_ix_i = x-0 = x$$

Thus, we have written $$x$$ as a $$k$$-convex combination, but $$\alpha_m-CC_m = 0$$, so in fact the above is a $$k-1$$ convex combination of $$x_i$$ which remain elements of $$A$$. In other words, we have a contradiction since the above shows that $$k-1\in T$$, whose minimum was $$k$$.

This stemmed from the false assumption that $$k > n-1$$. Thus, as the conclusion desires, $$k \leq n-1$$.

Check out Helly's theorem as well!

But now with Caratheodory, what can we do? What we will do is show that $$\mbox{conv}(A)$$ is sequentially compact i.e. every sequence has a convergent subsequence within $$\mbox{conv}(A)$$. At least in $$\mathbb R^d$$ (it holds in more generality), compactness and sequential compactness are equivalent.

So pick a sequence $$x_i \in \mbox{conv}(A)$$. Write each $$x_i$$ as a $$d+1$$-convex combination, $$x_i = \sum_{j=1}^{d+1} \lambda_{ji}y_{ji}$$, in other words, $$x_i$$ is a convex combination of $$y_{1i},y_{2i},...,y_{(d+1)i}$$. We do a procedure which is quite common in functional analysis :

• Note that $$\lambda_{1i}$$, the sequence of "first coefficients" of each convex combination, is an infinite subset of the compact $$[0,1]$$, hence has a convergent subsequence. Call the subsequence $$\lambda_{n_k}$$, and let $$\lambda_{n_k} \to \lambda_1$$ as $$k \to \infty$$ where $$\lambda_1 \in [0,1]$$.

• Now, consider the sequence $$y_{n_k}$$, with $$n_k$$ as above. By sequential compactness, we get a further subsequence $$y_{n_{k_l}}$$ of this which converges in $$A$$, say $$y_{n_{k_l}} \to y_1$$ as $$l \to \infty$$. Note that $$y_1 \in A$$.

• Further, note that $$\lambda_{1n_{k_l}}$$ being a subsequence of a convergent sequence also converges to $$\lambda_1$$.

• Now, consider $$\lambda_{2n_{k_l}}$$, it has a convergent subsequence in $$[0,1]$$, some $$y_{n_{k_{l_m}}} \to \lambda_2$$. Note that $$y_{n_{k_{l_m}}}$$ is a subsequence of a convergent sequence and hence also goes to $$y_1$$.

• Now proceed iteratively, and stop at $$k$$ (the stopping at finite time ensures that you are always left with a subsequence : after infinitely many transitions you cannot guarantee that there will be any subsequence left!)

At the end , you obtain $$\lambda_i \in [0,1]$$ and $$y_i \in A$$ for $$1 \leq i \leq k$$, such that there is a subsequence (which we index by $$N$$) such that $$y_{iN} \to y_i$$ and $$\lambda_{iN} \to \lambda_i$$ for all $$1 \leq i \leq d+1$$.

Now we just have to complete a few checks :

• Each $$\lambda_i \in [0,1]$$.

• We have $$\sum_{i=1}^{d+1} \lambda_{iN} = 1$$ for all $$N$$, so dragging $$N \to \infty$$ gives us $$\sum_{i=1}^d \lambda_{i} = 1$$.

• We have $$y_{Ni} \to y_i$$ for all $$i$$ , hence by continuity of scalar multiplication we get $$\lambda_{Ni}y_{Ni} \to \lambda_iy_i$$ for all $$i$$. Taking the sum over $$i$$ gives $$x_{N} \to \sum_{i=1}^n \lambda_iy_i$$, a convex combination of vectors from $$A$$, hence belonging to $$\mbox{conv}(A)$$.

Which shows that $$\mbox{conv}(A)$$ is compact!

You might wonder if $$(d)$$ generalizes i.e. in spaces other than $$\mathbb R^d$$ can we get the same result ? Well, we have the following :

In a complete metric space $$(X,d)$$ with the topology induced by the metric, the convex hull(yes, this is the term for $$\mbox{conv}$$ !) of a compact set is totally bounded.

For clarification : a subset $$S$$ of a metric space is totally bounded if for each $$\epsilon >0$$ there are $$x_1,...,x_N \in S$$ ($$N$$ can vary with $$\epsilon$$) such that $$S \subset \cup_1^N B(x_i,\epsilon)$$. Or , for all very small values, $$S$$ can be covered by fintely many balls with radius that value.

This, combined with the general fact that (in a metric space) a set is compact if and only if it is closed and totally bounded, tells you :

The closed convex hull of a compact set is compact.

These are more difficult to prove, though, involving some other concepts.