While this submission is a draft, it cannot be used by other submissions.

Proof of `Unbounded linear programs have improving recession directions`

groundedproofs/Lax109476Proofs/Recession.lean · lax-109476

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Apply Farkas' lemma to Ad≤0Ad\le0, d≥0d\ge0, cTd≥1c^Td\ge1. An infeasibility certificate has a strictly positive multiplier tt on the final row. Dividing the other multipliers by tt gives a dual feasible vector for the original program. Weak duality then supplies a finite objective bound, a contradiction.