Observation 4.1, p. 12 — dynamic programming principle V(x) = min over y ∈ B_ρ(x) ∩ X of V(y) + C(y, x)
ProvedSemilinearHJ.Verification.observation_4_1dynamic-programminghamilton-jacobioptimal-controlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1state-constraintsviscosity-solutions
Let be a polytope, Lipschitz continuous, the speed bound of the running cost (3.1), and compact. Let be the value function of the source problem (SP) and the minimum cost of travelling from to , both with values in . For and let be the closed ball of radius around . Then for every and every ,
that is, for every , with equality for some such .
This dynamic programming principle is the tool used to prove that is a viscosity subsolution (Proposition 4.3).
Formalization Note The radius is called to keep it apart from the speed bound ; the statement holds for every , so it covers the paper's reuse of the letter .
Differences from the source:
- reading: ", the closed unit ball in with center ", for → for every ; reason: the paper's norm is (p. 5) and the radius is the quantified ; the letter is renamed to avoid a clash with the speed bound , and every radius is covered.
- encoding: → existence of a minimizer together with the lower bound for every ; reason: that is what a minimum means.
- encoding: , real or → values in
ℝ≥0∞; reason: is for paths faster than under (3.1), and . - encoding: → , nonnegative and Lipschitz on ; reason: values off are never used.
Preamble
import Mathlib import Definitions.Def_SemilinearHJ_Verification_Setting
Formal statement
namespace SemilinearHJ.Verification
open scoped ENNReal MeasureTheory
theorem observation_4_1 {n : ℕ} (X : Set (E n)) (hX : IsPolytope X)
(Ψ : E n → E n) (hΨL : ∃ K : NNReal, LipschitzOnWith K Ψ X) (hΨ0 : ∀ x ∈ X, ∀ i, 0 ≤ Ψ x i)
(r : ℝ) (hr : 0 < r)
(X0 : Set (E n)) (hX0c : IsCompact X0) (hX0X : X0 ⊆ X) :
∀ x ∈ X, ∀ ρ : ℝ, 0 < ρ →
(∃ y ∈ X, l1 (y - x) ≤ ρ ∧ srcVal X Ψ r X0 x = srcVal X Ψ r X0 y + minCost X Ψ r y x) ∧
∀ y ∈ X, l1 (y - x) ≤ ρ → srcVal X Ψ r X0 x ≤ srcVal X Ψ r X0 y + minCost X Ψ r y x := by sorry
end SemilinearHJ.Verification
Source
Sandholm, Tran & Arigapudi, Hamilton-Jacobi Equations with Semilinear Costs and State Constraints, with Applications to Large Deviations in Games, author's manuscript (July 4, 2018; Math. Oper. Res. doi:10.1287/moor.2020.1114), p. 12, Observation 4.1, Equation (4.2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.