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.
Best Answer
In my opinion, the solution is not totally convincing. It only shows that there is one representation of the set $S$ with infinitely many inequalities. It does not show that there might be another representation with finitely many inequalities.
Of course, for the quarter of the circle $S$, this might be obvious, but it is not mentioned in the solution at all. If this would be an answer of a student in a test or homework, I would not give all possible points.
To give another example: $$R = \{ x \in \mathbb R \mid x \, t \le 1 \; \forall t \in [-1,1]\}.$$ Again, $R$ is defined by infinitely many hyperplanes, but is a polyhedron since $R = [-1,1]$.