§3.1 — every PHA price vector yields a lower bound
ProvedPHLowerBound.TwoStage.pha_lower_boundLet a finite-support two-stage SMIP have a feasible, attained finite optimum and nonempty scenario sets . Run Algorithm 1 through any iteration , starting with zero prices and using its exact scenario minimizers, aggregation, and price updates. Its scenario dual bound satisfies
Thus a lower bound on the optimal cost is available after every completed price update of progressive hedging, regardless of whether its first-stage scenario decisions have converged.
Formalization Note A finite run prefix records all of Algorithm 1's exact minimization clauses through . Its final price vector is computed at iteration ; Step 6 can stop the run there. The page does not restrict the sign of , and neither does the theorem.
import Mathlib import Definitions.Def_PHLowerBound_TwoStage_Setting
namespace PHLowerBound.TwoStage
attribute [local instance] Classical.decEq
theorem pha_lower_bound {Ξ : Type*} [Fintype Ξ]
{n₁ p₁ n₂ p₂ m₁ m₂ : ℕ} (P : SMIP Ξ n₁ p₁ n₂ p₂ m₁ m₂)
(hX : ∀ ξ, (P.X ξ).Nonempty) (hopt : P.HasOptimalSolution)
(ρ : ℝ) (x : ℕ → Ξ → Fin n₁ → ℝ) (y : ℕ → Ξ → Fin n₂ → ℝ)
(xhat : ℕ → Fin n₁ → ℝ) (w : ℕ → Ξ → Fin n₁ → ℝ)
(N : ℕ) (hN : 1 ≤ N) (hrun : P.IsPHARun ρ x y xhat w N) :
P.D (w N) ≤ P.zStar := by sorry
end PHLowerBound.TwoStage
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.