Show that Polar of a set is convex

Question

Polar of a set is defined as:

$C^0 = \{ y\in \mathbb{R}^n | y^Tx \leq 1, \forall x \in C\}$

Now from wikipedia, the intuitive idea of polar of a cone is easily understandable. But how can it be shown that $C^0$ is convex, even when $C$ is not? Any hint or explanation is highly appreciated. Thanks.

Answer 1

$C^0$ can be written as the intersection of closed half-spaces: $$ C^0 = \bigcap_{x\in C} \{ y\in \mathbb R^n: x^Ty\le 1\}, $$ hence $C^0$ is convex.

If $C$ is cone then $$ C^0 = \{ y\in \mathbb R^n: x^Ty\le 0 \ \forall x\in C\}, $$ which is sometimes called the dual cone. If $C$ is a linear subspace then $C^0 = C^\perp$.

Answer 2

The half-space proof by daw is quick and elegant; here is also a direct proof:

Let $\alpha\in\left]0,1\right[$, let $x\in C$, and let $y_1,y_2\in C^0$. Then by definition of $C^0$, $y_1^\top x\leq 1$ and $y_2^\top x\leq 1$. Since multiplication by positive numbers preserves inequality, we know $\alpha y_1^\top x\leq \alpha$ and $(1-\alpha)y_2^\top x\leq (1-\alpha)$. Adding both inequalities reveals $$\alpha y_1^\top x+(1-\alpha)y_2^\top x=\big(\alpha y_1+(1-\alpha)y_2\big)^\top x\leq \alpha+(1-\alpha)=1,$$ so $\alpha y_1+(1-\alpha)y_2\in C^0$ which completes the proof.