Exercise 4.19 (Null variables)

Let P = {x ∈ℜn∣Ax = b,x ≥0} be a nonempty polyhedron, and let m be the dimension of the vector b. We call xj a null variable if xj = 0 whenever x ∈ P.

(a)
Suppose that there exists some p ∈ℜm for which p′A ≥0′,p′b = 0, and such that the j th component of p′A is positive. Prove that xj is a null variable.
(b)
Prove the converse of (a): if xj is a null variable, then there exists some p ∈ℜm with the properties stated in part (a).
(c)
If xj is not a null variable, then by definition, there exists some y ∈ P for which yj > 0. Use the results in parts (a) and (b) to prove that there exist x ∈ P and p ∈ℜm such that:

p′A ≥0′,p′b = 0,x + A′p > 0.

Answers

(a)

Proof. Consider the following pair of problems that are duals of each other:

minimize − xj subject toAx ≥b x ≥0, maximize p′b subject top′A ≤−ej′,
(1)

where ej denotes the unit vector in jth direction. Let c denote p′A’s jth direction; by assumption, c > 0. Define q := −1 cp. Then it is obvious that q is feasible for the dual problem as well, and the corresponding cost is q′b = −1 cp′b = 0. By weak duality (Theorem 4.3), the optimal cost of the primal problem cannot go lower than 0. But it cannot be positive either; thus, we conclude that xj will always be a null variable. □

(b)

Proof. Since xj is a null variable, the optimal cost of the primal problem in (1) will be 0. By strong duality (Theorem 4.4), the optimal cost of the dual problem is 0 as well. Let q denote the corresponding optimal solution. Then it is easy obvious that p := −q satisfies p′A ≥ej′≥0′, (p′A)j ≥ 1 > 0 and p′b = 0. □

(c)

Proof. Let I denote the indices of non-null variables, and let N denote the indices of null variables.
By definition, for each j ∈ I, we can find a vector x(j) such that xj(j) > 0. By setting x := ∑ ⁡ j∈Ix(j), we ensure that x is positive at all nonnull variables.
Similarly, by part (a), for each j ∈ N, we can find a vector p(j) such that its jth component (p(j)′A)j is positive. Setting p := ∑ ⁡ j∈Np(j), we ensure that p′A is strictly positive at every null variable.
Finally, since both x ≥0 and p′A ≥0, adding x + p′A results in a strictly positive vector. □

User profile picture
2022-03-21 00:20
Comments

c. I think it should be set x := 1 |I|∑ ⁡ j∈Ix(j) to satisfy Ax = b.

User profile picture
2022-06-21 13:13
Comments