Proposition 7.34 -- polyhedral_lconvex_argmin_is_lconvex_polyhedron
ProvedDiscreteConvex.LConvexFunctionsC.polyhedral_lconvex_argmin_is_lconvex_polyhedrondiscrete-convex-analysisdiscrete-geometry
Proposition 7.34 (p.193). Let be a polyhedral L-convex function. For any , is an L-convex polyhedron if it is not empty.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.193, Proposition 7.34.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexFunctionsC_SBFR import Definitions.Def_DiscreteConvex_LConvexFunctionsC_TRFR import Definitions.Def_DiscreteConvex_LConvexFunctionsC_LConvexPolyhedronR import Definitions.Def_DiscreteConvex_LConvexFunctionsC_IsPolyhedralConvex import Definitions.Def_DiscreteConvex_LConvexFunctionsC_ArgMinR import Definitions.Def_DiscreteConvex_LConvexFunctionsC_LinearWeightR
Formal statement
namespace DiscreteConvex.LConvexFunctionsC
open Classical
open scoped Pointwise
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Proposition 7.34 (p.193). The minimizer set of a linearly-perturbed polyhedral L-convex
function is an L-convex polyhedron of the class `L⁰[R]`, if nonempty. The class is the real one,
not the integral hull class `L⁰[Z|R]`: for `g(p) = max(p₁ - p₂ - 1/2, 0)` and `x = 0` the
minimizer set is `{p : p₁ - p₂ ≤ 1/2}`, which is the convex hull of no integer set. -/
theorem polyhedral_lconvex_argmin_is_lconvex_polyhedron (g : (V → ℝ) → WithTop ℝ)
(hg : SBFR g ∧ TRFR g) (hpoly : IsPolyhedralConvex g) (x : V → ℝ)
(hne : (ArgMinR (LinearWeightR g (fun v => - x v))).Nonempty) :
LConvexPolyhedronR (ArgMinR (LinearWeightR g (fun v => - x v))) := by sorry
end DiscreteConvex.LConvexFunctionsC
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.193, Proposition 7.34
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.