Theorem 7.11 -- lnat_convex_operations_and_restrictions
DisprovedDiscreteConvex.LConvexFunctionsB.lnat_convex_operations_and_restrictionsconvex-optimizationdiscrete-convex-analysis
Theorem 7.11 (p.184). Let be L-convex functions. (1) Operations (1)-(6) of Theorem 7.10 are valid for L-convex functions. (2) The restriction to the integer interval is L-convex provided its domain is nonempty. (3) The restriction to is L-convex provided its domain is nonempty.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.184, Theorem 7.11.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexFunctionsB_DomZ import Definitions.Def_DiscreteConvex_LConvexFunctionsB_LNaturalConvex import Definitions.Def_DiscreteConvex_LConvexFunctionsB_PosScalarMul import Definitions.Def_DiscreteConvex_LConvexFunctionsB_LinearWeight import Definitions.Def_DiscreteConvex_LConvexFunctionsB_ProjectionZ import Definitions.Def_DiscreteConvex_LConvexFunctionsB_SeparablePerturbZ import Definitions.Def_DiscreteConvex_LConvexFunctionsB_IntervalRestrict import Definitions.Def_DiscreteConvex_LConvexFunctionsB_Restriction
Formal statement
namespace DiscreteConvex.LConvexFunctionsB
open Classical
open scoped Pointwise
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Theorem 7.11 (p.184). The six operations of Theorem 7.10 are valid for L♮-convex functions,
which additionally admit restriction to an integer interval and restriction to `U ⊆ V`. -/
theorem lnat_convex_operations_and_restrictions (g g1 g2 : (V → ℤ) → WithTop ℝ)
(hg : LNaturalConvex g) (hg1 : LNaturalConvex g1) (hg2 : LNaturalConvex g2) :
((∀ lam : ℝ, 0 < lam → LNaturalConvex (fun p => PosScalarMul lam (g p))) ∧
(∀ a : V → ℤ, ∀ beta : ℤ, beta ≠ 0 →
LNaturalConvex (fun p => g (fun v => a v + beta * p v))) ∧
(∀ x : V → ℝ, LNaturalConvex (LinearWeight g (fun v => - x v))) ∧
(∀ U : Set V, (DomZ (ProjectionZ g U)).Nonempty → LNaturalConvex (ProjectionZ g U)) ∧
(∀ psi : V → ℤ → WithTop ℝ, (DomZ (SeparablePerturbZ g psi)).Nonempty →
LNaturalConvex (SeparablePerturbZ g psi)) ∧
((DomZ (fun p => g1 p + g2 p)).Nonempty → LNaturalConvex (fun p => g1 p + g2 p))) ∧
(∀ a b : V → WithBot (WithTop ℤ), (DomZ (IntervalRestrict g a b)).Nonempty →
LNaturalConvex (IntervalRestrict g a b)) ∧
(∀ U : Finset V, (DomZ (Restriction g U)).Nonempty → LNaturalConvex (Restriction g U)) := by sorry
end DiscreteConvex.LConvexFunctionsB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.184, Theorem 7.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.