Theorem 7.46 -- integral_lconvex_iff_integral_argmin
DisprovedDiscreteConvex.LConvexFunctionsD.integral_lconvex_iff_integral_argminconvex-optimizationdiscrete-convex-analysisdiscrete-geometry
Theorem 7.46 (p.198). For a polyhedral convex function with : iff for every with nonempty. The integral refinement of Theorem 7.45's (a) (d).
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.198, Theorem 7.46.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexFunctionsD_DomR import Definitions.Def_DiscreteConvex_LConvexFunctionsD_IsIntegralPolyhedron import Definitions.Def_DiscreteConvex_LConvexFunctionsD_LinearWeightR import Definitions.Def_DiscreteConvex_LConvexFunctionsD_ArgMinR import Definitions.Def_DiscreteConvex_LConvexFunctionsD_LConvexIntegralR import Definitions.Def_DiscreteConvex_LConvexFunctionsD_LConvexPolyhedron
Formal statement
namespace DiscreteConvex.LConvexFunctionsD
open Classical
open scoped Pointwise
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Theorem 7.46 (p.198). The integral refinement of Theorem 7.45's (a) ⇔ (d). -/
theorem integral_lconvex_iff_integral_argmin (g : (V → ℝ) → WithTop ℝ) (hdom : (DomR g).Nonempty) :
LConvexIntegralR g ↔
∀ x : V → ℝ, (ArgMinR (LinearWeightR g (fun v => - x v))).Nonempty →
(LConvexPolyhedron (ArgMinR (LinearWeightR g (fun v => - x v))) ∧
IsIntegralPolyhedron (ArgMinR (LinearWeightR g (fun v => - x v)))) := by sorry
end DiscreteConvex.LConvexFunctionsD
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.198, Theorem 7.46
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.