Proof of Theorem 4, p. 13 — x⋆ = max{Σᵢ max{ξᵢ, 1 − ξᵢ} : Aξ ≤ b} is the unique optimal decision of (11)
ProvedSPHardness.IntFeas.xStar_optimalLet be an instance of the Integer Feasibility Problem, so , and assume the polytope is nonempty. Let
Then
- a decision is feasible for problem (11) if and only if ;
- attains the optimal value: ;
- is the only feasible decision attaining .
The optimal decision of the stochastic program thus encodes the largest value of a separable function over the IFP polytope, which is how the program carries the combinatorial information of the instance.
Formalization Note. Feasibility of in (11) is robust: the second stage must be feasible for every . Under an almost-sure reading of feasibility the statement fails when the polytope is Lebesgue-null (every would then be feasible), so the robust reading is the one under which the page's claim holds. The page's is read as . The nonemptiness of the polytope is the page's own assumption ("Assuming that ").
import Mathlib import Definitions.Def_SPHardness_IntFeas_Model open MeasureTheory
namespace SPHardness.IntFeas
theorem xStar_optimal {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℤ) (b : Fin m → ℤ)
(hinst : IsIFPInstance A b) (hne : ∃ ξ : Fin n → ℝ, InPolytope A b ξ) :
(∀ x, FirstStageFeasible A b x ↔ xStar A b ≤ x) ∧
objective A b (xStar A b) = optValue A b ∧
∀ x, FirstStageFeasible A b x → objective A b x = optValue A b → x = xStar A b := by sorry
end SPHardness.IntFeas
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.