While studying convex analysis/optimization i encountered the following problem:
Problem:
Let $S_{1}$ and $S_{2}$ be convex sets in $R^{n}$. Then: $$
S_{1} + S_{2}=\left\{\mathbf{x}_{1}+\mathbf{x}_{2}: \mathbf{x}_{1} \in S_{1}, \mathbf{x}_{2} \in S_{2}\right\} \text { is convex. }
$$
Relevant Definitions:
A set $S$ in $R^{n}$ is convex if given $x_{1}$ and $x_{2}$ in S, then $\lambda x_{1}+(1-\lambda) x_{2},$ must also belong to $S$ for each $\lambda \in[0,1].$
My attempt(draft):
Let $s_{1}$ and $s_{2}$ in $S_{1}$ and $S_{2}$ respectively. By observing that $$s_{1} + s_{2} = \lambda s_{1} + \lambda s_{2} + s_{1} + s_{2} – \lambda s_{1} – \lambda s_{2} = $$
$$=\lambda(s_{1} + s_{2}) + (1 – \lambda)(s_{1} + s_{2})$$
We conclude that: $$\lambda(s_{1} + s_{2}) + (1 – \lambda)(s_{1} + s_{2}) \in S_{1} + S_{2}$$ since it equals $s_{1} + s_{2}$, which belongs to $S_{1} + S_{2}$
Questions:
I think the proof is wrong, since i have not used the fact that both $S_{1}$ and $S_{2}$ are convex sets. However, i have not been able to spot the mistake. Can someone help?
Thanks in advance, Lucas
Related:
Best Answer
On the right track, but not quite there yet. With this definition of convexity, we need to first fix some arbitrary $s\in (S_1+S_2)$, $z\in(S_1+ S_2)$, and $\lambda\in[0,1]$. Then, we must show that $$\lambda s+(1-\lambda)z \in S_1+S_2\tag{*}$$.
Using the definition of the Minkowski sum, we can say $s=s_1+s_2$, where $s_1\in S_1$ and $s_2\in S_2$. Likewise, we can say (without loss of generality) that $z=z_1+z_2$, where $z_1\in S_1$ and $z_2\in S_2$. Now, rephrasing (*), we need to show that
$$\lambda(s_1+s_2) + (1-\lambda)(\mathbf{z_1+z_2}) \in S_1+S_2.$$ However, the current form of your proof has shown that $\lambda(s_1+s_2)+(1-\lambda)(\mathbf{s_1+s_2})\in S_1+S_2$, so it is not quite right.
On the other hand, I say you are on the right track, because you have already found the trick that $s_1=\lambda s_1 + (1-\lambda )s_1$. This is a very common "trick" used in convex analysis, and I think it will help you find the right proof :-)