Theorem 6.49 -- polyhedral_mconvex_operations
ProvedDiscreteConvex.MConvexFunctionsD.polyhedral_mconvex_operationsconvex-optimizationdiscrete-convex-analysis
Theorem 6.49 (p.162-163), operations (1)-(4). Let be polyhedral M-convex. (1) is polyhedral M-convex for . (2) is polyhedral M-convex in , for , . (3) is polyhedral M-convex for . (4) The separable perturbation is polyhedral M-convex, for convex univariate , provided its domain is nonempty.
Formalization Note. Parts (5)-(8) (real-interval restriction, restriction to , aggregation, infimal convolution) are not restated here — the same scope decision as chunk 22-ch06b-mconvexfunctions's Theorem 6.13, see MODERATION_NOTES.md.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.162-163, Theorem 6.49.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_MConvexFunctionsD_DomR import Definitions.Def_DiscreteConvex_MConvexFunctionsD_MExchangeAxiomR import Definitions.Def_DiscreteConvex_MConvexFunctionsD_PosScalarMul import Definitions.Def_DiscreteConvex_MConvexFunctionsD_LinearWeightR import Definitions.Def_DiscreteConvex_MConvexFunctionsD_IsConvexUniv import Definitions.Def_DiscreteConvex_MConvexFunctionsD_SeparablePerturbR
Formal statement
namespace DiscreteConvex.MConvexFunctionsD
open scoped Pointwise
open Classical
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Theorem 6.49 (p.181-182), operations (1)-(4); (5)-(8) are not restated here (see
`MODERATION_NOTES.md`, the same scope decision as chunk `22-ch06b-mconvexfunctions`'s Theorem
6.13). -/
theorem polyhedral_mconvex_operations (f : (V → ℝ) → WithTop ℝ) (hf : MExchangeAxiomR f) :
(∀ lam : ℝ, 0 < lam → MExchangeAxiomR (fun x => PosScalarMul lam (f x))) ∧
(∀ (a : V → ℝ) (beta : ℝ), beta ≠ 0 → MExchangeAxiomR (fun x => f (fun v => a v + beta * x v))) ∧
(∀ p : V → ℝ, MExchangeAxiomR (LinearWeightR f p)) ∧
(∀ phi : V → ℝ → WithTop ℝ, (∀ v, IsConvexUniv (phi v)) →
(DomR (SeparablePerturbR f phi)).Nonempty → MExchangeAxiomR (SeparablePerturbR f phi)) := by sorry
end DiscreteConvex.MConvexFunctionsD
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.162-163, Theorem 6.49
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.