Proof of Theorem 4, pp. 13–14 — every ϵ-optimal decision x of (11) satisfies |x⋆ − x| ≤ 2nϵ
ProvedSPHardness.IntFeas.epsOptimal_boundapproximationepsilon-optimalp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-programming
Let be an instance of the Integer Feasibility Problem with a nonempty polytope and , let , and let . If is an -optimal decision of problem (11), that is, is feasible and
then
This converts relative accuracy of the objective into absolute accuracy of the decision; with it gives , half the gap of the dichotomy for .
Formalization Note. is the infimum of the objective over feasible decisions; is the integral over with Lebesgue measure. The hypotheses (used in ) and (implicit in -optimality) are added. The page's strict "" is the combination of this bound with and is part of Theorem 4.
Preamble
import Mathlib import Definitions.Def_SPHardness_IntFeas_Model open MeasureTheory
Formal statement
namespace SPHardness.IntFeas
theorem epsOptimal_bound {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℤ) (b : Fin m → ℤ)
(hinst : IsIFPInstance A b) (hne : ∃ ξ : Fin n → ℝ, InPolytope A b ξ) (hn : 1 ≤ n)
(ε : ℝ) (hε0 : 0 ≤ ε) (x : ℝ) (hx : IsEpsOptimal A b ε x) :
|xStar A b - x| ≤ 2 * n * ε := by sorry
end SPHardness.IntFeas
Source
Hanasusanto, Kuhn & Wiesemann, A comment on "computational complexity of stochastic programming problems", Optimization Online preprint 2015/03/4825 (version of October 6, 2015), §3, proof of Theorem 4, pp. 13–14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.