Definition: $C_1 + C_2 = \{x + y \,\, | \,\,x \in C_1, y \in C_2\}$.
Proposition: Let $C_1$ and $C_2$ be convex sets, then $C_1 + C_2$ is convex.
Proof (sketch): Choose $a = a_1 + a_2$ and $b = b_1 + b_2$ such that $a_1, b_1 \in C_1$ and $a_2, b_2 \in C_2$. Then $a, b \in C$. Suppose there exists $\lambda \in [0,1]$ such that $\lambda a + (1 – \lambda) b \notin C$. Then:
$$\lambda(a_1 + a_2) + (1 – \lambda) (b_1 + b_2) \notin C $$
$$( \lambda a_1 + (1 – \lambda) b_1) + (\lambda a_2 + (1-\lambda) b_2) \notin C $$
Define $A = ( \lambda a_1 + (1 – \lambda) b_1)$ and $B = ( \lambda a_2 + (1 – \lambda) b_2)$, $A \in C_1$ and $B \in C_2$. Therefore $A + B \notin C$, which is an absurd since by definition $A+B$ must belong to $C$.
Is this enough or am I missing something?
Best Answer
Here is another approach, albeit just replacing one problem by another:
Show that $C_1 \times C_2$ is convex first and then show that if $L$ is linear and $C$ convex, then $L(C)$ is convex. Then apply $L(x) = x_1+x_2$ to $C_1 \times C_2$.