3
$\begingroup$

Let $S\subset R^n$. Prove that the convex hull of $S$ is a convex set.

By definition of convex hull we know

$$S=\{x=\lambda_1x_1+\cdots+\lambda_mx_m\mid \lambda_1,\ldots,\lambda_m\geq0,\lambda_1+\cdots+\lambda_m=1, \text{ and } x_1,\ldots,x_m\in S \} $$

Using Proof by Induction $m=1$ is trivial and $m=2$ is the definition of a convex set. To prove $m+1$ is true I force factored a $\lambda$ to result in...

Let $\lambda = \lambda_1+\cdots+\lambda_m = 1-\lambda_{m+1}$ then

$$\lambda \left(\frac{\lambda_1}{\lambda}x_1+\cdots+\frac{\lambda_m}{\lambda}x_m \right) + (1-\lambda)x_{m+1}.$$

This is a convex combination. I believe this would finish proving that the convex hull of $S$ is a convex set.

Can this be proved without using Proof by Induction?

$\endgroup$
3
  • $\begingroup$ You only have proved that $\sum_i \lambda_i x_i\in S$ if $S$ is convex. You should take $u,v$ from the convex hull of $S$ and look what happens to $(1-\lambda) u + \lambda v$ $\endgroup$
    – user251257
    Apr 18, 2017 at 17:55
  • $\begingroup$ I am not sure what it means to take $u$ from the convex hull of $S$? would that imply setting $u=\lambda_1u_1+...+\lambda_mu_m$ ?@user251257 $\endgroup$
    – av056
    Apr 18, 2017 at 18:15
  • $\begingroup$ yes, and the same to $v$. Notice that both sums may have different number of summands (which is not that important) $\endgroup$
    – user251257
    Apr 18, 2017 at 18:24

2 Answers 2

2
$\begingroup$

If $s_1, s_2 \in \operatorname{co} S$, then there are (a finite number of) $\lambda_k(1), \lambda_k(2)$ and $x_k \in S$ such that $s_i = \sum_k \lambda_k(i) x_k$ with $\lambda_k(i) \ge 0$ and $\sum_k \lambda_k(i) = 1$.

Now choose $t \in [0,1]$ and pick $s = ts_1 + (1-t) s_2$, then $s = \sum_k (t \lambda_k(1)+ (1-t) \lambda_k(2)) x_k$ and we can see that $t \lambda_k(1)+ (1-t) \lambda_k(2) \ge 0$ and we can quickly check that $\sum_k (t \lambda_k(1)+ (1-t) \lambda_k(2)) = 1$. Hence $s \in \operatorname{co} S$.

$\endgroup$
0
$\begingroup$

Here is proof without induction.

Let $T$ be the convex hull of some arbitrary set $S \subset R^n$.

Let $x, y \in T$. Then by definition (of convex hull)

$$ x = \sum_{i=1}^k \alpha_i x_i, \, x_i \in S, \, \alpha_i \geq 0, \sum_i \alpha_i = 1 $$ and $$ y = \sum_{j=1}^l \beta_j y_j, \, y_j \in S, \, \beta_j \geq 0, \sum_j \beta_j = 1 $$

Without loss of generality, let us assume that $k \geq l$ and let us extend $y$ expression to $$ y = \sum_{j=1}^l \beta_j y_j + \sum_{j=l+1}^k \beta_j y_j $$ where $\beta_j = 0$ for $l < j \leq k$ and $y_j$ are arbitrarily chosen from $S$ for $l < j \leq k$. (if $k=l$, then no additional terms will be added to the expression of $y$).

We did this to ensure that both convex combinations have the same number of terms ($k$).

Now, choose $\theta \in [0,1]$ and consider the point $z = \theta x + (1-\theta) y$.

We have $$ z = \sum_{i=1}^k \theta \alpha_i x_i + \sum_{j=1}^k (1 - \theta) \beta_j y_j $$

This indeed is a convex combination of $2k$ points in $S$ with $x_i \in S$ and $y_j \in S$ since $$ \sum_{i=1}^k \theta \alpha_i + \sum_{j=1}^k (1 - \theta) \beta_j = \theta \sum_{i=1}^k \alpha_i + (1 - \theta) \sum_{j=1}^k \beta_j = \theta + (1 - \theta) = 1. $$

Thus, $z$ being a convex combination of points in $S$ belongs to $T$.

We have shown that for $x, y \in T$, $z$ belongs to $T$. Hence $T$ is convex.

$\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.