Lemma 2 — Av ≤ v gives v ≥ f, Av ≥ v gives v ≤ f; Av_δ ≥ v_δ; H_δ v ≥ v gives v_δ ≥ H_δ v
ProvedDenardoDP.NStage.lemma2contraction-mappingdynamic-programmingmonotone-operatorp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Work in Denardo's model under the monotonicity and N-stage contraction assumptions, with the fixed point of for each policy and the optimal return. Then:
- (a) if , then ; if , then ;
- (b) for each ;
- (c) if , then .
Inequalities between functions are pointwise. Part (a) says that is the smallest element of with and the largest with ; it is the step that identifies as the fixed point of in Theorem 4 and makes optimal for the two mathematical programs of §6.
Formalization Note is any element of that is the pointwise least upper bound of (such an exists by Theorem 4 (a)–(c)). The family satisfies , the paper's definition of in §5.
Preamble
import Mathlib import Definitions.Def_DenardoDP_NStage_Model
Formal statement
namespace DenardoDP.NStage
theorem lemma2 {Ω : Type*} {D : Ω → Type*}
(h : (x : Ω) → D x → DenardoDP.Contraction.BFun Ω → ℝ) (H : ((x : Ω) → D x) → DenardoDP.Contraction.BFun Ω → DenardoDP.Contraction.BFun Ω)
(A : DenardoDP.Contraction.BFun Ω → DenardoDP.Contraction.BFun Ω) (v : ((x : Ω) → D x) → DenardoDP.Contraction.BFun Ω) (N : ℕ) (c : ℝ)
(hH : DenardoDP.Contraction.IsPolicyOperator h H) (hA : DenardoDP.Contraction.IsMaxOperator h A)
(hmono : DenardoDP.Contraction.MonotonicityAssumption H) (hN : NStageContractionAssumption H N c)
(hv : ∀ δ, (H δ)^[N] (v δ) = v δ)
(f : DenardoDP.Contraction.BFun Ω) (hf : DenardoDP.Contraction.IsOptimalReturn v f) :
((∀ w, DenardoDP.Contraction.PLe (A w) w → DenardoDP.Contraction.PLe f w) ∧ (∀ w, DenardoDP.Contraction.PLe w (A w) → DenardoDP.Contraction.PLe w f)) ∧
(∀ δ, DenardoDP.Contraction.PLe (v δ) (A (v δ))) ∧
(∀ δ w, DenardoDP.Contraction.PLe w (H δ w) → DenardoDP.Contraction.PLe (H δ w) (v δ)) := by sorry
end DenardoDP.NStage
Source
Denardo, Contraction Mappings in the Theory Underlying Dynamic Programming, SIAM Review 9(2) (1967), p. 169, Lemma 2 (proof pp. 169–170)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.