# How does strong convexity behave under Minkowski sums?

Suppose we have two convex sets $$A,B$$. It is straightforward to show the sum $$A+B = \{a+b:a \in A,b\in B\}$$ is convex. For take any $$c=a+b$$ and $$c'=a'+b'$$ and consider the convex combination

$$xc+(1-x)c' = x(a+b)+(1-x)(a'+b')$$ $$= \big(xa+(1-x)a'\big) + \big( xb+(1-x)b'\big).$$

By convexity the two summand are in $$A,B$$ respectively. Hence the sum is in $$A+B$$ as required.

Now suppose $$A$$ is $$\alpha$$-strongly convex and $$B$$ is $$\beta$$-strongly convex. That means the for each $$a,a' \in A$$ and $$x \in [0,1]$$ that the ball centred at $$xa+(1-x)a'$$ of radius $$\alpha x(1-x)$$ is contained in $$A$$. Likewise for each $$b,b' \in B$$ and $$x \in [0,1]$$ that the ball centred at $$xb+(1-x)b'$$ of radius $$\beta x(1-x)$$ is contained in $$B$$.

Can we say anything about the strong-convexity parameter of $$A+B$$? By that I mean $$\inf\{ \gamma \ge 0: A+B$$ is $$\gamma$$-strongly convex $$\}$$.

• Are you supposing that $\alpha$ and $\beta$ are also "sharp" in the sense that they're the smallest possible strong convexity constant with respect to $A$ and $B$?
– Zim
Jul 28, 2020 at 16:11
• @Zim Oh yeah we'd have to assume that to say anything about the inf for $A+B$. But even lower bounds for $A+B$ would be nice. Jul 28, 2020 at 16:19
• Wait, isn't the "sharpest" strong convexity constant the largest one? If $\gamma_1<\gamma_2$, then the ball of radius $\gamma_1$ is contained in the ball of radius $\gamma_2$, so if $C$ is $\gamma_2$ strongly convex, then it must be $\gamma_1$ strongly convex.
– Zim
Jul 28, 2020 at 17:29
• @Zim Yes you're right. We should be talking about the sup and not the inf. Jul 28, 2020 at 17:55
• great, well I think $\max\{\alpha,\beta\}$ might be the best we can do (see answer below).
– Zim
Jul 29, 2020 at 15:53

If $$A$$ is $$\alpha$$-strongly convex and $$B$$ is $$\beta$$-strongly convex, then $$A+B$$ is $$\gamma:=\max\{\alpha,\beta\}$$-strongly convex.
Proof: Let $$a_1,a_2\in A$$, let $$b_1,b_2\in B$$, and let $$\eta\in[0,1]$$. For notational simplicity, I will set $$a:=\eta a_1+(1-\eta)a_2$$ and $$b:=\eta b_1+(1-\eta)b_2$$. Now suppose that $$z$$ is in the ball centered at $$\eta(a_1+b_1) + (1-\eta)(a_2+b_2)=a+b$$ with radius $$\eta(1-\eta)\gamma$$. It suffices to show that $$z\in A+B$$. By the construction of $$\gamma$$ and definition of $$z$$, either
$$$$\|a+b-z\|=\|a - \left(z - b\right)\| \leq \eta(1-\eta)\gamma=\eta(1-\eta)\max\{\alpha,\beta\} =\eta(1-\eta)\alpha, \tag{1}$$$$ or, $$$$\|a+b-z\|=\|b - \left(z - a\right)\|\leq \eta(1-\eta)\beta. \tag{2}$$$$
If (1) holds, then $$z-b$$ is in the ball centered at $$a$$ with the proper radius. Since $$A$$ is strongly convex, this implies $$z-b\in A$$ and hence $$z\in A+b\subset A+B$$. Likewise, if (2) holds, then $$z-a$$ is in the ball centered at $$b$$ with the proper radius. Since $$B$$ is strongly convex, we find $$z-a\in B$$ and hence $$z\in B+a\subset A+B$$.