Exercise 2.13

Consider the standard form polyhedron {x∣Ax = b,x ≥0}. Suppose that the matrix A, of dimensions m × n, has linearly independent rows, and that all basic feasible solutions are nondegenerate.

(a)
Let x be an element of P that has exactly m positive components. Show that x is a basic feasible solution.
(b)
Show that the result of part (a) is false if the nondegeneracy assumption is removed.

Answers

Proof. Let B(1),…,B(m) denote the indices of the m nonzero components of x. By Theorem 2.4, it suffices to demonstrate that

(a)
The columns AB(1),…,AB(m) are linearly independent; and
(b)
if i≠B(1),…,B(m), then xi = 0.

The second condition is true by assumption. Suppose for the sake of contradiction that the first condition does not hold; in other words, AB(1),…,AB(m) are linearly dependent. Then, a degenerate basis formed by these columns, i.e.,

[ | | | AB(1)…AB(m−1)AB(m) | | | ] [ xB(1) ⋮ x B(m−1) xB(m) ] = b 		(1)

can be reduced to

[ | | | AB(1)…AB(m−1)0 | | | ] [ xB(1) + α1xB(1) ⋮ x B(m−1) + αm−1xB(m−1) 0 ] = b. 		(2)

where α1,…,αm−1 ∈ ℜ are such that AB(m) = α1AB(1) + … + αm−1AB(m−1). If AB(1),…,AB(m−1) are linearly independent, then by full row rank assumption, we can find another column Aj, j≠B(1),…,B(m), such that AB(1),…,AB(m−1),Aj are linearly independent. As such, the degenerate vector x′ from (2) is a basic solution corresponding to the matrix

[ | | | AB(1)…AB(m−1)Aj | | | ] [ xB(1) + α1xB(1) ⋮ x B(m−1) + αm−1xB(m−1) 0 ] = b, 		(3)

- a contradiction to the fact that P cannot have degenerate solutions. In case that AB(1),…,AB(m−1) are linearly independent, repeat the procedure until a linearly independent sequence of columns is reached, and replenish it with the remaining columns from {1,…,n}∖{B(1),…,B(m)} to get a linearly independent basis. □

For a counterexample, consider a simple three dimensional polyhedron P defined by the standard form constraint

[011 1 2 0 ] [x1 x2 x3 ] = [4 8 ],x ≥ 0.

Then the vector [0,4,0] is a basic feasible degenerate solution; yet the vector [1,4,0] is not.

User profile picture
2021-12-08 16:12
Comments
  • It seems like you only proved that if $A_{B(1)},...,A_{B(m)}$ are not linear independent, then we can find a degenerate basic solution. But such basic solution may not be feasible. We only have the assumption that all basic feasible solutions are nondegenerate.
    Qi • 2023-05-17
  • To Qi: the constructed degenerate solution is feasible since it satisfies the constraints defining P. I think for polyhedrons of standard form, as long as you have a solution, that would be feasible.
    GT_Buzz • 2024-08-27