Theorem 5.1 — convex progressive hedging is bounded iff (P) and (D) have solutions, and then converges to such a pair, monotonically in ‖·‖_r
ProvedProgHedging.Convex.theorem_5_1Consider the progressive hedging algorithm in the convex case with exact minimization and a fixed , started from an arbitrary policy and a price system , and let and be the sequences it generates. Then:
- the sequences and are bounded if and only if (P) and (D) both have optimal solutions;
- in that case there is a particular pair optimal for (P) and optimal for (D) such that
and, in terms of , for every
with strict inequality unless , while for every
This is the main convergence theorem for progressive hedging: every iteration strictly improves the distance to a primal–dual solution until one is reached, and boundedness of the iterates detects solvability.
Formalization Note. Boundedness and convergence of policy sequences use Mathlib's topology on S → EuclideanSpace ℝ (Fin n), which in finite dimension agrees with that of the norm ; the inequalities use built from that weighted norm, never Mathlib's sup norm. The paper adds "i.e. there exist and satisfying the optimality conditions in Theorem 4.1, or equivalently the saddle point condition in Theorem 4.2"; that equivalence is the content of Theorems 4.2 and 4.6, and the theorem is stated with the printed condition, existence of optimal solutions of (P) and (D).
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
namespace ProgHedging.Convex
/-- Theorem 5.1, pp. 20–21. Progressive hedging in the convex case with exact minimization, from
arbitrary `X⁰` and `W⁰ ∈ ℳ`: the sequences `X̂^ν = J X^ν` and `W^ν` are bounded iff (P) and (D) both
have optimal solutions. In that case they converge to some optimal pair `(X*, W*)`, the distance to
it in `‖·‖_r` (5.2) does not increase (5.3), strictly unless `(X̂^ν, W^ν) = (X*, W*)`, and the step
lengths in `‖·‖_r` do not increase from `ν = 1` on (5.4). -/
theorem theorem_5_1 {S : Type*} [Fintype S] {n T : ℕ} (pr : Problem S n T)
(hconv : pr.ConvexCase) {r : ℝ} (hr : 0 < r)
(X W : ℕ → Policy S n) (hseq : pr.IsExactPHSeq r X W) :
((Bornology.IsBounded (Set.range fun ν => pr.J (X ν)) ∧ Bornology.IsBounded (Set.range W)) ↔
((∃ Xs, pr.SolvesP Xs) ∧ ∃ Ws, pr.SolvesD Ws)) ∧
(((∃ Xs, pr.SolvesP Xs) ∧ ∃ Ws, pr.SolvesD Ws) →
∃ Xs Ws, pr.SolvesP Xs ∧ pr.SolvesD Ws ∧
Tendsto (fun ν => pr.J (X ν)) atTop (𝓝 Xs) ∧ Tendsto W atTop (𝓝 Ws) ∧
(∀ ν, pr.rnorm r (pr.J (X (ν + 1)) - Xs) (W (ν + 1) - Ws) ≤
pr.rnorm r (pr.J (X ν) - Xs) (W ν - Ws) ∧
((pr.J (X ν), W ν) ≠ (Xs, Ws) →
pr.rnorm r (pr.J (X (ν + 1)) - Xs) (W (ν + 1) - Ws) <
pr.rnorm r (pr.J (X ν) - Xs) (W ν - Ws))) ∧
∀ ν, 1 ≤ ν →
pr.rnorm r (pr.J (X (ν + 1)) - pr.J (X ν)) (W (ν + 1) - W ν) ≤
pr.rnorm r (pr.J (X ν) - pr.J (X (ν - 1))) (W ν - W (ν - 1))) := by sorry
end ProgHedging.Convex
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.