Theorem 6.1 — a limit of δ-locally optimal progressive hedging is a stationary point of (P) and a local solution of (P̃)
ProvedProgHedging.Nonconvex.theorem_6_1Consider the scenario model under its standing assumptions, with no convexity. Fix and , and let , be generated by the progressive hedging algorithm in such a way that in each iteration is -locally optimal for the scenario subproblem
with and . Suppose and . Then:
- and satisfy the optimality conditions of Theorem 4.1: , , and
in this sense is a stationary point of (P); 2. is a locally optimal solution of the problem obtained from (P) by replacing each by
that is, for all near ; 3. is a corresponding multiplier vector for : for all .
Here is Clarke's generalized gradient and Clarke's normal cone. Without convexity one cannot expect the algorithm to solve (P) globally; the theorem says that whenever it converges, its limit is as good a "solution" as can be hoped for.
Formalization Note No convexity and no constraint qualification are assumed: the standing assumptions of the model (nonempty closed , locally Lipschitz , bounded level sets) are the only hypotheses besides the run and its convergence. The -neighbourhood of is the closed Euclidean ball. Convergence of policies and "near " refer to the (norm-independent) topology of the finite-dimensional space . The algorithm starts from and as on p. 9.
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 scoped Pointwise open Filter Topology
namespace ProgHedging.Nonconvex
/-- Theorem 6.1, p. 30: if progressive hedging with `δ`-locally optimal subproblem solutions
generates `X^ν → X*` and `W^ν → W*`, then `X*`, `W*` satisfy the optimality conditions of
Theorem 4.1; moreover `X*` is locally optimal for, and `W*` a multiplier vector for, the problem
`(P̃)` obtained by replacing each `f_s` with `f̃_s(x) = f_s(x) + ½r|x − X*(s)|²` (6.1). -/
theorem theorem_6_1 {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)) :
pr.OptCond41 Xs Ws ∧
(∃ ε > 0, ∀ Y ∈ pr.adm ∩ pr.N, dist Y Xs < ε →
∑ s, pr.p s * pr.fTilde r Xs s (Xs s) ≤ ∑ s, pr.p s * pr.fTilde r Xs s (Y s)) ∧
∀ s, -Ws s ∈ ClarkeGradients.Shared.generalizedGradient (pr.fTilde r Xs s) (Xs s) +
ClarkeGradients.FlowInvariance.normalCone (pr.C s) (Xs s) := by sorry
end ProgHedging.Nonconvex
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.