2

Recently I have encountered this set, from "Introduction to Linear Optimization" by D. Bertsimas and John.N.Tsitsiklis:

$$P = \{(x,y) \in \mathbb{R}^2 : x \cos \theta + y \sin \theta \le 1, \forall \theta \in [0; \pi/2 ] \wedge x \ge 0 \wedge y \ge 0 \}$$

They ask if the set is a polyhedron or not. I guess that the answer is negative, as the variables have uncountable amount of constraints. I had some idea in mind, but I cannot enforce them into a real solution.

For now, I am trying to assume that there exists a matrix $A^{m \times 2}$ and a vector $b \in \mathbb{R}^m$ such that: $$P = \{ x \in \mathbb{R}^2: Ax \ge b \} $$ After that, I was attemping to prove that we can at least "turn" most of the constrains into the form of $x \cos \alpha_i + y \sin \alpha_i \ge \beta_i$, with $\alpha_i \in [0;\pi/2]$. In order to achieve this, I was trying to prove that the constrains with the form of $a_{i1}x + a_{i2}x \ge b_i$ with $a_{i1} < 0$ or $a_{i2} < 0$ are redundant. However, up to the current moment, my attempts seem to be in vain.

Please check my guess and my idea if it was correct in the first place, and please guide me to the solution of this problem.

Thank you for reading.

Jean Marie
  • 81,803
ElementX
  • 922

1 Answers1

2

$P$ is simply $Q=\{ (x,y) | x \geq 0, y \geq 0, x^2 + y^2 \leq 1 \}$. And it should be easy to prove $Q$ is not a polytope.

Let $(x,y) \in P$, if $x=y=0$ then clearly $(x,y) \in Q$ otherwise since $x \geq 0,y \geq 0$ there is a $\theta \in [0,\pi/2]$ with $\cos\theta = \dfrac{x}{\sqrt{x^2+y^2}}$ and $\sin\theta=\dfrac{y}{\sqrt{x^2+y^2}}.$ We must have $x\cos\theta+y\sin\theta \leq 1$ so $x^2 + y^2 \leq 1$. So $P \subseteq Q$.

Take any $(x,y) \in Q$ and $\theta \in [0,\pi/2]$ then $0 \leq x\cos\theta + y\sin\theta = |x\cos\theta + y\sin\theta| \leq \sqrt{x^2+y^2}\sqrt{\cos^2\theta + \sin^2\theta} \leq 1$. So $Q \subseteq P$.

Arin Chaudhuri
  • 6,349