Proposition 1 — scenario price duality gives a lower bound
ProvedPHLowerBound.TwoStage.proposition_1lagrangian-dualitylower-boundmixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-programming
Let be the scenario feasible set of a finite-support two-stage SMIP. Assume the SMIP has an attained finite optimum and every is nonempty. For prices satisfying , set
Then . This gives a certified lower bound from independent scenario optimization problems.
Formalization Note The paper's finite-support probabilities are positive and sum to one. The minima are represented by extended-real infima, preserving the value when a subproblem is unbounded below. Optimal attainment is the paper's standing assumption of §3.1.
Preamble
import Mathlib import Definitions.Def_PHLowerBound_TwoStage_Setting
Formal statement
namespace PHLowerBound.TwoStage
attribute [local instance] Classical.decEq
theorem proposition_1 {Ξ : Type*} [Fintype Ξ]
{n₁ p₁ n₂ p₂ m₁ m₂ : ℕ} (P : SMIP Ξ n₁ p₁ n₂ p₂ m₁ m₂)
(hX : ∀ ξ, (P.X ξ).Nonempty) (hopt : P.HasOptimalSolution)
(w : Ξ → Fin n₁ → ℝ) (hw : ∑ ξ, P.p ξ • w ξ = 0) :
P.D w ≤ P.zStar := by sorry
end PHLowerBound.TwoStage
Source
Gade et al., Obtaining Lower Bounds from the Progressive Hedging Algorithm for Stochastic Mixed-Integer Programs, author manuscript SAND2013-9195J (OSTI 1310314), p. 6, Proposition 1, (18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.