(5.26) — one exact iteration is firmly nonexpansive in ‖·‖_r on 𝒩 × ℳ (proof of Theorem 5.1)
ProvedProgHedging.Convex.eq_5_26p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1progressive-hedgingproximal-pointstochastic-programming
Assume the convex case and . Let , and let one exact iteration of progressive hedging take to and to . Then
where .
This is the firm nonexpansiveness of the iteration map, from which the monotonicity statements (5.3) and (5.4) of Theorem 5.1 follow.
Formalization Note. The paper states (5.26) for acting on with , in the norm . By (5.5)–(5.7) and (5.22), exactly when one exact iteration takes to , and ; the statement above is (5.26) in these original variables. The operator itself is not introduced.
Preamble
import Mathlib import Definitions.Def_ProgHedging_Convex_Problem import Definitions.Def_ProgHedging_Convex_Algorithm open scoped RealInnerProductSpace Pointwise Topology open Filter
Formal statement
namespace ProgHedging.Convex
/-- (5.26), proof of Theorem 5.1, p. 23, in the original variables. In the convex case with
`r > 0`, let one exact iteration take `(V, W) ∈ 𝒩 × ℳ` to `(V₁, W₁)` and `(V', W') ∈ 𝒩 × ℳ` to
`(V₁', W₁')`. Then, in the norm `‖·‖_r` of (5.2),
`‖(V₁', W₁') − (V₁, W₁)‖_r² + ‖((V', W') − (V₁', W₁')) − ((V, W) − (V₁, W₁))‖_r² ≤ ‖(V', W') − (V, W)‖_r²`. -/
theorem eq_5_26 {S : Type*} [Fintype S] {n T : ℕ} (pr : Problem S n T)
(hconv : pr.ConvexCase) {r : ℝ} (hr : 0 < r)
(V W V' W' V₁ W₁ V₁' W₁' : Policy S n)
(hV : V ∈ pr.N) (hW : W ∈ pr.M) (hV' : V' ∈ pr.N) (hW' : W' ∈ pr.M)
(hstep : pr.IsStep r V W V₁ W₁) (hstep' : pr.IsStep r V' W' V₁' W₁') :
pr.rnorm r (V₁' - V₁) (W₁' - W₁) ^ 2 +
pr.rnorm r ((V' - V₁') - (V - V₁)) ((W' - W₁') - (W - W₁)) ^ 2 ≤
pr.rnorm r (V' - V) (W' - W) ^ 2 := 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. 23, (5.26) in the proof of Theorem 5.1, with (5.5)–(5.7) p. 21 and (5.22)–(5.23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.