Prove the Convexity

Question

For the set C in R. We have

S={y \in R^n: y^Tx \leq 1 for all x \in C}. How to prove S is convex

I used the basic definition of convexity to do this.

Also, how to characterize the S in terms of C when specific C is given.

Answer 1

To show it is convex:

1. Let $\boldsymbol{y}{1}, \boldsymbol{y}{2} \in \mathcal{S}$.
2. For $\alpha \in \left[ 0, 1 \right]$, show that $\alpha \boldsymbol{y}{1} + \left( 1 - \alpha \right) \boldsymbol{y}{2} \in \mathcal{S}$.

The (2) step is trivial, as we get:

$$ {\left( \alpha \boldsymbol{y}{1} + \left( 1 - \alpha \right) \boldsymbol{y}{2} \right)}^{T} \boldsymbol{x} = \alpha \boldsymbol{y}{1}^{T} \boldsymbol{x} + \left( 1 - \alpha \right) \boldsymbol{y}{2}^{T} \boldsymbol{x} \leq 1 $$

Which proves the set is indeed convex.