Basic result on convex sets

39 Views Asked by At

I am trying to understand the concept of the support function of convex sets. I want to verify if the following result is correct.

Let $w(\cdot)$ be the support function of a convex set $C\in \mathbb{R}^{n}$. Suppose $x\not\in C$, let $s\in C$ be the closest point to x contained in C. Let $\vec{d}=\vec{Ox}-\vec{Os}$. Then, it would be correct to say $w(\vec{d})=\vec{Os}\cdot \vec{d}$?, if it is correct, why?

1

There are 1 best solutions below

0
On

Your intuition has not lead you astray here; yes this condition holds.

The classic result behind it is sometimes known as Kolmogorov's inequality. Specifically, suppose $C$ is a closed, non-empty, convex subset of $\Bbb{R}^n$ (though the result holds in any real Hilbert space). Suppose $x \in \Bbb{R}^n$ and $z \in C$. Then $z$ is the closest point in $C$ to $x$ if and only if $$(x - z) \cdot (c - z) \le 0$$ for all $c \in C$.

Why does this hold? I'm not going into a full proof here, but it means that the vector from $z$ to $x$ and the vector from $z$ to any other $c \in C$ must be an obtuse (or possibly right) angle. If you think about it, the angle can't ever be an acute angle, because if this were the case, then moving along the line segment between $z$ and $c$ (which is contained in $C$), you will get points that are strictly closer to $x$ than $z$. This would contradict $z$ being the nearest point to $x$ in $C$.

So, if $w$ is the support function of $C$, then we have $$w(x - z) = \sup_{c \in C} (x - z) \cdot c.$$ Kolmogorov's inequality implies $$(x - z) \cdot c \le (x - z) \cdot z$$ for all $c \in C$. Since $z \in C$ too, this means $(x - z) \cdot c$ achieves its maximum over $c \in C$ at $c = z$. Thus, $$w(x - z) = (x - z) \cdot z,$$ as expected.