Lemma 6.11, p. 29 — f_c convex, g_c and w_c concave as extended-real functions of z, and sup of w_c over integer points of I_ℤ is finite iff over I_ℤ
ProvedMICPRep.Periodic.lemma_6_11convex-analysismixed-integer-convex-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1support-function
Let be closed and convex, inducing an MICP formulation with index set and -projected sets . For define by
Then is convex and , are concave on , and for all : , , . If, in addition, has an integer point in its relative interior, then for every
The width functions measure the extent of the -projected sets in direction ; (6.25) transfers finiteness of the MICP diameter from integer to all points of .
Formalization Note Values are in EReal; may be and may be at non-integer (the paper's Example 6.1). Convexity is the explicit inequality for in EReal (where , so the endpoints are identities), and the reverse inequality for concavity. never meets on .
Preamble
import Mathlib import Definitions.Def_MICPRep_Periodic_Setting
Formal statement
namespace MICPRep.Periodic
open scoped ENNReal Matrix
/-- Lemma 6.11, p. 29. -/
theorem lemma_6_11 {n p d : ℕ} (M : Set (Ambient n p d)) (S : Set (Pt n))
(hM : Induces M S) :
let I := indexSet M
let f : Pt n → (Fin d → ℝ) → EReal := fun c z => -supportFn (zProj M z) (-c)
let g : Pt n → (Fin d → ℝ) → EReal := fun c z => supportFn (zProj M z) c
let w : Pt n → (Fin d → ℝ) → EReal := fun c z => g c z - f c z
(∀ c : Pt n, ∀ z₁ ∈ I, ∀ z₂ ∈ I, ∀ t : ℝ, 0 ≤ t → t ≤ 1 →
f c (t • z₁ + (1 - t) • z₂) ≤ (t : EReal) * f c z₁ + ((1 - t : ℝ) : EReal) * f c z₂ ∧
(t : EReal) * g c z₁ + ((1 - t : ℝ) : EReal) * g c z₂ ≤ g c (t • z₁ + (1 - t) • z₂) ∧
(t : EReal) * w c z₁ + ((1 - t : ℝ) : EReal) * w c z₂ ≤ w c (t • z₁ + (1 - t) • z₂)) ∧
(∀ c : Pt n, ∀ z ∈ I, f c z < ⊤ ∧ ⊥ < g c z ∧ 0 ≤ w c z) ∧
((intrinsicInterior ℝ (IZ I) ∩ intLattice d).Nonempty →
∀ c : Pt n, ((⨆ z ∈ IZ I ∩ intLattice d, w c z) < ⊤ ↔ (⨆ z ∈ IZ I, w c z) < ⊤)) := by sorry
end MICPRep.Periodic
Source
Lubin, Vielma, Zadik, Mixed-integer convex representability, arXiv:1706.05135v3, p. 29, Lemma 6.11 and (6.25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.