Prove Convex Hull of Minkowski sum

I want to prove that the following holds, where the $+$ means Minkowski sum:

$$conv(A+B)=conv(A)+conv(B)$$

Let the convex hull of $A+B$ be $$conv(A+B)=\sum_{j,k}\lambda_j\mu_k(a_j+b_k)$$

I don't know how to continue from here.

• Can you prove at least one direction? – Stefan Hamcke Nov 30 '13 at 19:25

A set $C$ is convex iff for all $t\in (0,1)$ we have $tC+(1-t)C= C$.

It follows that the Minkowski sum of convex sets $A, B$ is convex: $$t(A+B)+(1-t)(A+B) = (tA+(1-t)A) + (tB+(1-t)B) = A+B$$

Therefore, for general sets $A,B$ the sum $\operatorname{conv}(A)+\operatorname{conv}(B)$ is convex; and since it contains $A+B$, it also contains the convex hull of $A+B$. One inclusion proved.

For the opposite inclusion, pick a point in the convex hull of $A+B$. It is a convex combination of some points of $A+B$, i.e., $\sum \lambda_k (a_k+b_k)$. Since $$\sum \lambda_k (a_k+b_k)= \sum \lambda_k a_k + \sum \lambda_k b_k \in \operatorname{conv}(A)+\operatorname{conv}(B)$$

• $\newcommand{co}{\operatorname{conv}}$ As I see it, you prove two times that the $\co(A+B) \subset \co A + \co B$. First you say $\co A + \co B$ is convex and contains $A+B$ so $\co (A +B) \subset \co A + \co B$. Then you pick a gain a point $\sum \lambda_k (a_k+b_k)$ in $\co (A+B)$. – user42761 Mar 28 '14 at 19:32

$\newcommand{\co}{\operatorname{co}}$ As already noted we have $\co (A+B) \subset \co A +\co B$. Now let $v+w \in \co A + \co B$. Write $v = \sum_i \alpha_i a_i$ and $w = \sum_j \beta_j b_j$. First we have $$v + b_j = \sum_i \alpha_i (a_i + b_j)$$ so $v + b_j \in \co ( A +B)$. Now we have $$v+w = \sum_j \beta_j ( v+ b_j).$$ So $v+w \in \co( \co (A+B)) = \co (A+B)$ and we are done.

• Very nice. You should have gotten the uptick! – Evan Aad Dec 6 '18 at 13:41