From Stephen Boyd & Lieven Vandenberghe's Convex Optimization:
$$S = \left\{ x \in \mathbb{R}^n \mid x \ge 0, x^{T} y \le 1 ,\, \forall y \in \mathbb{R}^n \text{ such that } \lVert y \rVert_2 = 1 \right\}$$ Is the set $S$ a polyhedron?
The solution given is:
S is not a polyhedron. It is the intersection of the unit ball $\{x | \lVert x \rVert_2 \le 1\}$ and the nonnegative orthant $\mathbb{R}^n_+$. This follows from the following fact, which follows from the Cauchy-Schwarz inequality:
$$x^{T}y \le 1 \text{ for all } y \text{ with } \lVert y \rVert_2 = 1 \iff \left\lVert x \right\rVert_2 \leq 1\label{1}\tag{1}$$
Although in this example we define $S$ as an intersection of halfspaces, it is not a polyhedron, because the definition requires infinitely many halfspaces.$\label{2}\tag{2}$
I am not able to understand how \ref{1} is obtained using the Cauchy Schwarz inequality $(x^Ty \le \lVert x \rVert_2\lVert y \rVert_2)$ and how \ref{2} is correct, since we need only a finite number of halfspaces and not infinite for it to be polyhedron.
(1)
"$\Leftarrow$" We have $\lVert x \rVert_2 \leq 1$. Then for any $y$ with $\lVert y \rVert_2 = 1$ we get $x^Ty \le \lVert x \rVert_2\lVert y \rVert_2 \le 1 \cdot 1 = 1$.
"$\Rightarrow$" We have $x^T y \le 1$ for all $y$ with $\lVert y \rVert_2 = 1$. If $x = 0$, then trivially $\lVert x \rVert_2 \leq 1$. If $x \ne 0$, then $\lVert x \rVert_2 = \frac{\lVert x \rVert_2^2}{\lVert x \rVert_2} = \frac{x^T x}{\lVert x \rVert_2} = x^T \frac{x}{\lVert x \rVert_2} \le 1$. The last inequality is due to $x^Ty \leq 1$ with $y=\frac{x}{\lVert x \rVert_2}$.
(2)
A polyhedron is determined by finitely many constraints $x^Ty_i \le r_i$, $i = 1,\dots, n$. But here (in case $n > 1$) we have infinitely many constraints $x^Ty \le 1$ with $y$ in the unit sphere $S^{n-1}$. To get $S$, we need the additional constraints $x^T(-e_i) \le 0$ (equivalent to $x^Te_i \ge 0$) for $i=1,\ldots,n$, where the $e_i$ are the standard basis vectors of $\mathbb R^n$.
The case $n=1$ is an exception because $S^0 = \{-1,1\}$. Two constraints are sufficient in that case.
Edited:
As copper.hat remarks, the fact that for $n > 1$ we have represented $S$ via infinitely many constraints does not imply that it is impossible via finitely many constraints. So let us give a proof.
Boyd and Vandenberghe define a polyhedron as the intersection of finitely many halfspaces and hyperplanes. Since each hyperplane $P$ is the intersection of the two halfspaces bounded by $P$, we can equivalently define a polyhedron as the intersection of finitely many halfspaces. A halfspace is a set $H(y,r) = \{ x \in \mathbb R^n \mid y^Tx \le r \}$ with $y \in \mathbb R^n \setminus \{0\}$ and $r \in \mathbb R$. Note that we exclude $y = 0$ because $H(0,r)$ is either $= \mathbb R^n$ or empty. Also note that $y^Tx = x^Ty = \langle x, y \rangle$, where $\langle -, - \rangle$ is the standard inner product on $\mathbb R^n$. Let us write $P(y,r)$ for the hyperplane $x^Ty = r$ which is the boundary of $H(y,r)$.
The representation of a halfspace as a set $H(y,r)$ is not unique. However, it has a unique representation as $H(y, r)$ with $y \in S^{n-1}$ ("normalized form"). In fact, $\langle x, y \rangle = \lVert y \rVert\langle x, y/\lVert y \rVert \rangle$, thus $H(y,r) = H(y/\lVert y \rVert, r/\lVert y \rVert)$.
Assume that $S = \bigcap_{j=1}^m H(y_j,r_j)$ with $y_j \in S^{n-1}$. This describes $S$ by $m$ constraints. Define $T = \{x = (x_1,\ldots,x_n) \in \mathbb R^n \mid \lVert x \rVert_2 = 1, x_i > 0 \text{ for } i =1,\ldots,n \}$. For $y \in T$ let $L(y) = \{ ty \mid t \in \mathbb R \}$ be the line through $0$ and $y$ and let $R(y) = \{ ty \mid t > 1 \}$. The $m$ constraints must rule out $R(y)$. If $P(y_j,r_j)$ is parallel to $L(y)$, no point of $R(y)$ is ruled out and the constraint is irrelevant. All other $P(y_j,r_j)$ are not parallel to $L(y)$, hence $P(y_j,r_j)$ and $L(y)$ intersect in a unique point $p_j = t_jy$. Since $0 \in H(y_j,r_j)$, the segment $I(t_j) = \{ ty \mid 0 \le t \le t_j \}$ is contained in $H(y_j,r_j)$ and the open ray $J(t_j) = \{ty \mid t > t_j \}$ is disjoint from $H(y_j,r_j)$, i.e. is ruled out by the constraint. $t_j < 1$ is impossible because then the constraint would rule out all points of the form $ty$ with $t_j < t \le 1$ although they belong to $S$. It is also impossible that all $t_j > 1$ because then $\theta = \min t_j > 1$ and $\theta y \notin S$ is not ruled out. Hence some $t_j = 1$ and $P(y_j,r_j) \cap L(y) = \{y\}$. If $P(y_j,r_j)$ is not the tangential hyperplane to $S^{n-1}$ at $y$, then $P(y_j,r_j)$ splits $S$ into two non-empty parts. Thus $S$ cannot be contained in $H(y_j,r_j)$. Therefore $P(y_j,r_j)$ must be the tangential hyperplane at $y$ which means $y_j = y$ and $r = 1$.
We have shown that for each $y \in T$ one of the $m$ constraints $H(y_j,r_j)$ must be $H(y,1)$. This impossible because there are infinitely many $y \in T$.