Proposition 3.2 — every modified scenario subproblem has an optimal solution, unique in the convex case
ProvedProgHedging.Convex.proposition_3_2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1progressive-hedgingstochastic-programming
Let , and . The modified scenario subproblem
has at least one optimal solution (so a finite optimal value). In the convex case its optimal solution is unique.
The subproblems of the progressive hedging algorithm are of this form, so this is what makes Step 2 of the algorithm well defined.
Formalization Note. "Finite optimal value" is automatic for a real-valued objective with a minimizer, so it is not stated separately.
Preamble
import Mathlib import Definitions.Def_ProgHedging_Convex_Problem open scoped RealInnerProductSpace Pointwise Topology open Filter
Formal statement
namespace ProgHedging.Convex
/-- Proposition 3.2, p. 11. For `r > 0`, every modified scenario subproblem
`(P̂_s(x̂, w, r)) minimize f_s(x) + x·w + ½ r |x − x̂|² over x ∈ C_s`
has an optimal solution (hence a finite optimal value); in the convex case it is unique. -/
theorem proposition_3_2 {S : Type*} [Fintype S] {n T : ℕ} (pr : Problem S n T) (s : S)
(xhat w : EuclideanSpace ℝ (Fin n)) {r : ℝ} (hr : 0 < r) :
(∃ x ∈ pr.C s, ∀ z ∈ pr.C s, pr.subObj s xhat w r x ≤ pr.subObj s xhat w r z) ∧
(pr.ConvexCase → ∀ x ∈ pr.C s, ∀ x' ∈ pr.C s,
(∀ z ∈ pr.C s, pr.subObj s xhat w r x ≤ pr.subObj s xhat w r z) →
(∀ z ∈ pr.C s, pr.subObj s xhat w r x' ≤ pr.subObj s xhat w r z) → x = x') := 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. 11, Proposition 3.2, (3.4); (P̂_s(x̂, w, r)) defined p. 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.