How does strong convexity behave under Minkowski sums?

Question

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 $}$.

Zim · Answer

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$.

How does strong convexity behave under Minkowski sums?

One Answer

Add your own answers!

Ask a Question