How does strong convexity behave under Minkowski sums?

Mathematics Asked by Daron on October 14, 2020

Suppose we have two convex sets $$A,B$$. It is straightforward to show the sum $$A+B = {a+b:a in A,bin 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 $$}$$.

I'm going for the largest strong convexity constant, since any smaller value also works.

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_2in A$$, let $$b_1,b_2in B$$, and let $$etain[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 $$zin A+B$$. By the construction of $$gamma$$ and definition of $$z$$, either

$$begin{equation} |a+b-z|=|a - left(z - bright)| leq eta(1-eta)gamma=eta(1-eta)max{alpha,beta} =eta(1-eta)alpha, tag{1} end{equation}$$ or, $$begin{equation} |a+b-z|=|b - left(z - aright)|leq eta(1-eta)beta. tag{2} end{equation}$$

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-bin A$$ and hence $$zin A+bsubset 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-ain B$$ and hence $$zin B+asubset A+B$$.

Answered by Zim on October 14, 2020