Theorem 7.54 -- the quasi L-proximity theorem
ProvedDiscreteConvex.LConvexFunctions.Quasi.quasi_l_proximity_theoremcombinatoricsconvex-optimizationdiscrete-convex-analysisdiscrete-geometry
Theorem 7.54 (p.201). Let satisfy (SSQSB) and for all , and assume and . If satisfies for all , then and there is with the componentwise bound — verbatim the same conclusion, and the same exact bound, as chunk 08's Theorem 7.18(1), now established for the strictly larger class of functions satisfying (SSQSB) rather than (SBF[Z]). This genuinely broadens the class covered by an explicit proximity guarantee to include every strictly increasing rescaling of an L-convex objective (Example 7.48), a class the plain L-convex theory of chunk 08 says nothing about.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.201, Theorem 7.54.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexFunctions_DomZ import Definitions.Def_DiscreteConvex_LConvexFunctions_ArgMin import Definitions.Def_DiscreteConvex_LConvexFunctions_IndicatorVec import Definitions.Def_DiscreteConvex_LConvexFunctions_Quasi_SSQSB
Formal statement
open DiscreteConvex.LConvexFunctions
namespace DiscreteConvex.LConvexFunctions.Quasi
/-- Theorem 7.54, the quasi L-proximity theorem (Murota, *Discrete Convex Analysis*, SIAM 2003,
p.201). Let `g : Zⱽ → R ∪ {+∞}` satisfy (SSQSB) and `g(p) = g(p+1)` for all `p`, and assume
`n = |V|` and `α ∈ Z++`. If `pα ∈ dom g` satisfies `g(pα) ≤ g(pα + αχ_Y)` for all `Y ⊆ V`, then
`arg min g ≠ ∅` and there exists `p* ∈ arg min g` with `pα ≤ p* ≤ pα + (n-1)(α-1)·1`
(componentwise) — the same conclusion as Theorem 7.18(1) (chunk `08-lconvex-functions-i`), for
the strictly larger class of functions satisfying (SSQSB) rather than (SBF[Z]). -/
theorem quasi_l_proximity_theorem {V : Type*} [Fintype V] [DecidableEq V] (α : ℤ) (hα : 0 < α)
(g : (V → ℤ) → WithTop ℝ) (hper : ∀ p : V → ℤ, g (fun v => p v + 1) = g p)
(hg : SSQSB g) (pα : V → ℤ) (hpα : pα ∈ DomZ g)
(hloc : ∀ Y : Finset V, g pα ≤ g (fun v => pα v + α * IndicatorVec Y v)) :
(ArgMin g).Nonempty ∧ ∃ p ∈ ArgMin g, ∀ v : V,
pα v ≤ p v ∧ p v ≤ pα v + ((Fintype.card V : ℤ) - 1) * (α - 1) := by sorry
end DiscreteConvex.LConvexFunctions.Quasi
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.201, Theorem 7.54
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.