Proof of Theorem 5.1 (p. 24) — the fixed points of one exact iteration are exactly the pairs (X*, W*) with X* solving (P) and W* solving (D)
ProvedProgHedging.Convex.fixedPoint_iff_optimalconvex-dualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1progressive-hedgingstochastic-programming
Assume the convex case and , and let , . One exact iteration of progressive hedging maps to itself if and only if is an optimal solution of (P) and is an optimal solution of (D).
In the proof of Theorem 5.1 this is the identification of the zeros of , equivalently the fixed points of the iteration, with the primal–dual optimal pairs; combined with the convergence theory of the proximal point algorithm it gives the limits in Theorem 5.1.
Preamble
import Mathlib import Definitions.Def_ProgHedging_Convex_Problem import Definitions.Def_ProgHedging_Convex_Duality import Definitions.Def_ProgHedging_Convex_Algorithm open scoped RealInnerProductSpace Pointwise Topology open Filter
Formal statement
namespace ProgHedging.Convex
/-- Proof of Theorem 5.1, p. 24. In the convex case with `r > 0`, a pair `(V, W) ∈ 𝒩 × ℳ` is a
fixed point of one exact iteration of the algorithm iff `V` is an optimal solution of (P) and `W` is
an optimal solution of (D). -/
theorem fixedPoint_iff_optimal {S : Type*} [Fintype S] {n T : ℕ} (pr : Problem S n T)
(hconv : pr.ConvexCase) {r : ℝ} (hr : 0 < r) (V W : Policy S n)
(hV : V ∈ pr.N) (hW : W ∈ pr.M) :
pr.IsStep r V W V W ↔ pr.SolvesP V ∧ pr.SolvesD W := by sorry
end ProgHedging.Convex
Source
Rockafellar and Wets, Scenarios and policy aggregation in optimization under uncertainty, IIASA Working Paper WP-87-119 (1987), p. 24, proof of Theorem 5.1, first paragraph and the paragraph after (5.29)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.