Exercise 4.26

Let A be a given matrix. Show that exactly one of the following alternatives must hold.

(a)
There exists some x≠0 such that Ax = 0,x ≥0.
(b)
There exists some p such that p′A > 0′.

Answers

Remark 1. Note that the existence of a vector p such that p′A > 0 is equivalent to the existence of a vector p such that p′A > e, where e is the vector with all components equal to 1, since we can always rescale the former using a scalar large enough so that all of the components of p′A > 0 become larger than 1.

Proof. The trick is to consider the following pair of problems that are duals of each other:

minimize p′0 subject top′A ≥ej′, maximize e′x subject toAx= 0 x ≥0.
(1)
  • Suppose that (b) holds. Then the primal problem in (1) is feasible with the optimal cost 0. By strong duality (Theorem 4.4), the dual problem has an optimal cost of 0 as well. Suppose that there exists a x≠0 with Ax = 0 and x ≥ 0. Then x is feasible for the dual problem in (1), and its cost is e′x > 0 - a contradiction. Thus, only (b) holds.
  • Suppose that (b) does not hold. Then the primal problem in (1) is infeasible. From Table 4.2 we know that the dual problem must then be either infeasible or unbounded. The former case does not hold since the zero vector 0 is always feasible for the dual problem in (1). Thus, the dual is unbounded. In other words, e′x > 0 is achievable for some x with Ax = 0 and x ≥0 - implying that x≠0. In other words, (a) holds.
□
User profile picture
2022-03-21 01:05
Comments