Theorem 8.43 -- l2_optimality_criterion
ProvedDiscreteConvex.ConjugacyDualityC.l2_optimality_criterioncombinatoricsdiscrete-convex-analysis
Theorem 8.43 (L2-optimality criterion; p.232). For an L2-convex function and : globally minimizes iff for all and .
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.232, Theorem 8.43.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_ConjugacyDualityC_IndicatorVec import Definitions.Def_DiscreteConvex_ConjugacyDualityC_DomZ import Definitions.Def_DiscreteConvex_ConjugacyDualityC_L2Convex
Formal statement
namespace DiscreteConvex.ConjugacyDualityC
open Classical
open scoped Pointwise
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Theorem 8.43 (L2-optimality criterion; p.232). Global optimality of an L2-convex function is
characterized by local non-improvement plus periodicity. -/
theorem l2_optimality_criterion (g : (V → ℤ) → WithTop ℝ) (hg : L2Convex g) (p : V → ℤ)
(hp : p ∈ DomZ g) :
(∀ q, g p ≤ g q) ↔
((∀ Y : Finset V, g p ≤ g (fun v => p v + IndicatorVec Y v)) ∧ g p = g (p + 1)) := by sorry
end DiscreteConvex.ConjugacyDualityC
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.232, Theorem 8.43
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.