1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ I added a relevant note to my answer, lest your teacher be picky... $\endgroup$ Commented Apr 23, 2017 at 19:00

1 Answer 1

Reset to default
0
$\begingroup$

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.

Note:

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.