Theorem 2.3 (Fujishige): the minimum-norm point solves SFM
ProvedGeomRescale.theorem_2_3combinatorial-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm
Let be submodular with . The problem
has a unique optimal solution . The set is the inclusionwise minimal minimizer of , , and .
Lemma 3.8 uses this result to turn integrality of into a lower bound on the width of .
Differences from the source:
- encoding: the unique optimal solution; the inclusionwise minimal minimizer →
∃!and a universally quantified ; is a minimizer contained in every minimizer; reason: minimizers of a submodular function form a lattice, so the minimal one is the least
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Alg_Setting import Definitions.Def_GeomRescale_norm2 import Definitions.Def_GeomRescale_IsMinNormPoint open NonmonotoneSubmod.Shared open SchrijverSFM.Alg
Formal statement
namespace GeomRescale
/-- Theorem 2.3, Fujishige (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Theorem 2.3, p.5): problem (6) has a unique optimal solution `z`.
The set `S* = {v ∈ V : z(v) < 0}` is the inclusionwise minimal minimizer of `f`, `f(S*) = z⁻(V)`,
and `|f(S*)| ≤ √n ‖z‖₂`.
**Formalization Note.** "Inclusionwise minimal minimizer" is: `S*` is a minimizer and is contained in
every minimizer. `z⁻(V) = ∑_v min {0, z(v)}`. The paper cites this result and does not prove it. -/
theorem theorem_2_3 {n : ℕ} (f : Finset (Fin n) → ℝ) (hsub : Submodular f) (hf0 : f ∅ = 0) :
(∃! z, IsMinNormPoint f z) ∧
∀ z, IsMinNormPoint f z →
let Sstar : Finset (Fin n) := Finset.univ.filter (fun v => z v < 0)
(∀ T, f Sstar ≤ f T) ∧
(∀ T, (∀ U, f T ≤ f U) → Sstar ⊆ T) ∧
f Sstar = ∑ v, min 0 (z v) ∧
|f Sstar| ≤ √(n : ℝ) * norm2 z := by sorry
end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Theorem 2.3, p.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.