Lemma 2(iii), p. 17 — the Lovász extension of a submodular function is convex on [0,1]^d
ProvedGradDOvS.Submod.lemma_2_iiiconvexitylovasz-extensionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-function
Let be submodular: for all . Then its Lovász extension of (2) is convex on the box:
This is the classical theorem of Lovász (1983). It turns stochastic submodular minimization into a convex problem on , to which (stochastic) subgradient methods apply. A version for Murota's encoding of the Lovász extension (values in , normalised by , on all of ) is proved on the platform as DiscreteConvex.MConvexSetsB.lovasz_convex_iff_submodular (Murota, Theorem 4.16); the object here is a different encoding, so that result is cited, not reused.
Formalization Note Of Assumptions 1–4 only submodularity (Assumption 2 on ) is needed and kept.
Preamble
import Mathlib import Definitions.Def_GradDOvS_Submod_Model open MeasureTheory ProbabilityTheory
Formal statement
namespace GradDOvS.Submod
/-- Lemma 2(iii), p. 17: for submodular `f`, the Lovász extension is convex on `[0,1]^d`. -/
theorem lemma_2_iii {d : ℕ} (f : Finset (Fin d) → ℝ) (hf : NonmonotoneSubmod.Shared.Submodular f) :
ConvexOn ℝ (box d) (lovasz f) := by sorry
end GradDOvS.Submod
Source
Zhang, Zheng & Lavaei, arXiv:2010.16250v3, p. 17, Lemma 2(iii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.