Rewriting a set as a polyhedron

Question

I have the following set:

\begin{align} M = \{ x \in \mathbb{R}^n: x \geq 0, x^{T}y \leq 1, \forall y \text{ with } \lVert y \rVert \leq 1 \} \end{align}

I would like to rewrite this set so as to find out whether it is a polyhedron, defined as the intersection of finitely many halfspaces of the form:

\begin{align} P=\{x \in \mathbb{R}^n:Ax \leq b\} \end{align}

How can I do this so as to have the polyhedron, or how can I argument that it is impossible, and thus the set is not a polyhedron?

What I have: if the condition on $y$ from the set m were $\lVert y \rVert = 1$ instead of the inequality, then the set would represent the intersection of the unit ball $\{ x: \lVert x \rVert \leq 1 \}$ (using the Cauchy inequality to rewrite the $x^T y \leq 1$ condition) and the non-negative outhunt $R^n_{+}$. To my understanding, this would not be a polyhedron according to the above definition. How does the $\lVert y \rVert \leq 1$ instead of $\lVert y \rVert = 1$ condition change things?

Answer 1

If the norm is Euclidean then the answer is straightforward.

Note that $\langle x , y \rangle \le 1$ for all $y$ of unit norm or less iff $\max_{\|y\| \le 1} \langle x , y \rangle \le 1$ iff $\|x\| \le 1$.

Hence the set in question can be written as $\{ x | x \ge 0, \|x \| \le 1 \}$.

This is not a polyhedral set.

Note:

This answer is a bit flip in that I have not demonstrated that $M$ is not polyhedral. To take a quote of Rockafellar's slightly out of context, "This classical result is an outstanding example of a fact which is completely obvious to geometric intuition, ... and is not trivial to prove" ("Convex Analysis", p. 171).

In particular, a bounded polyhedral set (a polytope in Rockafellar's nomenclature) has a finite number of extreme points (Corollary 19.1.1 in the above), but it is easy to see that $M$ has an infinite number of extreme points.