Theorem 7.14 -- the L-optimality criterion
ProvedDiscreteConvex.LConvexFunctions.l_optimality_criterioncombinatoricsdiscrete-convex-analysis
Theorem 7.14 (p.185). (1) For an L-convex function and , for all if and only if both for all and . (2) For an L-convex function and , global optimality is equivalent to for all . Part (1)'s extra periodicity condition is a genuine, load-bearing hypothesis of the plain L-convex case, not a technical footnote — it is exactly what is not needed in the L-convex case, since that normalization is built into the class differently.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.185, Theorem 7.14.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexFunctions_SBF import Definitions.Def_DiscreteConvex_LConvexFunctions_TRF import Definitions.Def_DiscreteConvex_LConvexFunctions_LNaturalConvex import Definitions.Def_DiscreteConvex_LConvexFunctions_DomZ import Definitions.Def_DiscreteConvex_LConvexFunctions_IndicatorVec
Formal statement
namespace DiscreteConvex.LConvexFunctions
/-- Theorem 7.14, the L-optimality criterion (Murota, *Discrete Convex Analysis*, SIAM 2003,
p.185). (1) For an L-convex function `g` and `p ∈ dom g`, `g(p) ≤ g(q)` for all `q ∈ Zⱽ` iff
both `g(p) ≤ g(p + χ_Y)` for all `Y ⊆ V` and `g(p) = g(p + 1)`. (2) For an L♮-convex function
`g` and `p ∈ dom g`, `g(p) ≤ g(q)` for all `q ∈ Zⱽ` iff `g(p) ≤ g(p ± χ_Y)` for all `Y ⊆ V`. -/
theorem l_optimality_criterion {V : Type*} [Fintype V] [DecidableEq V] :
(∀ g : (V → ℤ) → WithTop ℝ, SBF g → TRF g → ∀ p ∈ DomZ g,
(∀ q, g p ≤ g q) ↔
((∀ Y : Finset V, g p ≤ g (fun v => p v + IndicatorVec Y v)) ∧
g p = g (fun v => p v + 1))) ∧
(∀ g : (V → ℤ) → WithTop ℝ, LNaturalConvex g → ∀ p ∈ DomZ g,
(∀ q, g p ≤ g q) ↔
(∀ Y : Finset V, g p ≤ g (fun v => p v + IndicatorVec Y v) ∧
g p ≤ g (fun v => p v - IndicatorVec Y v))) := by sorry
end DiscreteConvex.LConvexFunctions
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.185, Theorem 7.14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.