A nice counterexample in Convex Analysis

[gugo82]

Here's a nice and interesting counterexample for all analysts and geometricians.

*** Prerequisites ***

Let [tex]$(X,||\cdot ||)$[/tex] be a (real) normed vector space.

A subset [tex]$C\subseteq X$[/tex] is said to be convex iff the following holds:

[tex]$\forall x,y\in C \text{ and } \forall \lambda \in [0,1],\ \lambda \ x+(1-\lambda )\ y\in C$[/tex].

The property in the previous definition can readily be extended by induction: in fact, one can show that [tex]$C$[/tex] is convex iff [tex]$\sum_{i=1}^{n} \lambda_i\ x_i \in C$[/tex] for all [tex]$n\in \mathbb{N}$[/tex], all [tex]$x_1,\ldots ,x_n \in C$[/tex] and all [tex]$\lambda_1,\ldots ,\lambda_n \in [0,1]$[/tex] with [tex]$\sum_{i=1}^{n} \lambda_i =1$[/tex].
A sum of the type [tex]$\sum_{i=1}^{n} \lambda_i\ x_i $[/tex] with coefficients [tex]$\lambda_i \in [0,1]$[/tex] s.t. [tex]$\sum_{i=1}^n \lambda _i=1$[/tex] is said convex combination of [tex]$x_1,\ldots ,x_n$[/tex].

The class [tex]$\mathcal{C}:=\{ C\subseteq X:\ C \text{ is convex}\}$[/tex] is closed under intersection, in the sense that the intersection [tex]$\bigcap_{i\in \mathfrak{I}} C_i$[/tex] of a family [tex]$\{ C_i\}_{i\in \mathfrak{I}} \subseteq \mathcal{C}$[/tex] is convex; in other words, each family of [tex]$\mathcal{C}$[/tex] has a greatest lower bound in [tex]$\mathcal{C}$[/tex].

This fact allows to define what one means with "convex hull": in fact, if [tex]$Y$[/tex] is a nonempty subset of [tex]$X$[/tex] the convex hull of [tex]$Y$[/tex] in [tex]$X$[/tex], denoted [tex]$\text{conv} Y$[/tex], is the least convex set which contains [tex]$Y$[/tex]; in other words:

[tex]$\text{conv} Y :=\bigcap_{C\in \mathcal{C},\ Y\subseteq C} C$[/tex].

A characterization of the convex hull follows:

[tex]$\text{conv} Y=\{ y\in X:\ y \text{ is a convex combination of a finite number of points in } X\}$[/tex]

i.e. [tex]$y\in \text{conv} Y$[/tex] iff there exists [tex]$x_1,\ldots ,x_n \in X$[/tex] and [tex]$\lambda_i\in [0,1]$[/tex] with [tex]$\sum_{i=1}^{n} \lambda_i =1$[/tex] s.t. [tex]$y=\sum_{i=1}^{n} \lambda_i\ x_i $[/tex].

Finally, the following compactness theorem holds:

Let [tex]$(X,||\cdot ||)$[/tex] be a normed vector space of finite dimension and [tex]$K\subseteq X$[/tex].

If [tex]$K$[/tex] is compact, then [tex]$\text{conv} K$[/tex] is compact.

***

Problem:

The previous compactness theorem fails in infinite dimensional vector spaces.
Find a counterexample.

In order to answer to the Problem, it could be useful to solve the following:

Exercise:

Consider the normed vector space [tex]$\ell^2:=\{ x=(x_n):\ \sum_{n=1}^{+\infty} |x_n|^2 <+\infty\}$[/tex] equipped with the standard norm, i.e. [tex]$x=(x_n) \mapsto ||x||_2:=\left\{ \sum_{n=1}^{+\infty} |x_n|^2\right\}^{1/2}$[/tex]; this space is the prototype of all separable Hilbert spaces, hence [tex]$\ell^2$[/tex] is complete w.r.t. the norm [tex]$||\cdot ||_2$[/tex].
Let for all [tex]$m\in \mathbb{N}$[/tex]:

[tex]$e^m:=(\delta_n^m),\quad \text{with } \delta_n^m:=\begin{cases} 1&\text{, if } n=m \\ 0&\text{, otherwise} \end{cases}$[/tex];

and [tex]$o$[/tex] be the null sequence, i.e. [tex]$o:=(0,0,l\dots ,0,\ldots )$[/tex].

1. Prove that, for each sequence [tex]$a=(a_n) \in c_0$[/tex]*, the set:

[tex]$K(a):=\{ o\} \cup \{ a_m\ e^m\}_{m\in \mathbb{N}} =\{o, a_1\ e^1,\ a_2\ e^2,\ldots ,a_m\ e^m,\ldots \}$[/tex]

is compact in [tex]$\ell^2$[/tex] and that [tex]$\text{conv} K(a) \subseteq c_{00}$[/tex]**.

2. For all [tex]$m\in \mathbb{N}$[/tex] put:

[tex]$x^m:=\sum_{n=1}^{m} \frac{2^{-n}}{\sum_{j=1}^{m} 2^{-j}}\ a_n\ e^n$[/tex]
[tex]$=\left( \frac{2^{-1}}{\sum_{j=1}^{m} 2^{-j}}\ a_1, \frac{2^{-2}}{\sum_{j=1}^{m} 2^{-j}}\ a_2,\ldots ,\frac{2^{-m}}{\sum_{j=1}^{m} 2^{-j}}\ a_m, 0,\ldots ,0,\ldots \right)$[/tex]

and show that [tex]$x^m \in \text{conv} K(a)$[/tex].

3. Show that [tex]$(x^m)$[/tex] converges in [tex]$\ell^2$[/tex] and evaluate its limit.

4. Prove that [tex]$x:=\lim_m x^m \notin c_{00}$[/tex], hence [tex]$x\notin \text{conv} K(a)$[/tex].

5. Is [tex]$\text{conv} K(a)$[/tex] compact in [tex]$\ell^2$[/tex]?

Hints: 1. The inclusion [tex]$\text{conv} K(a) \subseteq c_{00}$[/tex] is almost trivial; the fact that [tex]$K(a)$[/tex] is compact (or sequentially compact, which ammount to the same thing) follows from the fact that [tex]$\lim_m a_m\ e^m =o$[/tex] in [tex]$\ell^2$[/tex].
2. Direct computation.
3 & 4. Remember that a sequence [tex]$(x^m) \subseteq \ell^2$[/tex] with [tex]$x^m:=(x_n^m)$[/tex] converges in [tex]$\ell^2$[/tex] iff the limits [tex]$x_n=\lim_m x_n^m$[/tex] exist, are all finite and the sequence [tex]$x=(x_n)$[/tex] is [tex]$\ell^2$[/tex]; in this case one has also [tex]$x=lim_m x^m$[/tex] in [tex]$\ell^2$[/tex].
5. Remember that a compact subset of a normed space is closed.

__________
* Here [tex]$c_0:=\{ a=(a_n):\ a_n\to 0\}$[/tex].
** Remember that [tex]$c_{00}:=\{ b=(b_n):\ \exists \nu \in \mathbb{N} \text{ s.t. } \forall n\geq \nu ,\ b_n=0 \}$[/tex].

[gugo82]

"dissonance":[quote="gugo82"]Carathéodory's theorem is almost trivial...

Trivial, you say?
Convexity is your cup of tea, isn't it? Surely it's not mine: I could use some help in understanding the proof of this theorem! [/quote]
Convexity isn't exactly my "daily bread" (:-D)... But while I was writing my last post, I remembered a proof of the Carathéodory's theorem I read some time ago (perhaps when I was writing my degree thesis) and, well, it is just linear algebra...

Proof (of Carathéodory's theorem): Let:

[tex]$ C_Y := \{ x\in X:\ x \text{ can be written as a convex combination of } N+1\text{ or fewer points in } Y\}$[/tex].

Clearly [tex]$C_Y$[/tex] is contained in each convex set [tex]$C$[/tex] containing [tex]$Y$[/tex]; hence [tex]$C_Y\subseteq \bigcap_{C\in \mathcal{C} ,\ Y\subseteq C} C =:\text{conv} Y$[/tex].

The "harder" part is to show that [tex]$\text{conv} Y\subseteq C$[/tex], i.e. that each [tex]$x$[/tex] in the convex hull of [tex]$Y$[/tex] can actually be written as a convex combination of [tex]$N+1$[/tex] or fewer point in [tex]$Y$[/tex]: so let's do it!

Choose [tex]$x\in \text{conv} Y$[/tex] and let's say [tex]$x_1,\ldots ,x_M$[/tex] points in [tex]$Y$[/tex] s.t. [tex]$x=\sum_{n=1}^M \lambda_n\ x_n$[/tex] with [tex]$\lambda_n\geq 0$[/tex] and [tex]$\sum_{n=1}^M \lambda_n =1$[/tex].
If [tex]$M\leq N+1$[/tex], then [tex]$x\in C_Y$[/tex] and there's nothing to prove; so we suppose [tex]$M>N+1$[/tex].
In order to obtain [tex]$x\in C_Y$[/tex], we're going to prove that there exists a procedure which allows us to write [tex]$x$[/tex] as convex combination of [tex]$M-1$[/tex] points in [tex]$\{ x_1,\ldots ,x_M\}$[/tex]; then we'll iterate this procedure (in a sort of "descent method") to reach our goal.

Since [tex]$M>N+1$[/tex], the points [tex]$x_1,\ldots ,x_M$[/tex] are affinely dependent, i.e. the [tex]$M-1$[/tex] vectors [tex]$x_2-x_1,\ldots ,x_M-x_1$[/tex] are linearly dependent*, hence there exists [tex]$M-1$[/tex] scalars [tex]$\alpha_2,\ldots ,\alpha_M$[/tex] not all zero s.t.:

[tex]$\sum_{n=2}^M \alpha_n\ (x_n-x_1)=\mathfrak{o}$[/tex]

(here and in what follows [tex]$\mathfrak{o}$[/tex] is the null vector of [tex]$X$[/tex]); if we put [tex]$\alpha_1:=-\sum_{n=2}^M \alpha_n$[/tex], the previous relation reads:

(*) [tex]$\sum_{n=1}^M \alpha_n\ x_n =\mathfrak{o}$[/tex]

and obviously we have also:

(**) [tex]$\sum_{n=1}^M \alpha_n=0$[/tex].

W.l.o.g. we can assume that at least one [tex]$\alpha_n$[/tex] is [tex]$>0$[/tex] (if it were not the case, we can change the signs in (*) and (**) without altering them), so that we can put:

[tex]$\mu :=\min \left\{ \frac{\lambda_n}{\alpha_n} ,\ \text{with } n\text{ s.t. } \alpha_n>0 \right\} \geq 0$[/tex];

again w.l.o.g. we can assume that [tex]$\mu =\frac{\lambda_M}{\alpha_M}$[/tex] (if it were not the case, we just relabel properly the [tex]$x_n$[/tex]s); now we have:

[tex]$x=\sum_{n=1}^M\lambda_n\ x_n -\mathfrak{o}$[/tex]
[tex]$=\sum_{n=1}^M\lambda_n\ x_n - \mu \ \sum_{n=1}^M\alpha_n\ x_n$[/tex] (we're using (*))
[tex]$=\sum_{n=1}^M(\lambda_n-\mu \ \alpha_n)\ x_n$[/tex]
[tex]$=\sum_{n=1}^{M-1}(\lambda_n -\mu \ \alpha_n)\ x_n$[/tex] (we've suppressed the last summand because [tex]$\lambda_M-\mu \ \alpha_M=0$[/tex]),

therefore [tex]$x$[/tex] is a linear combination of the [tex]$M-1$[/tex] points [tex]$x_1,\ldots ,x_{M-1}$[/tex].
We have:

[tex]$\lambda_n- \mu \ \alpha_n\geq 0$[/tex]

for the very definition of [tex]$\mu$[/tex] (in case [tex]$\alpha_n > 0$[/tex]) or because [tex]$\lambda_n,\ -\mu \alpha_n \geq 0$[/tex] (if [tex]$\alpha_n \leq 0$[/tex]), and also:

[tex]$\sum_{n=1}^{M-1} \lambda_n- \mu \ \alpha_n = \sum_{n=1}^M \lambda_n- \mu \ \alpha_n =1-\mu \ \sum_{n=1}^M \alpha_n =1-\mu \ 0=1$[/tex],

hence [tex]$x$[/tex] is actually a convex combination of the [tex]$M-1$[/tex] points [tex]$x_1,\ldots ,x_{M-1}$[/tex].

As we noted before, we can apply our procedure to reduce in each iteration the number of points used to express [tex]$x$[/tex] as a convex combination of points in [tex]$Y$[/tex]; hence, after (at most) [tex]$M-(N+1)$[/tex] iterations, we succeed in writing [tex]$x$[/tex] as a convex combination of [tex]$N+1$[/tex] (or possibly fewer) points in [tex]$Y$[/tex].
Therefore [tex]$x\in C_Y$[/tex] and finally [tex]$\text{conv} Y \subseteq C_Y$[/tex], which was our claim. [tex]$\square$[/tex]

__________
* Formally, we would have to distinguish the vector space [tex]$X$[/tex] and the affine space [tex]$\mathcal{X}$[/tex] modelled on [tex]$X$[/tex]... But we're not geometrician after all.

[dissonance]

"gugo82":Carathéodory's theorem is almost trivial...

Trivial, you say?
Convexity is your cup of tea, isn't it? Surely it's not mine: I could use some help in understanding the proof of this theorem! [size=75](but I don't want you to waste time if you're busy. Don't answer unless you really have time to spare! After all this is just a curiosity to me, I don't need those tools at the moment.)[/size]

[gugo82]

As far as I know, the compactness theorem for convex hull is a consequence of both a theorem of Carathéodory (which is a result of combinatorial type, see below) and the topological Weierstrass theorem (i.e. the image of a compact space under a continuous function is a compact space).

Carathéodory's theorem reads as follows:

Let [tex]$(X, ||\cdot ||)$[/tex] be a normed vector space of finite dimension [tex]$N$[/tex], [tex]$Y\subseteq X$[/tex] non empty and [tex]$x\in X$[/tex].

Then [tex]$x\in \text{conv} Y$[/tex] iff [tex]$x$[/tex] can be written as a convex combination of [tex]$N+1$[/tex] or fewer points of [tex]$Y$[/tex].

A proof of the compactness theorem is the following:


Proof: If the compact [tex]$K$[/tex] is empty, then [tex]$\text{conv} K=\emptyset$[/tex] hence [tex]$\text{conv} K$[/tex] is compact.

Otherwise, let [tex]$K\neq \emptyset$[/tex] be compact and let [tex]$\Delta^N$[/tex] be the standard [tex]$N$[/tex]-simpex in [tex]$\mathbb{R}^{N+1}$[/tex], i.e.:

[tex]$\Delta^N :=\{ \lambda=(\lambda_1,\ldots ,\lambda_{N+1})\in \mathbb{R}^{N+1} :\ \lambda_n\geq 0 \text{ e } \sum_{n=1}^{N+1} \lambda_n=1\}$[/tex].

Define the function [tex]$\Phi : \mathbb{R}^{N+1}\times X^{N+1} \mapsto X$[/tex] by:

[tex]$\Phi (\lambda , x_1,\ldots ,x_{N+1}) := \sum_{n=1}^{N+1} \lambda_n\ x_n$[/tex];

[tex]$\Phi$[/tex] is continuous in [tex]$\mathbb{R}^{N+1}\times X^{N+1}$[/tex] (that's a trivial exercise), hence its restriction [tex]$\varphi :=\Phi \Big|_{\Delta^N \times K^{N+1}}$[/tex] is continuous as well.

By Carathéodory's theorem, we have [tex]$\varphi (\Delta^N\times K^{N+1}) =\text{conv} K$[/tex]; but [tex]$\Delta^N \times K^{N+1}$[/tex] is compact (for it is a product of compact sets), therefore [tex]$\text{conv} K$[/tex] is compact by the topological Weierstrass theorem. [tex]$\square$[/tex]

Carathéodory's theorem is almost trivial and can be found in the most textbooks on convexity; for example, Rockafellar, Convex Analysis, or Webster, Convexity.
Neverthless, if you want a proof, I can write it down here; it's rather short...

[dissonance]

Thank you!

I'd like to ask one more question. How difficult it is to prove

Let [tex]$(X,||\cdot ||)$[/tex] be a normed vector space of finite dimension and [tex]$K\subseteq X$[/tex].

If [tex]$K$[/tex] is compact, then [tex]$\text{conv} K$[/tex] is compact.

I must admit I have no clue. Could it be a consequence of the Heine-Borel property of $X$?

[gugo82]

OK!

Good solution and good English as well.

[dissonance]

Very nice indeed! I'll try my hand at the proofs.

Let [tex]a, K(a)[/tex] as in the preceding post. We rule out the case [tex]a \in c_{00}[/tex], that is we make sure [tex]a_n[/tex] is not eventually zero. This would make [tex]K(a)[/tex] into a finite set, trivializing everything.

First of all we prove that [tex]K(a)[/tex] is compact: choose a sequence [tex](k^m)[/tex] in [tex]K(a)[/tex]. If [tex](k^m)[/tex] contains only a finite number of terms then it contains a constant, hence convergent, subsequence; if not, we can find a strictly increasing sequence [tex](n_h)[/tex] of naturals s.t. [tex]a_{n_h}e^{n_h}[/tex] is a subsequence of [tex](k^m)[/tex] which we call [tex]k^h[/tex] with abuse of notations. Since [tex]\lVert k^h \rVert_2= \lvert a_{n_h} \rvert^2[/tex], this subsequence of [tex](k^m)[/tex] converges to [tex]o[/tex] which is an element of [tex]K(a)[/tex]. Hence the latter is compact.

Next we show that [tex]\mathrm{conv}K(a) \subset c_{00}[/tex]: let [tex]k_1=a_{m_1}e^{m_1},\ k_2=a_{m_2}e^{m_2}[/tex] and [tex]\lambda \in[0, 1][/tex]; clearly every term of [tex](1-\lambda)k_1+\lambda k_2[/tex] of index greater than [tex]\mathrm{max}(m_1, m_2)[/tex] is zero and so [tex](1-\lambda)k_1+\lambda k_2 \in c_{00}[/tex].

Now we call [tex]$x^m=\sum_{n=1}^{m} \frac{2^{-n}}{\sum_{j=1}^{m} 2^{-j}}\ a_n\ e^n$[/tex].
Being a linear combination of [tex]a_1e^1, \ldots, a_me^m \in K(a)[/tex] whose coefficients add up to [tex]1[/tex], [tex]x^m \in \mathrm{conv}K(a)[/tex]. Call [tex]\tilde{a}=(2^{-1}a_1, 2^{-2}a_2, \ldots )=(2^{-n} a_n e^n )[/tex]. This sequence belongs to [tex]\ell^2[/tex] because of [tex]\tilde{a}_n \le \frac{a_n}{2^n}[/tex] and the fact that [tex]a_n[/tex] is bounded.
We claim that [tex]\lVert x^m-\tilde{a} \rVert_2 \to 0[/tex].
To prove this, let [tex]$\alpha_m=(\frac{1}{\sum_{j=1}^m2^{-j}}-1)$[/tex]. Then

[tex]\lVert x^m - \tilde{a} \rVert_2^2= \alpha_m^2 \Bigl [(2^{-1}a_1)^2+ \ldots + (2^{-m}a_m)^2 \Bigr ]+\Bigl [ (2^{-(m+1)}a_{m+1})^2 + (2^{-(m+2)}a_{m+2})^2 +... \Bigr ]=\alpha_m^2S_m + R_m[/tex]

Note that [tex]\alpha_m \to 0[/tex] (obviously); [tex]S_m[/tex] is bounded by [tex]\lVert \tilde a \rVert_2^2[/tex]; and [tex]R_m\to 0[/tex] being a remainder of the convergent series [tex]$\sum_{n=0}^\infty \tilde{a}_n^2[/tex]. We conclude that [tex]\lVert x^m - \tilde{a} \rVert_2^2 \to 0[/tex].

Last, we point out that [tex]\tilde{a} \notin c_{00}[/tex] (that's why we ruled out [tex]a\in c_{00}[/tex]). This implies that [tex]\mathrm{conv}K(a)[/tex] is not closed in [tex]\ell^2[/tex] hence not compact, since [tex]\ell^2[/tex] is Hausdorff.