# 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 '19 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)

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

• The above doesn't really show that $S$ is not a polyhedron. The $l_1$ unit disk can be represented by an infinite number of contraints but is a polyhedron. – copper.hat Sep 17 '20 at 15:42
• @copper.hat You are right, I added a proof. – Paul Frost Sep 19 '20 at 19:36

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