# Why is this set not a polyhedron?

(Question from Stephen Boyd and Lieven Vandenberghe - Convex Optimization)
$$S = \{x \in \mathbb{R}^n |x \ge 0, x^{T}y \le 1$$ for all $$y \in \mathbb{R}^n$$ such that $$\lVert y \rVert_2 = 1$$}. 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.

• Welcome the Mathematics Stack Exchange community. A quick tour of the site will help you get the most of your time here. For typesetting your equations, please use MathJax. Here is a great reference. – dantopa Feb 10 at 16:54

(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$$.

(2)

For a polyhedron you have only finitely many constraints $$x^Ty_i \le b_i$$, $$i = 1,\dots, n$$. Here you have infinitely many constraints $$x^Ty \le 1$$ with $$y$$ in the unit sphere.

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]$$.