Exercise 2.1

By Definition 2.1, we must represent the sets in question as

for some matrix $A\in {\Re }^{m\times n}$ and a vector $b\in {\Re }^m$.

(a)

No. To see why, notice that the set $P$ defined by the constraints in question is, in fact, equal to $$Q=\left\{x\in {\Re }^2\mid x^2+y^2\le 1,x\ge 0\right\},$$

and the latter is obviously not a polyhedron.

• Let $x\in P$. In case that $x=0$, we obviously have $x\in Q$. Assume that $x>0$. Then, there exists a $𝜃\in [0,\pi ∕2]$ such that

  $$\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃=\frac{x}{\sqrt{x^2+y^2}},\sin <!--\; FUNCTION\; APPLICATION\; -->𝜃=\sqrt{1-{\cos <!--\; FUNCTION\; APPLICATION\; -->}^2𝜃}=\frac{y}{\sqrt{x^2+y^2}}.$$

  But then from $x\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃+y\sin <!--\; FUNCTION\; APPLICATION\; -->𝜃\le 1$ we deduce that $x^2+y^2\le 1$. In other words, $x\in Q$, i.e., $P\subseteq Q$.

• Take any $x\in Q$ and $𝜃\in [0,\pi ∕2]$. Then,

  $$0\le x\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃+y\sin <!--\; FUNCTION\; APPLICATION\; -->𝜃=|x\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃+y\sin <!--\; FUNCTION\; APPLICATION\; -->𝜃|\le \sqrt{x^2+y^2}\sqrt{{\cos <!--\; FUNCTION\; APPLICATION\; -->}^2𝜃+{\sin <!--\; FUNCTION\; APPLICATION\; -->}^2𝜃}\le 1.$$

  In other words, $x\in P$, i.e., $Q\subseteq P$.

We have thus established that $P=Q$. But $Q$ is not a polyhedron (see this answer on why a ball is not a polyhedron). Thus, $P$ is not a polyhedron as well.

(b)

Yes. Using the standard procedure to find the zeros of a quadratic equation, we can equivalently rewrite $x^2-8x+14\le 0$ as $(x-3)(x-5)\le 0$, which is equivalent to saying that both $x-3\ge 0$ and $x-5\le 0$ must hold. In other words, $$\left\{x\in \Re \mid x^2-8x+14\le 0\right\}=\left\{x\in \Re |\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 1\hfill \end{array}\right]x\ge \left[\begin{array}{c}\hfill -5\hfill \\ \hfill 3\hfill \end{array}\right]\right\}.$$

(c)

Yes. Empty set can be represented as a solution to any unsolvable system of linear equations. For instance, if we demand both $x+y\ge 1$ and $x,y\le 0$, then the polyhedron inequality $$\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -1\hfill \end{array}\right]\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \end{array}\right]\ge \left[\begin{array}{c}\hfill 1\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right].$$

characterizes a polyhedron and the empty set.

(a) Consider the polar coordinate system. Let $x=r\cos <!--\; FUNCTION\; APPLICATION\; -->t,y=r\sin <!--\; FUNCTION\; APPLICATION\; -->t$, $r\ge 0$, $t\in [0,2\pi ]$. Then $x\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃+y\sin <!--\; FUNCTION\; APPLICATION\; -->𝜃\le 1\iff r\cos <!--\; FUNCTION\; APPLICATION\; -->(𝜃-t)\le 1$ and $x\ge 0,y\ge 0\iff t\in \left[0,\frac{\pi }{2}\right]$. Since the inequality must hold for all $𝜃\in \left[0,\frac{\pi }{2}\right]$, we have $r\le 1$. Therefore, the set actually is a quarter of a unit circle and hence is not a polyhedron.

(b) We can equivalently write

Thus, the set is a polyhedron of the form $\{x\in ℝ\mid x\ge 3,x\le 5\}$.

(c) Empty set is a polyhedron. An example is $\{x\in ℝ\mid x\ge 1,x\le 0\}$.