Lemma 2 — a coherent monotone path passes through a -maximum
ProvedZeroOneSimplex.lemma_2linear-programmingp2o-gran-per-chapterp2o-plan-paperp2o-v1pivot-rulespolytopessimplex-method
Let be a polytope, , , and let be a -coherent -monotone path in . Then there is such that maximizes on and
i.e. the portion of from to is both -monotone and -monotone.
Lemma 2 is why a Shadow rule reaches an optimum: following the upper path of the shadow, it climbs in until the top.
Differences from the source:
- encoding: upper path: vertices of π(Q) on or above the line L through u⁰ and u¹ → upper boundary of π(Q): points of π(Q) highest above their first coordinate; reason: the same path for a polygon; it is also defined when vᵀx is constant on Q (L undefined)
- encoding: a path [x⁰, …, xᵏ] → a sequence x : ℕ → ℝⁿ with a length k; reason: only x 0, …, x k matter
Preamble
import Mathlib import Definitions.Def_ZeroOneSimplex_IsCoherentPath set_option autoImplicit false open Matrix
Formal statement
namespace ZeroOneSimplex
/-- **Lemma 2** (Black, De Loera, Kafer, Sanità, arXiv:2111.14050v1, pp.13–14). Consider the LP
`max {cᵀx : x ∈ Q}` for a polytope `Q`, let `v ≠ 0`, and let `x 0, …, x k` be a `c`-coherent
`v`-monotone path in `Q`. Then some `x i`, `0 ≤ i ≤ k`, maximizes `c` on `Q`, and the portion of
the path from `x 0` to `x i` is both `c`-monotone and `v`-monotone.
**Formalization Note.** Coherence uses the upper boundary of `π(Q)` for the paper's upper path
(see `upperBoundary`). -/
theorem lemma_2 {n : ℕ} (Q : Set (Fin n → ℝ)) (hQ : IsPolytope Q) (c v : Fin n → ℝ)
(hv : v ≠ 0) (x : ℕ → Fin n → ℝ) (k : ℕ) (hΓ : IsCoherentPath Q c v x k) :
∃ i ≤ k, IsMaximizer Q c (x i) ∧
∀ j < i, c ⬝ᵥ x j < c ⬝ᵥ x (j + 1) ∧ v ⬝ᵥ x j < v ⬝ᵥ x (j + 1) := by sorry
end ZeroOneSimplex
Source
Black, De Loera, Kafer, Sanità, On the Simplex method for 0/1 polytopes, arXiv:2111.14050v1, Lemma 2, pp.13–14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.