Lemma 2 — valid inequalities of a polyhedron with a bounded nonconstant direction are nonnegative combinations
ProvedExtensionComplexity.TSP.valid_inequality_nonneg_combinationLet , and , a possibly unbounded polyhedron. Suppose some direction satisfies
and let be valid for (satisfied by every point of ). Lemma 2: there are nonnegative multipliers with
that is, is a nonnegative combination of the rows of , with equality in the right-hand side.
Ordinary Farkas gives ; the hypothesis on is what upgrades it to equality, and this is what the proof of Theorem 3 needs to show that rows of a slack matrix for redundant inequalities are nonnegative combinations of the others.
Formalization Note The page prints ""; since has rows, , which is what is stated. The minimum and maximum are required to exist (IsLeast/IsGreatest of ), which is the meaning of the finite /. The lemma's "In particular" sentence (polytopes of dimension at least , and unbounded polyhedra projecting onto them) is not part of this statement.
import Mathlib open Matrix
namespace ExtensionComplexity.TSP
/-- **Lemma 2** (Fiorini et al., J. ACM 62(2) (2015), Art. 17, pp. 17:9–17:10): let
`P = {x ∈ ℝ^d | Ax ≤ b}` be a (possibly unbounded) polyhedron admitting a direction `u` such that
`min{uᵀx | x ∈ P}` and `max{uᵀx | x ∈ P}` are finite (attained) and the minimum is strictly less
than the maximum, and let `cᵀx ≤ δ` be valid for `P`. Then there are nonnegative multipliers
`λ ∈ ℝ^m` (the page prints `ℝ^d`; `A` has `m` rows) with `λᵀA = cᵀ` and `λᵀb = δ`. -/
theorem valid_inequality_nonneg_combination {m d : ℕ} (A : Matrix (Fin m) (Fin d) ℝ)
(b : Fin m → ℝ) (P : Set (Fin d → ℝ)) (hP : P = {x | A *ᵥ x ≤ b})
(u : Fin d → ℝ) (lo hi : ℝ) (hlo : IsLeast ((fun x => u ⬝ᵥ x) '' P) lo)
(hhi : IsGreatest ((fun x => u ⬝ᵥ x) '' P) hi) (hlohi : lo < hi)
(c : Fin d → ℝ) (δ : ℝ) (hvalid : ∀ x ∈ P, c ⬝ᵥ x ≤ δ) :
∃ lam : Fin m → ℝ, 0 ≤ lam ∧ lam ᵥ* A = c ∧ lam ⬝ᵥ b = δ := by sorry
end ExtensionComplexity.TSP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.