Proof of Theorem 6.1 — X* is δ′-locally optimal for F(X) + ½r‖X − X*‖² = E{f̃_s(X(s))} over 𝒞 ∩ 𝒩
ProvedProgHedging.Nonconvex.local_opt_tildelocal-optimalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1progressive-hedging
Let , , and let , be a run of progressive hedging with -locally optimal subproblem solutions, with and . Let and . Then
- for all with ;
- for every policy ,
Together these say that is a local minimizer of the modified problem , in which each is replaced by .
Formalization Note As in (6.6), the paper's closed ball is replaced by the open ball; see the note on (6.6) for why the closed-ball version can fail. is the weighted norm (pnorm).
Preamble
import Mathlib import Definitions.Def_ProgHedging_Convex_Problem import Definitions.Def_ProgHedging_Nonconvex_Algorithm import Definitions.Def_ClarkeGradients_Shared_generalizedGradient import Definitions.Def_ClarkeGradients_FlowInvariance_normalCone open Filter Topology
Formal statement
namespace ProgHedging.Nonconvex
/-- Proof of Theorem 6.1, p. 31: `X*` is `δ′`-locally optimal (open `δ′`-ball of the norm (2.3))
for minimizing `F(X) + ½r‖X − X*‖² = E{f̃_s(X(s))}` over `𝒞 ∩ 𝒩`, and that identity holds. -/
theorem local_opt_tilde {S : Type*} [Fintype S] {n T : ℕ} (pr : Problem S n T) {r δ : ℝ}
(hr : 0 < r) (hδ : 0 < δ) (X W : ℕ → ProgHedging.Convex.Policy S n) (hseq : pr.IsLocalPHSeq r δ X W)
(Xs Ws : ProgHedging.Convex.Policy S n) (hX : Tendsto X atTop (𝓝 Xs)) (hW : Tendsto W atTop (𝓝 Ws)) :
(∀ Y ∈ pr.adm ∩ pr.N, pr.pnorm (Y - Xs) < pr.deltaPrime δ →
pr.F Xs ≤ pr.F Y + r / 2 * pr.pnorm (Y - Xs) ^ 2) ∧
∀ Y : ProgHedging.Convex.Policy S n, pr.F Y + r / 2 * pr.pnorm (Y - Xs) ^ 2 = ∑ s, pr.p s * pr.fTilde r Xs s (Y s) := by sorry
end ProgHedging.Nonconvex
Source
Rockafellar and Wets, Scenarios and policy aggregation in optimization under uncertainty, IIASA Working Paper WP-87-119 (1987), p. 31, proof of Theorem 6.1, last paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.