I have the following set:

\begin{align} M = \{ x \in \mathbb{R}^n: x \geq 0, x^{T}y \leq 1, \forall y \text{ with } \lVert y \rVert \leq 1 \} \end{align}

I would like to rewrite this set so as to find out whether it is a polyhedron, defined as the intersection of finitely many halfspaces of the form:

\begin{align} P=\{x \in \mathbb{R}^n:Ax \leq b\} \end{align}

How can I do this so as to have the polyhedron, or how can I argument that it is impossible, and thus the set is not a polyhedron?

What I have: if the condition on $y$ from the set m were $\lVert y \rVert = 1$ instead of the inequality, then the set would represent the intersection of the unit ball $\{ x: \lVert x \rVert \leq 1 \}$ (using the Cauchy inequality to rewrite the $x^T y \leq 1$ condition) and the non-negative outhunt $R^n_{+}$. To my understanding, this would not be a polyhedron according to the above definition. How does the $\lVert y \rVert \leq 1$ instead of $\lVert y \rVert = 1$ condition change things?

  • $\begingroup$ I added a relevant note to my answer, lest your teacher be picky... $\endgroup$ – copper.hat Apr 23 '17 at 19:00

If the norm is Euclidean then the answer is straightforward.

Note that $\langle x , y \rangle \le 1$ for all $y$ of unit norm or less iff $\max_{\|y\| \le 1} \langle x , y \rangle \le 1$ iff $\|x\| \le 1$.

Hence the set in question can be written as $\{ x | x \ge 0, \|x \| \le 1 \}$.

This is not a polyhedral set.


This answer is a bit flip in that I have not demonstrated that $M$ is not polyhedral. To take a quote of Rockafellar's slightly out of context, "This classical result is an outstanding example of a fact which is completely obvious to geometric intuition, ... and is not trivial to prove" ("Convex Analysis", p. 171).

In particular, a bounded polyhedral set (a polytope in Rockafellar's nomenclature) has a finite number of extreme points (Corollary 19.1.1 in the above), but it is easy to see that $M$ has an infinite number of extreme points.


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.