What is the convex hull of $\text{conv}(u_1,u_2,\cdots,u_p)+\text{conv}(v_1,v_2,\cdots,v_s)$?

Question

Let $u_i, i= 1,\cdots,p$ and $v_j, j= 1,\cdots,s$ be finitely many vectors in $\mathbb{R}^n$. Show that

$$ \text{conv}(u_1,u_2,\cdots,u_p)+\text{conv}(v_1,v_2,\cdots,v_s)=\text{conv}\{u_i+v_j \mid i= 1,\cdots,p, \,\, j= 1,\cdots,s\} $$

We need to show

$$ x+y \in \text{conv}\{u_i+v_j \mid i= 1,\cdots,p, \,\, j= 1,\cdots,s\} $$

where $x \in \text{conv}(u_1,u_2,\cdots,u_p)$ and $y \in \text{conv}(v_1,v_2,\cdots,v_s)$. Also, we need to show

$$ z \in \text{conv}(u_1,u_2,\cdots,u_p)+\text{conv}(v_1,v_2,\cdots,v_s) $$

where $z \in \text{conv}\{u_i+v_j \mid i= 1,\cdots,p, \,\, j= 1,\cdots,s\}$.

I have tried the following for the first one:

Let $x \in \text{conv}(u_1,u_2,\cdots,u_p)$ so $x=\sum_{i=1}^p\lambda_iu_i$ where $\sum_{i=1}^p\lambda_i=1$. Also, Let $y \in \text{conv}(v_1,v_2,\cdots,v_s)$ so $x=\sum_{j=1}^s\mu_jv_j$ where $\sum_{j=1}^s\mu_j=1$.

Summing them

$$x+y=\lambda_1u_1+\lambda_2u_2+\cdots+\lambda_pu_p+\mu_1v_1+\mu_2v_2+\cdots+\mu_sv_s.$$

Now the question is how we can get something in the form of $\text{conv}\{u_i+v_j \mid i= 1,\cdots,p, \,\, j= 1,\cdots,s\}$?

Answer 1

We can use the match-up procedure as follows. Set $$\lambda_i^0:=\lambda_i\text{ for each }i=1,2,\ldots,p\,,$$ $$\mu_j^0:=\mu_j\text{ for each }j=1,2,\ldots,s\,,$$ and $$z_0:=x+y\,.$$ Suppose that we have $$z_k=\sum_{i=1}^p\,\lambda_i^k\,u_i+\sum_{j=1}^s\,\mu_j^k\,v_j$$ for some nonnegative integer $k$ and for some $\lambda_i^k,\mu_j^k\in[0,1]$ such that $$s_k:=\sum_{i=1}^p\,\lambda_i^k=\sum_{j=1}^s\,\mu_j^k\,.$$

If $s_k=0$, then the process terminates at this point. If $s_k>0$, then we take $i_k:=\min\{i\,|\,\lambda^k_i\neq 0\}$ and $j_k:=\min\{j\,|\,\mu^k_j\neq 0\}$. Now define $w_k:=u_{i_k}+v_{j_k}$. Let $\nu_k:=\min\{\lambda_{i_k},\mu_{j_k}\}$. Then, set $$\lambda_i^{k+1}:=\left\{\begin{array}{ll}\lambda_i^k&\text{if }i\neq i_k\,,\\ \lambda_i^k-\nu_k&\text{if }i=i_k\,,\end{array}\right\}\text{ for every }i=1,2,\ldots,p\,,$$ $$\mu_j^{k+1}:=\left\{\begin{array}{ll}\mu_j^k&\text{if }j\neq j_k\,,\\ \mu_j^k-\nu_k&\text{if }j=j_k\,,\end{array}\right\}\text{ for every } j=1,2,\ldots,s\,,$$ and $$z_{k+1}:=z_k-\nu_k\,w_k\,.$$

Note that this algorithm cannot prolong indefinitely, since the number of nonzero coefficients amongst $\lambda_1,\lambda_2,\ldots,\lambda_p,\mu_1,\mu_2,\ldots,\mu_s$ decreases each step. When the loop is over (say, in $l+1$ steps, namely, with $s_1,s_2,\ldots,s_l>0$ and $s_{l+1}=0$), we can see that $$x+y=\sum_{k=1}^l \,\nu_k\,w_k\,,$$ where $\nu_k\in[0,1]$ for each $k=1,2,\ldots,l$ with $\sum\limits_{k=1}^l\,\nu_k=1$, and each $w_k$ is of the form $u_i+v_j$ for some $i=1,2,\ldots,p$ and $j=1,2,\ldots,s$. (It is obvious that $l\leq p+s$, by the way.) This proves that $$\begin{align}\text{conv}\left\{u_1,u_2,\ldots,u_p\right\}&+\text{conv}\left\{v_1,v_2,\ldots,v_s\right\}\\&\subseteq \text{conv}\big\{u_i+v_j\,\big|\,i=1,2,\ldots,p\ \text{and}\ j=1,2,\ldots,s\big\}\,.\end{align}$$

---

To prove the reversed inclusion, it is actually easier. Let $$a\in \text{conv}\big\{u_i+v_j\,\big|\,i=1,2,\ldots,p\text{ and }j=1,2,\ldots,s\big\}\,.$$ Then, there exist $\alpha_{i,j}\in[0,1]$ for $i=1,2,\ldots,p$ and $j=1,2,\ldots,s$ such that $$\sum_{i=1}^p\,\sum_{j=1}^s\,\alpha_{i,j}=1\text{ and }a=\sum_{i=1}^p\,\sum_{j=1}^s\,\alpha_{i,j}\,\left(u_i+v_j\right)\,.$$

By taking $\beta_i:=\sum\limits_{j=1}^s\,\alpha_{i,j}$ for each $i=1,2,\ldots,p$ and $\gamma_j:=\sum\limits_{i=1}^p\,\alpha_{i,j}$ for every $j=1,2,\ldots,s$, we see that $\beta_i\in[0,1]$ for each $i=1,2,\ldots,p$, $\gamma_j\in[0,1]$ for every $j=1,2,\ldots,s$, $\sum\limits_{i=1}^p\,\beta_i=1$, and $\sum\limits_{j=1}^s\,\gamma_j=1$. Thus, $a=b+c$, where $$b:=\sum_{i=1}^p\,\beta_i\,u_i\in \text{conv}\left\{u_1,u_2,\ldots,u_p\right\}$$ and $$c:=\sum_{j=1}^s\,\gamma_j\,v_j\in\text{conv}\left\{v_1,v_2,\ldots,v_s\right\}\,.$$ Hence, $$\begin{align}\text{conv}\big\{u_i+v_j\,\big|\,i=1,2,\ldots,p\ &\text{and}\ j=1,2,\ldots,s\big\}\\&\subseteq \text{conv}\left\{u_1,u_2,\ldots,u_p\right\}+\text{conv}\left\{v_1,v_2,\ldots,v_s\right\}\,,\end{align}$$ as desired.

Answer 2

Here is an less verbose and more general way. Suppose you have two sets $S_1,S_2$ and we let $C_1= \operatorname{co} S_1$, $C_2= \operatorname{co} S_2$.

Then we have $S_1+S_2 \subset C_1+C_2$ and so $\operatorname{co} (S_1+S_2) \subset C_1+C_2$.

We have $S_1+S_2 \subset\operatorname{co} (S_1+S_2) $. Suppose $c \in C_1$, then $c= \sum_k \lambda(k) s_1(k)$ where the $s_1(k) \in S_1$ and the $\lambda(k)$ are convex multipliers. Since $\operatorname{co} (S_1+S_2)$ is convex, it follows that $c+s_2 = \sum_k \lambda(k) (s_1(k) +s_2) \in \operatorname{co} (S_1+S_2)$ for any $s_2 \in S_2$, and so $C_1 +S_2 \subset \operatorname{co} (S_1+S_2)$. A similar argument shows that $C_1+C_2 \subset \operatorname{co} (S_1+S_2)$.

Answer 3

For two sets $$\operatorname{co}(S_1 \times S_2) = \operatorname{co}(S_1) \times \operatorname{co}(S_2)$$

the inclusion from left to right is clear, for the other way notice the equality $$(\sum \lambda_i u_i, \sum \mu_j v_j) = \sum \lambda_i \mu_j (u_i , v_j)$$ if $\lambda_i$, $\mu_j$ positive with sum $1$. Now apply the affine map $+\colon V\times V \to V$.