Exercise 4.12* (Degeneracy and uniqueness - I)

Consider a general linear programming problem and suppose that we have a nondegenerate basic feasible solution to the primal. Show that the complementary slackness conditions lead to a system of equations for the dual vector that has a unique solution.

Answers

Proof. Consider the general primal problem and its dual

minimize c′x subject toAx≥ b , maximize p′b subject top′A = c′ p ≥0.

Now suppose that we have obtained a nondegenerate basic feasible solution x∗ of the primal problem. By complementary slackness (Theorem 4.5), we have

∀ ⁡i = 1,…,m : pi (ai′x∗− b i) = 0 ∀ ⁡j = 1,…,n : (cj −p′A j) xj = 0.

In the exercise, we also assume that xi∗≠0 for all i = 1,…,n. The second condition thus becomes cj −p′Aj, j = 1,…,n. In other words, we want to deduce the dual vector from the system of linear equations

p′A = c′.
(1)

Let B be the set of all indices at which constraints ai′ become active at x∗ and let N denote the rest. By Definition 2.9, the rows ai, i ∈ B must be linearly independent. By Definition 2.10, there are exactly n such indices. Thus, the matrix AB is an n × n invertible matrix (cf. Theorem 1.2). Using this notation, we can equivalently rewrite (1) as

[pB′pN′ ] [AB AN ] = c′.
(2)

By construction, we have ai′x∗ = bi for i ∈ B, and we have ai′x∗ > bi for i ∈ N. Notice that the latter implies pi = 0, i ∈ N, when combined with the first complementary slackness condition. Thus, (2) equivalently becomes:

[pB′0′ ] [AB AN ] = pB′A B = c′.
(3)

As already mentioned, AB is invertible, and the above system will therefore always result in a unique solution. Rearranging the indices back to the original positions in (1), we obtain the desired vector. □

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