Proposition 6.62 -- dir_deriv_eq_finite_diff_on_integral_mconvex
DisprovedDiscreteConvex.MConvexFunctionsE.dir_deriv_eq_finite_diff_on_integral_mconvexconvex-optimizationdiscrete-convex-analysis
Proposition 6.62 (p.167). For and , we have for .
This shows the two halves of Theorem 6.61 (formalized in mission 24-ch06d-mconvexfunctions) are consistent with each other: the real-variable directional derivative and the integer-variable finite difference agree exactly at the integer points where both are defined.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.167, Proposition 6.62.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_MConvexFunctionsE_CharVec import Definitions.Def_DiscreteConvex_MConvexFunctionsE_DomR import Definitions.Def_DiscreteConvex_MConvexFunctionsE_DirDeriv import Definitions.Def_DiscreteConvex_MConvexFunctionsE_MConvexIntegralR
Formal statement
namespace DiscreteConvex.MConvexFunctionsE
open Classical
open scoped Pointwise
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Proposition 6.62 (p.167). Consistency of the directional derivative with the finite
difference on `M[Z|R→R]` at an integer point. -/
theorem dir_deriv_eq_finite_diff_on_integral_mconvex (f : (V → ℝ) → WithTop ℝ)
(hf : MConvexIntegralR f) (x : V → ℝ) (hx : x ∈ DomR f)
(hxZ : ∀ v, ∃ k : ℤ, x v = (k : ℝ)) (u v : V) :
DirDeriv f x (fun w => (CharVec v w - CharVec u w : ℝ)) =
f (fun w => x w - (CharVec u w : ℝ) + (CharVec v w : ℝ)) - f x := by sorry
end DiscreteConvex.MConvexFunctionsE
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.167, Proposition 6.62
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.