Proposition 8.14 -- mnat_lnat_ineq_extends_to_reals
ProvedDiscreteConvex.ConjugacyDualityB.mnat_lnat_ineq_extends_to_realsconvex-optimizationdiscrete-convex-analysis
Proposition 8.14 (p.217). (1) If , for all implies for all . (2) The L analogue.
Formalization Note. The inequality (with concave, possibly -valued) is restated as where is the M-convex function the book itself hypothesizes, avoiding any need for WithTop ℝ negation or an EReal-valued codomain.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.217, Proposition 8.14.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_ConjugacyDualityB_MNaturalConvex import Definitions.Def_DiscreteConvex_ConjugacyDualityB_LNaturalConvex import Definitions.Def_DiscreteConvex_ConjugacyDualityB_ConvexClosureVal
Formal statement
namespace DiscreteConvex.ConjugacyDualityB
open Classical
open scoped Pointwise
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Proposition 8.14 (p.217). An inequality between M♮-(resp. L♮-)convex functions on the
integer lattice extends to the real domain via convex/concave closure. -/
theorem mnat_lnat_ineq_extends_to_reals :
(∀ f h2 : (V → ℤ) → WithTop ℝ, MNaturalConvex f → MNaturalConvex h2 →
(∀ x : V → ℤ, f x + h2 x ≥ 0) →
∀ x : V → ℝ, ConvexClosureVal f x + ConvexClosureVal h2 x ≥ 0) ∧
(∀ g k2 : (V → ℤ) → WithTop ℝ, LNaturalConvex g → LNaturalConvex k2 →
(∀ p : V → ℤ, g p + k2 p ≥ 0) →
∀ p : V → ℝ, ConvexClosureVal g p + ConvexClosureVal k2 p ≥ 0) := by sorry
end DiscreteConvex.ConjugacyDualityB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.217, Proposition 8.14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.