§3.1, p. 7 — weighted PHA prices sum to zero in every iteration
ProvedPHLowerBound.TwoStage.price_invariantdual-feasibilityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1progressive-hedgingstochastic-programming
Consider a finite-support two-stage stochastic mixed-integer program with scenario probabilities summing to one. Let be a run of Algorithm 1 through iteration . Then the prices satisfy
This invariant supplies the dual-feasibility condition used to turn scenario subproblem values into lower bounds. It includes the zero initial prices at .
Formalization Note The assertion does not require the paper's separate assumptions that every is nonempty and that the original SMIP attains its optimum; the stated run already records its own minimizers. No sign restriction on is imposed.
Preamble
import Mathlib import Definitions.Def_PHLowerBound_TwoStage_Setting
Formal statement
namespace PHLowerBound.TwoStage
attribute [local instance] Classical.decEq
theorem price_invariant {Ξ : Type*} [Fintype Ξ]
{n₁ p₁ n₂ p₂ m₁ m₂ : ℕ} (P : SMIP Ξ n₁ p₁ n₂ p₂ m₁ m₂)
(ρ : ℝ) (x : ℕ → Ξ → Fin n₁ → ℝ) (y : ℕ → Ξ → Fin n₂ → ℝ)
(xhat : ℕ → Fin n₁ → ℝ) (w : ℕ → Ξ → Fin n₁ → ℝ)
(N : ℕ) (hrun : P.IsPHARun ρ x y xhat w N) :
∀ ν ≤ N, ∑ ξ, P.p ξ • w ν ξ = 0 := 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. 7, §3.1, paragraph after Proposition 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.