Theorem 2.1, p. 3 — Balas's sequential convexification theorem
ProvedBinaryExtForm.HypercubeRank.theorem_2_1lift-and-projectp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polytopessequential-convexification
Let be a polytope and let be a set of coordinates such that for every and every (the paper's with ). For a coordinate write . If lists every index of exactly once, then
Convexifying the 0/1 variables one at a time, each exactly once and in any order, produces the 0/1 hull. In particular , so the lift-and-project rank is a genuine minimum.
Formalization Note. The paper convexifies in this order; the statement here allows any set of 0/1 coordinates and any duplicate-free enumeration l of it (l.Nodup, l.toFinset = H). This matches the paper's remark on p. 3 that the order is irrelevant. IteratedSplit Q l applies the convexification steps left to right.
Preamble
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model open Disjunctive.HigherDim
Formal statement
namespace BinaryExtForm.HypercubeRank
theorem theorem_2_1 {n : ℕ} (Q : Set (Fin n → ℝ)) (H : Finset (Fin n)) (hQ : IsPolytope Q)
(hQH : ∀ p ∈ Q, ∀ i ∈ H, 0 ≤ p i ∧ p i ≤ 1) (l : List (Fin n)) (hl : l.Nodup)
(hlH : l.toFinset = H) :
IteratedSplit Q l = intHull Q H := by sorry
end BinaryExtForm.HypercubeRank
Source
Aprile, Conforti, Di Summa, Binary extended formulations and sequential convexification, arXiv:2106.00354v1, p. 3, Theorem 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.