Theorem 5.2 — a convex scenario program has at most support constraints
ProvedScenarioApproach.Generalization.card_support_constraints_le_dimLet and every constraint set , , be convex, and let . Fix any and any sample , and let be a solution of the scenario program
Then the number of support constraints of this program (constraints whose removal allows a feasible point of strictly smaller cost than ) is at most :
The statement is deterministic: it holds for every sample, with no probability involved. It is the combinatorial fact on which the generalization theory of convex scenario programs rests, since the number of scenarios that determine the solution is bounded by the number of decision variables rather than by the number of scenarios.
Formalization Note The book states the result for in Theorem 5.2 and for general in its footnote 15; the general form is stated here. Only convexity of and of the is assumed (closedness and uniqueness of the solution, which are in force in the chapter, are not needed for this statement). The sample is ω : Fin m → Δ.
import Mathlib import Definitions.Def_ScenarioApproach_Generalization_scenarioProgram import Definitions.Def_ScenarioApproach_Generalization_supportConstraint
namespace ScenarioApproach.Generalization
/-- Theorem 5.2 with footnote 15 (p. 57): if `Θ` and every `Θ_δ` are convex, then for every
`m` and every sample `ω : Fin m → Δ`, the scenario program with these `m` constraints has at most
`d` support constraints at any of its solutions. -/
theorem card_support_constraints_le_dim {d m : ℕ} {Δ : Type*}
(c : EuclideanSpace ℝ (Fin d)) (Θ : Set (EuclideanSpace ℝ (Fin d)))
(Θδ : Δ → Set (EuclideanSpace ℝ (Fin d)))
(hΘ_convex : Convex ℝ Θ) (hΘδ_convex : ∀ δ, Convex ℝ (Θδ δ))
(ω : Fin m → Δ) (θstar : EuclideanSpace ℝ (Fin d)) (hθstar : IsSolution c Θ Θδ ω θstar) :
numSupportConstraints c Θ Θδ ω θstar ≤ d := by sorry
end ScenarioApproach.Generalization
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.