3
$\begingroup$

I am having trouble understanding the proof for:

4.3.1 Lemma. Convex hull $C$ of a set $X \subseteq \Re $ equals the set: $$D= \left\{ \sum_{i=1}^{m}{t_i x_i} : m \geq 1, x_1...x_m \in X, t_1,...,t_m \geq 0, \sum_{t=1}^{m}{t_i} = 1 \right\}$$ of all convex combinations of finitely many points of X.

For the direction $C\subseteq D$, the authors say:

For the reverse inclusion it suffices to prove that $D$ is convex, that is, to verify that whenever $x,y \in D$ are two convex combinations and $t\in (0,1)$, then $tx + (1-t)y$ is again a convex combination.

Why does it suffice to prove that $D$ is convex? Shouldn't we prove that any point in $C$ is in $D$?

P.S. And what would it mean for a point to be in $C$ - which is convex hull? I find that confusing...

$\endgroup$
4
  • 2
    $\begingroup$ Take $m=1$, $t_1 = 1$ and $x_1 = x$ to see that $x \in D$ for all $x \in X$. Together with the stated fact that $D$ is convex we have $D \supset X$ and since $C$ is (probably) by definition the intersection of all convex sets containing $X$, we must have $C \subset D$. $\endgroup$
    – t.b.
    Commented Nov 12, 2011 at 9:35
  • $\begingroup$ Why do you need to have $X\subset D$? $\endgroup$ Commented Nov 12, 2011 at 9:39
  • 5
    $\begingroup$ Again: $C$ is by definition the intersection of all convex sets containing $X$: $$C = \bigcap_{\substack {C' \text{ convex} \\ C' \supset X}} C'$$ If you know that $D$ contains $X$ (obvious, as I said above) and is convex (this requires an argument) then you know that $C \subset D$, as $D$ will then appear in the intersection. $\endgroup$
    – t.b.
    Commented Nov 12, 2011 at 9:41
  • $\begingroup$ My typo Didier - I fixed that. $\endgroup$ Commented Nov 12, 2011 at 10:17

1 Answer 1

3
$\begingroup$

On drozzy's request I'm posting my comment as an answer:

By definition the convex hull $C$ of $X$ is the intersection of all convex sets $C'$ containing $X$: $$C = \bigcap_{\substack{C' \text{ convex} \\ C' \supset X}} C'.$$ If you know that $D$ is convex (that's what the authors show later on and needs some argument) and contains $X$ (that's obvious by taking $m = 1$, $t_1 = 1$ and $x_1 = x$ for each $x \in X$) then you know that $D$ will appear as some $C'$ in the intersection on the right hand side, so that $C \subset D$.

For the sake of completeness, the reasoning for the other inclusion $D \subset C$ is this: since all $C'$ appearing in the intersection are convex and contain $X$, they must contain all convex combinations of points of $X$. But $D$ is by its very description the set of all convex combinations of points of $X$, so $D$ is contained in all $C'$ appearing in the intersection and thus $D \subset C$.

$\endgroup$
2
  • $\begingroup$ Interesting, but the authors show the other direction $D\in C$ by induction. $\endgroup$ Commented Nov 12, 2011 at 16:55
  • $\begingroup$ I haven't looked at the book you mentioned, I assume that they show by induction the following: if $x_{1},\ldots,x_m \in C'$ and $t_1 + \cdots + t_m = 1$ with $t_i \geq 0$ then $\sum t_i x_i \in C'$. For $m = 2$ this is the definition of convexity and for greater $m$ you indeed need to prove this by induction. $\endgroup$
    – t.b.
    Commented Nov 12, 2011 at 17:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .