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 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)

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.

$\endgroup$
1
$\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.