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.

New contributor
Atul Balaji is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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

Atul Balaji is a new contributor. Be nice, and check out our Code of Conduct.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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