Proposition 7.41 -- pos_homog_iff_argmin_l0
DisprovedDiscreteConvex.LConvexFunctionsD.pos_homog_iff_argmin_l0convex-optimizationdiscrete-convex-analysisdiscrete-geometry
Proposition 7.41 (p.195). For a positively homogeneous polyhedral convex function with : iff for every with nonempty.
Formalization Note. "" is replaced by the equivalent (ArgMinR ...).Nonempty hypothesis, matching mission 25-ch06e-mconvexfunctions's identical substitution.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.195, Proposition 7.41.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_LConvexFunctionsD_PosHomogeneous import Definitions.Def_DiscreteConvex_LConvexFunctionsD_DomR import Definitions.Def_DiscreteConvex_LConvexFunctionsD_ZeroLR import Definitions.Def_DiscreteConvex_LConvexFunctionsD_LinearWeightR import Definitions.Def_DiscreteConvex_LConvexFunctionsD_ArgMinR import Definitions.Def_DiscreteConvex_LConvexFunctionsD_LConvexPolyhedron
Formal statement
namespace DiscreteConvex.LConvexFunctionsD
open Classical
open scoped Pointwise
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- Proposition 7.41 (p.195). A positively homogeneous polyhedral convex function is `0L[R→R]`
iff its weighted minimizer sets are always L-convex polyhedra. -/
theorem pos_homog_iff_argmin_l0 (g : (V → ℝ) → WithTop ℝ) (hpos : PosHomogeneous g)
(hdom : (DomR g).Nonempty) :
ZeroLR g ↔ ∀ x : V → ℝ, (ArgMinR (LinearWeightR g (fun v => - x v))).Nonempty →
LConvexPolyhedron (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.195, Proposition 7.41
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.