Let $C\subset \mathbb{R}^n$ be a closed, convex set. The support function of $C$ is the function $\delta^*(\cdot|C):\mathbb{R}^n\rightarrow \mathbb{R}$ given by $$\delta^*(y|C)=\max_{x\in C}\sum x_iy_i.$$ The support function is strictly subbaditive if $$\delta^*(y+z|C)<\delta^*(y|C)+\delta^*(z|C),$$ whenever $y$ and $z$ are not colinear.

Question: What conditions on $C$ are sufficient (and necessary, if possible) to obtain that $\delta^*(\cdot|C)$ is strictly subbaditive?


The necessary and sufficient condition is that $C$ should not have corners: that is, at every boundary point of $C$ there is a unique supporting hyperplane (i.e., the tangent plane). This is a smoothness condition on $C$.

If $C$ was also centrally symmetric, a standard fact about finite-dimensional normed spaces could be used: smoothness of a space is equivalent to strict convexity of its dual. The strict convexity of the dual is precisely the strict subadditivity of the support functions.

Sketch of proof without assuming symmetry. If $w$ is a boundary point with two supporting hyperplanes, let $u,v$ be their normal vectors exterior to $C$. Strict subadditivity fails for $y=w+u$ and $z=w+v$, because the maximum in $\delta^*$ is attained at $w$ for both $y,z$, as well as for their sum.

Converse is left as an exercise for the reader.

| cite | improve this answer | |
  • $\begingroup$ The question was looking for sufficiency. $\endgroup$ – copper.hat Oct 11 '13 at 5:14
  • $\begingroup$ Thanks, this is in line with my intuition for the problem. I did realize that the condition you stated is necessary, and if I understand correctly, you prove necessity. Can you prove the converse as well, or at least give a reference? $\endgroup$ – Henrique Oct 11 '13 at 14:50
  • $\begingroup$ Actually, I see that it's not going to be hard to prove necessity. But what I really wanted to understand is how to phrase the "smoothness" in a way that doesn't involve talking about supporting hyperplanes. I will see if I can rephrase the question to be clear in that respect, but if you know some equivalent formulation of your answer, that'd be great. $\endgroup$ – Henrique Oct 11 '13 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.