# The Minkowski sum of two convex sets is convex

Let $A$ and $B$ be two convex subsets in $\mathbb{R}^n$. Define a set $C$ given by $$C = A + B = \{a + b : a \in A \mbox{ and } b \in B\}.$$ Is $C$ a convex set?

• Convexity conserves under Minkowski sum.
– BAI
Commented Aug 30, 2017 at 9:22
• See this if you like.
– BAI
Commented Aug 30, 2017 at 9:33
• What have you done by yourself ? Commented Aug 30, 2017 at 9:37

For $e,f\in C$, let $a,b\in A$ and $c,d\in B$ s.t. $e=a+c$ and $f=b+d$,

$$te+(1-t)f=t(a+c)+(1-t)(b+d) = (ta+(1-t)b) + (tc+(1-t)d)\in A+B=C$$ For all $t\in [0,1]$. $\square$

If $c_1=a_1+b_1$ and $c_2=a_2+b_2$ belong to $C$ (with $a_1,a_2\in A$ and $b_1,b_2\in B$), then for $\alpha\in [0,1]$: $$\alpha c_1+(1-\alpha) c_2=\left(\alpha a_1+(1-\alpha) a_2\right)+ \left(\alpha b_1+(1-\alpha) b_2\right)$$ What may we conclude?

A set is convex when a convex combination of two points also belong to the set.

Then take any two points of the Minkowsi sum, which are each the sum of two points of $A$ and $B$ and form their convex sum. By linearity, they can be expressed as the sum of two convex combinations of elements of $A$ and $B$.

$$(1-t)(p_A+p_B)+t(q_A+q_B)=((1-t)p_A+tq_A)+((1-t)p_B+tq_B).$$

Then by convexity of these sets, the linear combinations are themselves in $A$ and $B$ and their sum in the Minkowski sum.