Linear programming

Question

Consider an LP in standard form with feasible region S, and constraints Ax = b and x ≥ 0

component-wise. Recall that a nonzero vector d is a direction of unboundedness if ∀s ∈ S, c ≥ 0,

x + cd ∈ S. Show that d is a direction of unboundedness if and only if Ad = 0 and d > 0 component-wise.

Answer 1

I'll prove both directions of this characterization of directions of unboundedness.

Theorem

For an LP in standard form with feasible region S = {x : Ax = b, x ≥ 0}, a nonzero vector d is a direction of unboundedness if and only if Ad = 0 and d ≥ 0 (component-wise).

Proof

(⇒) Forward Direction: If d is a direction of unboundedness, then Ad = 0 and d ≥ 0

Assume d is a direction of unboundedness. By definition, for all s ∈ S and all c ≥ 0, we have s + cd ∈ S.

Step 1: Show Ad = 0

Let s ∈ S be arbitrary. Then As = b.

Since s + cd ∈ S for all c ≥ 0, we must have: A(s+cd)=bA(s+cd)=b

Expanding: As+cAd=bAs+cAd=b

Since As = b: b+cAd=bb+cAd=b cAd=0cAd=0

This must hold for all c ≥ 0. In particular, for c = 1: Ad=0Ad=0

Step 2: Show d ≥ 0

Since s + cd ∈ S for all c ≥ 0, we need s + cd ≥ 0 (component-wise).

For the i-th component: $s_i + cd_i ≥ 0$ for all c ≥ 0.

Suppose, for contradiction, that $d_i < 0$ for some component i.

Choose s ∈ S with $s_i ≥ 0$ (S is nonempty by assumption of feasibility).

Then for sufficiently large c, specifically for $c > -s_i/d_i$: si+cdi=si+c⋅di<si+−sidi⋅di=si−si=0si​+cdi​=si​+c⋅di​<si​+di​−si​​⋅di​=si​−si​=0

This violates s + cd ≥ 0, contradicting that d is a direction of unboundedness.

Therefore, $d_i ≥ 0$ for all i, so d ≥ 0.

(⇐) Reverse Direction: If Ad = 0 and d ≥ 0, then d is a direction of unboundedness

Assume Ad = 0 and d ≥ 0 (component-wise).

Let s ∈ S be arbitrary and let c ≥ 0. We need to show that s + cd ∈ S.

Check the equality constraint: A(s+cd)=As+cAd=b+c⋅0=bA(s+cd)=As+cAd=b+c⋅0=b ✓

Check the non-negativity constraint:

For each component i: (s+cd)i=si+cdi(s+cd)i​=si​+cdi​

Since s ∈ S, we have $s_i ≥ 0$. Since d ≥ 0, we have $d_i ≥ 0$. Since c ≥ 0, we have $cd_i ≥ 0$.

Therefore: $(s + cd)_i = s_i + cd_i ≥ 0$ ✓

Thus s + cd satisfies both Ax = b and x ≥ 0, so s + cd ∈ S.

This holds for all s ∈ S and all c ≥ 0, so d is a direction of unboundedness. ∎

Intuition

This result makes geometric sense:

1. Ad = 0 means d lies in the null space of A, so moving in direction d doesn't violate the equality constraints
2. d ≥ 0 ensures we never move in a negative direction, so we can't violate the non-negativity constraints regardless of how far we move

Together, these conditions allow unlimited movement along d while remaining feasible.