Proposition 2.1 — convex hull via LP min–max for integer objectives
ProvedChvatalPolytopes.Perfect.convexHull_iff_minmaxLet and be finite index sets, and (, ) real numbers, and consider the linear system
Let be a finite nonempty set of solutions of (2.1). Then the set of all solutions of (2.1) is the convex hull of if and only if, for every integer-valued vector ,
The proposition turns the polyhedral statement "(2.1) is a defining linear system of " into a family of min–max equalities, one for each integral objective. It is the bridge between Theorem 3.1(i) and the combinatorial condition used in its proof.
Formalization Note "min = max" is stated as two clauses: every feasible has , and some feasible attains equality. The hypothesis that is nonempty is added (the paper's requires it). The nonnegativity rows are kept, as a separate conjunct of the solution set; without them the statement is false. is a finite type and are real; ranges over .
import Mathlib
namespace ChvatalPolytopes.Perfect
/-- **Proposition 2.1** (Chvátal 1975, pp. 139–140). Let `S` be a finite set of solutions
`x = (x_u : u ∈ V)` of the system (2.1)
`−x_u ≤ 0 (u ∈ V)`, `Σ (a_{iu} x_u : u ∈ V) ≤ b_i (i ∈ J)`.
Then the set of all solutions of (2.1) is the convex hull of `S` if and only if, for every
integer-valued vector `c = (c_u : u ∈ V)`,
`max {cx : x ∈ S} = min {Σ (λ_i b_i : i ∈ J) : λ_i ≥ 0 for all i ∈ J and
Σ (λ_i a_{iu} : i ∈ J) ≥ c_u for all u ∈ V}`.
"min = max" is stated as: (a) every feasible `λ` has objective `≥ max_{x ∈ S} cx`, and (b) some
feasible `λ` has objective equal to it. The hypothesis `S.Nonempty` is added (the paper's
`max {cx : x ∈ S}` requires it). The nonnegativity rows `−x_u ≤ 0` are kept as the conjunct
`∀ u, 0 ≤ x u`; `J` is a finite index type and the coefficients `a`, `b` are real. -/
theorem convexHull_iff_minmax {V : Type*} [Fintype V] {J : Type*} [Fintype J]
(a : J → V → ℝ) (b : J → ℝ) (S : Finset (V → ℝ)) (hS : S.Nonempty)
(hSsol : ∀ x ∈ S, (∀ u, 0 ≤ x u) ∧ ∀ i, ∑ u, a i u * x u ≤ b i) :
{x : V → ℝ | (∀ u, 0 ≤ x u) ∧ ∀ i, ∑ u, a i u * x u ≤ b i} = convexHull ℝ (S : Set (V → ℝ)) ↔
∀ c : V → ℤ,
(∀ lam : J → ℝ, (∀ i, 0 ≤ lam i) → (∀ u, (c u : ℝ) ≤ ∑ i, lam i * a i u) →
S.sup' hS (fun x => ∑ u, (c u : ℝ) * x u) ≤ ∑ i, lam i * b i) ∧
(∃ lam : J → ℝ, (∀ i, 0 ≤ lam i) ∧ (∀ u, (c u : ℝ) ≤ ∑ i, lam i * a i u) ∧
∑ i, lam i * b i = S.sup' hS (fun x => ∑ u, (c u : ℝ) * x u)) := by sorry
end ChvatalPolytopes.Perfect
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Data and hypotheses.
- and are finite index sets.
- is a real matrix and is a real vector.
- is a nonempty finite set of vectors.
- Every solves the system
Let be the set of all real solutions of this system.
Claim. if and only if the following holds for every integer vector . Write
which is a genuine maximum because is finite and nonempty. Call dual feasible if
Then both of the following must hold:
- (a) every dual-feasible satisfies ;
- (b) some dual-feasible satisfies .
Degenerate cases.
- The maximum involves no default values, because is required to be nonempty.
- If is empty, is the nonnegative orthant. Dual feasibility then reduces to for all , with dual objective . For any with a positive entry, no dual-feasible exists and (b) fails.
- If is empty, is a single point and is that point. is the empty vector, , and is dual feasible with objective .
- The statement quantifies only over integer , not real .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.