1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – rubikscube09 Mar 2 '19 at 22:11
  • $\begingroup$ 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$. $\endgroup$ – Theo Bendit Mar 2 '19 at 23:07
  • $\begingroup$ d) is proved in Rudin's Functional Analysis. $\endgroup$ – Kavi Rama Murthy Mar 2 '19 at 23:48
  • $\begingroup$ An interesting side note on part (d): it does not hold true in more general vector spaces--see this SE post. $\endgroup$ – David M. Mar 8 '19 at 3:14
  • $\begingroup$ @rubikscube09 Part (c) is asking about a general normed vector space $X$, while part (d) is specific to the case $X=\mathbb{R}^n$. $\endgroup$ – David M. Mar 8 '19 at 13:34
0
$\begingroup$

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.


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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