Is $\{ x \in \mathbb{R}^2 \mid x \ge 0, v^Tx \le 1 \quad (\forall v \in \mathbb{R}^2 : \lvert\lvert v \rvert\rvert = 1) \}$ a polyhedron?

Question

I am working on the following exercise:

Consider $$P := \{ x \in \mathbb{R}^2 \mid x \ge 0, v^Tx \le 1 \quad (\forall v \in \mathbb{R}^2 : \lvert\lvert v \rvert\rvert = 1) \}$$

Is $P$ a polyhedron?

I think that $P$ is not a polyhedron since there are infinitely many such $v$, so we may not express $P$ in terms of a matrix.

Could you please tell me if my reasoning works?

@CalvinKhor $v$ is probably a fixed vector... $v^T x \leq 1$ is a linear restriction. — PierreCarre, May 23 '22 at 14:02
@PierreCarre but $\forall v$ appears inside the definition for the set? so is it not the intersection over all such $v$? — Calvin Khor, May 23 '22 at 14:03
You probably mean a polygon since polyhedrons are 3D objects (https://en.wikipedia.org/wiki/Polyhedron). Also note that $P$ can be unbounded, e.g. when $v = (-1,0)$ — blamocur, May 23 '22 at 14:04
@CalvinKhor I believe that the definition of the set is not formally correct but the intention of the question is the one I mentioned. — PierreCarre, May 23 '22 at 14:04
@PierreCarre I guess, given the tag, your interpretation makes more sense! — Calvin Khor, May 23 '22 at 14:06
@PierreCarre: Sorry, but the question is exaclty as I wrote it above. — 3nondatur, May 23 '22 at 14:07
I believe that $P$ as given above is not a polyhedron, but I do not see how to justify that $P$ can not be described via a matrix. I mean geometrically is clear since this quarter circle can not be described via finitely many halfspaces. — 3nondatur, May 23 '22 at 14:11
In that case @CalvinKhor is correct when he says that $P$ is a quarter of circle, and so not a polygon. — PierreCarre, May 23 '22 at 14:17

PierreCarre · Accepted Answer · 2022-05-23T15:28:00.253

1

If you consider the cases $v_1=0, v_2=1$ and $v1=1, v_2=0$, you see the $P \subseteq [0,1]\times[0,1]$. Additionally, we can show that, when $v_1^2+v_2^2=1$, the line defined by $v_1 x+v_2 y = 1$ is tangent to the unit circle, which leads to the conclusion mentioned by @CalvinKhor: $P$ is the parte of the unit circle in the first quadrant, and so not a polygon.

edited May 23 '22 at 15:28

answered May 23 '22 at 14:01

PierreCarre

20,974
1
18
34

Is $\{ x \in \mathbb{R}^2 \mid x \ge 0, v^Tx \le 1 \quad (\forall v \in \mathbb{R}^2 : \lvert\lvert v \rvert\rvert = 1) \}$ a polyhedron?

1 Answers1