Lemma 3.11:
ProvedGeomRescale.lemma_3_11combinatorial-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm
Throughout Algorithm Rescaling-SFM, holds for every , and also for every .
This links the geometry of to the condition number.
Differences from the source:
- generalization: → both and ; reason: the printed proof reads the definition of on and Theorem 3.6 applies it there; both forms are true
- reading: as a minimum →
sInf, which is if ; reason: may be empty or not closed here - encoding: throughout the algorithm / at every stage → every state reachable from the initial state, for as in the goal; reason: a run is a relation, so this covers all tie-breaks and argmins; the placeholder of the state before lines 2–3 is included, and the statement holds there too
- encoding: a ground set with elements →
1 ≤ n; reason: the parameter of Algorithm 2 is undefined at ; the hypothesis excludes only that case - generalization: the run of Algorithm 2 with → the runs for every , with ; reason: gives the paper's run, with rounded as in Theorem 3.6; the statement holds on every such run
- reading: with no case for → at in the step relation; reason: occurs (for at line 2 of Algorithm 1), and the run needs a value there
- reading: in (10) and in line 8 of Algorithm 2, returned after line 15 of Algorithm 1 incremented → , the bases the call computed; reason: line 15 has incremented , so no was computed
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Alg_Setting import Definitions.Def_GeomRescale_fR import Definitions.Def_GeomRescale_enlarge import Definitions.Def_GeomRescale_norm2 import Definitions.Def_GeomRescale_qnorm import Definitions.Def_GeomRescale_Ltwo import Definitions.Def_GeomRescale_Reachable import Definitions.Def_GeomRescale_omega open NonmonotoneSubmod.Shared open SchrijverSFM.Alg
Formal statement
namespace GeomRescale
/-- Lemma 3.11 (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.11, p.12): throughout Algorithm Rescaling-SFM,
`‖x‖_Q ≥ ω_μ ‖x‖₂` for every `x ∈ B(f) ∖ {0}`, and also for every `x ∈ B(f_μ) ∖ {0}`.
**Formalization Note.** The page prints `B(f)`, but its proof closes "from the definition of `ω_μ`",
which ranges over `B(f_μ)`, and the proof of Theorem 3.6 applies the lemma to `g_h ∈ B(f_μ)`. Both
forms are true and both are stated. -/
theorem lemma_3_11 {n : ℕ} (hn : 1 ≤ n) (f : Finset (Fin n) → ℤ) (hsub : Submodular (fR f))
(hf0 : f ∅ = 0) (Λ : ℝ) (hΛ : Ltwo (fR f) ≤ Λ) (s : St n) (hs : Reachable f Λ s) :
(∀ x ∈ baseB (fR f) \ {0},
omega (fR f) (s.vn.μ : ℝ) * norm2 x ≤ qnorm s.Q x) ∧
∀ x ∈ baseB (enlarge (fR f) (s.vn.μ : ℝ)) \ {0},
omega (fR f) (s.vn.μ : ℝ) * norm2 x ≤ qnorm s.Q x := by sorry
end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.11, p.12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.