0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – dantopa Feb 10 '19 at 16:54
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – copper.hat Sep 17 '20 at 15:42
  • $\begingroup$ @copper.hat You are right, I added a proof. $\endgroup$ – Paul Frost Sep 19 '20 at 19:36
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.