Theorem 7.53 -- the quasi L-optimality criterion
ProvedDiscreteConvex.LConvexFunctions.Quasi.quasi_l_optimality_criterioncombinatoricsdiscrete-convex-analysis
Theorem 7.53 (p.201). Assume satisfies for all . (1) For satisfying (QSBw) and : is the unique minimizer up to translation by ( for every with not a multiple of ) if and only if for every proper nonempty . (2) For satisfying (SSQSBw) and , global optimality is equivalent to for all . The direct analogue of chunk 08's Theorem 7.14 for the quasi-submodularity classes.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.201, Theorem 7.53.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexFunctions_DomZ import Definitions.Def_DiscreteConvex_LConvexFunctions_IndicatorVec import Definitions.Def_DiscreteConvex_LConvexFunctions_Quasi_QSBw import Definitions.Def_DiscreteConvex_LConvexFunctions_Quasi_SSQSBw
Formal statement
open DiscreteConvex.LConvexFunctions
namespace DiscreteConvex.LConvexFunctions.Quasi
/-- Theorem 7.53, the quasi L-optimality criterion (Murota, *Discrete Convex Analysis*, SIAM
2003, p.201). Assume `g : Zⱽ → R ∪ {+∞}` satisfies `g(p) = g(p+1)` for all `p`. (1) For `g`
satisfying (QSBw) and `p ∈ dom g`: `g(p) < g(q)` for every `q` with `q - p` not a multiple of
`1` iff `g(p) < g(p + χ_X)` for every `X ⊆ V` with `X ∉ {∅, V}`. (2) For `g` satisfying
(SSQSBw) and `p ∈ dom g`: `g(p) ≤ g(q)` for all `q` iff `g(p) ≤ g(p + χ_X)` for all `X ⊆ V`. -/
theorem quasi_l_optimality_criterion {V : Type*} [Fintype V] [DecidableEq V] :
(∀ g : (V → ℤ) → WithTop ℝ, (∀ p : V → ℤ, g (p + 1) = g p) → QSBw g → ∀ p ∈ DomZ g,
(∀ q : V → ℤ, (¬ ∃ k : ℤ, q = fun v => p v + k) → g p < g q) ↔
(∀ X : Finset V, X ≠ ∅ → X ≠ Finset.univ →
g p < g (fun v => p v + IndicatorVec X v))) ∧
(∀ g : (V → ℤ) → WithTop ℝ, (∀ p : V → ℤ, g (p + 1) = g p) → SSQSBw g → ∀ p ∈ DomZ g,
(∀ q, g p ≤ g q) ↔ (∀ X : Finset V, g p ≤ g (fun v => p v + IndicatorVec X v))) := by sorry
end DiscreteConvex.LConvexFunctions.Quasi
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.201, Theorem 7.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.