$S = \{x \in \mathbb{R}^2\mid x \geq 0, x^Ty \leq 1 ~~\forall y \text{ and } \|y\| = 1\}$

Question

Let $S = \{x \in \mathbb{R}^2\mid x \geq 0, x^Ty \leq 1 ~~\forall y \text{ and } \|y \| = 1\}$ I need to show whether S is a polyhedral. Apparently it is not as I can reduce to show that S is merely a quarter of a circle and S will have infinte extreme points hence S is not a polyhedral.

However, there is one step in the question that I cannot derive. One of the step is to show $\{x \in \mathbb{R}^2\mid x^Ty \leq 1 ~~\forall y \text{ and } \|y\| = 1\} = \{x \in \mathbb{R}^2\mid \|x\| \leq 1\}$

Note that I did not insert in the constraint $x \geq 0$ for the above equation just yet.

I tried to use all knowledge on inner space and properties but cannot effectively deduce the equation and a further question is how do I extrapolate this equation to $\mathbb{R}^n$?

Answer 1

Denote \begin{align} S_1&=\{x \in \mathbb{R}^2\mid x^Ty \leq 1 ~~\forall y \text{ and } \|y\| = 1\},\\ S_2 &= \{x \in \mathbb{R}^2\mid\|x\| \leq 1\}. \end{align}

1. Cauchy-Schwarz $x^Ty\le\|x\|\|y\|\le\|x\|$ shows that $S_2\subset S_1$.
2. To prove $S_1\subset S_2$, take $x\in S_1$, i.e. $x^Ty\le 1$ for all $y$ i the unit ball. Can you pick one $y$ to make it sure that $\|x\|\le 1$?

What about $y=\frac{x}{\|x\|}$? (If $x\ne 0$, of course.)

Answer 2

I will just use a x-y Cartesian coordinate, instead of theorems in linear algebra.

$\lVert\vec{y}\rVert = 1$ means $y_1^2 + y_2^2 = 1$

$\vec{x}^{T}\vec{y}$ means dot product.

Dot product formula:

$\vec{x} \cdot \vec{y} = \lVert \vec{x} \rVert \lVert \vec{y} \rVert \cos(\theta)$

Since $\vec{x} \cdot \vec{y} \le 1$ and $\lVert \vec{y} \rVert \le 1$, we have $\lVert \vec{x} \rVert \cos(\theta) \le 1$

So $\vec{x}$ is not necessarily within the unit circle for all possible $\vec{y}$. For example, for $\cos(\theta) = 0.1$, $\lVert \vec{x} \rVert$ can be 10.

Have to choose a specific $\vec{y}$ that guarantees $\lVert \vec{x} \rVert \le 1$

Since the problem's condition is for all $\lVert \vec{y} \rVert \le 1$, you can choose a $\vec{y}$ that makes $\theta$ have a specific value, which can force $\lVert \vec{x} \rVert \le 1$.

For each possible $\vec{x}$, I choose a $\vec{y}$ that has a length of 1 and is parallel to $\vec{x}$.

That makes $\cos(\theta) = 1$. Since $\lVert \vec{x} \rVert \cos(\theta) \le 1$, that means $\lVert \vec{x} \rVert \le 1$.

The dot product formula and Cauchy–Schwarz inequality both work in higher dimensions.