Let $C \subset \mathbb{R}^n$ be a given set. Show that the set $C^o = {\{y \in \mathbb{R}^n : y^Tx \le 0, \forall x \in C\}}$ is convex.

Question

I was wondering if this proof worked for this problem.

Let $t, s \in C$ and $\lambda \in [0,1].$ Let $z = \lambda t + (1 - \lambda)s$. Then $$y^Tz = y^T(\lambda t + (1 - \lambda)s$$ $$=\lambda y^Tt + (1-\lambda)y^Ts$$ Now $y^Tt$ and $y^Ts$ are $\le 0$, since $t, s \in C$. So then we know that $$\lambda y^Tt + (1-\lambda)y^Ts \le \lambda (0) + (1- \lambda) (0) = 0.$$ Thus, $z \in C$ and so the set is convex.

Also, how would one sketch this set?

Thanks ahead of time.

Answer 1

If you draw a picture, then it is clear : For $y,\ z\in C^0$, $$ [ty +(1-t)z ]^T x = ty^Tx + (1-t)z^T x \leq 0 $$ for all $x\in C$ and any $t \in (0,1)$.

Answer 2

Take x $\in$ C. Consider the plane P in $\mathbb{R}^n$ with normal vector $x$. The set C$^0_x$ = {y | $y^Tx \leq 0\}$ can be thought of as the closed half-space that lies on the opposite side of P as $x$. This is obviously convex. Note C = $\bigcap_{x \in C} C^0_x$. So the intersection of all these closed half-spaces is convex.