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.

  • $\begingroup$ Can you prove at least one direction? $\endgroup$ – 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)$$

  • 8
    $\begingroup$ $\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)$. $\endgroup$ – 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.

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

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.