Optimization – Support Function of a Set and Supremum Question

convex optimizationconvex-analysisoptimization

I have already learned about what a supremum means from wikipedia and from another answer here. However I am not quite sure what 'supremum over a set of functions' means exactly.

As an example, my book gives an example called "Support function of a set", where it states that the support function "associated with a set C" is:

$$
S_c(x) = sup \{ x^Ty \ |\ y \in C \}
$$

It goes on to say:

"Since $x^Ty$ is an affine function of $x$, so $S_c$ is the pointwise
supremum of a family of affine functions, hence convex"

What I am not too clear about, is, what exactly is a 'supremum of a set of functions' mean? Does this mean that in this case, I am simply taking the supremum of all the dot product results fpr any $x$, across all the vectors $y$ in $C$?

Best Answer

In convex geometry, a supporting line or supporting hyperplane of a convex set $C$ is an affine co-dimension-$1$ subspace $\{y:a^Ty=b\}$ outside of $C$ that touches $C$ in some point or larger facet, i.e., so that $a^TC\le b$ with equality assumed at least once.

From there it is just a twist of thought to compute the constant as $b=\sup a^TC$ and formalize it by giving it a name as a function

$$S_C(x)=\sup\{x^Ty:y\in C\},$$

i.e., $S_C(x)$ is how much you have to shift the plane $\{y:x^Ty=0\}$ to be a supporting hyperplane, thus support function.

Then $C⊂\{y:x^Ty≤S_C(x)\}$. Starting from any even non-convex $C$, the intersection of these supporting half-spaces is the closure of the convex hull of $C$.

As to $S_C$ itself, convex functions are closed under suprema, and since the family of linear functions $x\mapsto x^Ty$, $y\in C$ is a family of convex functions, their pointwise supremum is again convex.