Fdtxjr

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

a) Show that $operatornameconv(A)$ is a convex set

b) Show that

$$operatornameconv(A) = biggsum_i=1^nlambda _i x_i : sum_i=1^n lambda_i =1,
lambda_ige 0, x_iin A, i=1,cdots,nbigg$$

c) If $A$ is compact then is $operatornameconv(A)$ compact?

d) Show that if $Asubseteq mathbbR^n$ is compact then $operatornameconv(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^nlambda_i x_i $ belongs to $operatornameconv(A)$. We must prove that $sum_i=1^k+1lambda_i x_i $, with $sum_i=1^k+1=1$ also belongs.

$$sum_i=1^k+1lambda_i x_i = sum_i=1^klambda_i x_i + lambda_k+1x_k+1 = sum_i=1^klambda_i x_i + (1-sum_i=1^nlambda_i)x_k+1$$

Now choose $delta$ such that $deltasum_i=1^klambda_i=1$, then

$$fracdeltadelta left(sum_i=1^klambda_i x_i + (1-sum_i=1^nlambda_i)x_k+1right)= left(frac1deltasum_i=1^k(deltalambda_i) x_i + frac1delta(delta-1)x_k+1right) =\ frac1deltax + left(1-frac1deltaright)x_k+1$$

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

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

c) A hint is provided: show that $operatornameconv(Acup B)$ is the image by a continuous function of the compact $(alpha,beta; alpha,betage 0, alpha + beta = 1)times Atimes B$. I don't understand how to show this.

d) Any hints?

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 $mboxconv(A)$ contains the LHS, showing that the LHS is convex and contains $A$ will show that it contains $mboxconv(A)$.

That the RHS contains $A$ follows from $x = 1x$, where $colorbluex 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:
$$
tleft(sum_i=1^n lambda_ix_iright) + (1-t)left(sum_j=1^m mu_jy_jright) = sum_k=1^n+m xi_kz_k
$$

where :
$$
xi_k = begincases
tlambda_k quad quad quad quad k leq n \
(1-t)mu_k-n quad k > n
endcases
$$

and :
$$
z_k = begincases
x_k quad quad k leq n \
y_k-n quad k > n
endcases
$$

so all the $z_k in A$ and $sum_k=1^m+n xi_k = sum_i=1^n tlambda_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 $mboxconv(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 mboxconv(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 $mboxconv(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 $mboxconv(A)$ intact. This can be done in $mathbb R^d$ at least:

Caratheodory Convexity Theorem : In $mathbb R^n$, every vector in $mboxconv(A)$ can be written as a convex combination of (no more than) $colorbluen+1$ vectors from $A$!

I'll adapt the proof from the source. Fix $x in mboxconv(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 + sumlambda_i = 0
$$

and :
$$
sum C_ix_i = left(-sum lambda_iright) 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 = minleftfracalpha_iC_i : C_i > 0right$ (a non-empty set by choice) and let $fracalpha_mC_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 - Csum C_i = 1-0 = 1
  $$




• Furthermore :
  $$
  sum_i=1^k (alpha_i - CC_i)x_i = sum alpha_ix_i - Csum 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-1in 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 $mboxconv(A)$ is sequentially compact i.e. every sequence has a convergent subsequence within $mboxconv(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 mboxconv(A)$. Write each $x_i$ as a $d+1$-convex combination, $x_i = sum_j=1^d+1 lambda_jiy_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_Niy_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 $mboxconv(A)$.

Which shows that $mboxconv(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 $mboxconv$ !) 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.