Exercise 3.8*

Solution. (a) Since $P$ is a polyhedron, it can be represented by a set of linear inequalities, $P=\{x\in {ℝ}^n\mid \mathrm{Ax}\le b\}$ for some matrix $A$ and vector $b$. Let $y=(z,t)$ be a vector in ${ℝ}^{n+1}$. The set $Q$ consists of all such vectors $y$ for which $z=tx$ for some $x\in P$ and $t\in [0,1]$.

We can express these conditions using linear inequalities on $y=(z,t)$:

• If $t>0$, the condition $x\in P$ is equivalent to $A(z∕t)\le b$, which can be rewritten as $\mathrm{Az}\le tb$, or $\mathrm{Az}-tb\le 0$.
• If $t=0$, the condition $z=tx$ implies $z=0$. In this case, the inequality $\mathrm{Az}-tb\le 0$ becomes $0\le 0$, which is satisfied.

The condition $t\in [0,1]$ is equivalent to the two linear inequalities $t\le 1$ and $-t\le 0$. Thus, the set $Q$ can be described as:

Since $Q$ is defined by a finite set of linear inequalities, it is a polyhedron.

(b) Let $n=2$ and consider the polyhedron $P=\{x\in {ℝ}^2\mid x_1\ge 0,x_2\ge 0,x_1+x_2\le 1\}$. This can be written as $\mathrm{Ax}\le b$ with

The corresponding polyhedron $Q\subset {ℝ}^3$ is defined by the inequalities:

A basic feasible solution in ${ℝ}^3$ is degenerate if more than 3 constraints are active at that point. At the zero vector $(z,t)=(0,0,0)$, all four of the inequalities listed above are active. Furthermore, we can find 3 linearly independent constraint vectors among them, for example, the normal vectors $(-1,0,0)$, $(0,-1,0)$, and $(0,0,-1)$. Therefore, the zero vector is a degenerate basic feasible solution of $Q$.

Geometrically, $P$ is a triangle in ${ℝ}^2$ with vertices at $(0,0)$, $(1,0)$, and $(0,1)$. The set $Q$ is a pyramid in ${ℝ}^3$ with its apex at the origin and its base being the triangle $P$ on the plane $t=1$.

(c) The optimization problem over $Q$ is to minimize ${(c,0)}^{\prime }y=c^{\prime }z$. Since any point in $Q$ is of the form $y=(tx,t)$, the objective function is $c^{\prime }(tx)=t(c^{\prime }x)$. The problem is thus:

We prove both directions of the equivalence.

( $\Rightarrow$) Assume the zero vector is an optimal solution. The optimal cost is therefore 0. This means that for any $x\in P$ and any $t\in [0,1]$, we must have $t(c^{\prime }x)\ge 0$. If we choose $t=1$, this implies that $c^{\prime }x\ge 0$ for all $x\in P$. Consequently, the optimal cost in the original problem, $\underset{x\in P}{\min <!--\; FUNCTION\; APPLICATION\; -->}{c}^{\prime }x$, must be greater than or equal to zero.

( $\Leftarrow$) Assume the optimal cost in the original problem is greater than or equal to zero. This means $c^{\prime }x\ge 0$ for all $x\in P$. Since $t\in [0,1]$ is always non-negative, the objective function $t(c^{\prime }x)$ must also be non-negative. The zero vector, which is in $Q$ (by setting $t=0$), yields a cost of $0\cdot (c^{\prime }x)=0$. Since the cost is always non-negative, a cost of 0 must be optimal. Therefore, the zero vector is an optimal solution. □