Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Observation 4.1, p. 12 — dynamic programming principle V(x) = min over y ∈ B_ρ(x) ∩ X of V(y) + C(y, x)

Proved
SemilinearHJ.Verification.observation_4_1

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-programminghamilton-jacobioptimal-controlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1state-constraintsviscosity-solutions

Let X⊂RnX\subset\mathbb R^nX⊂Rn be a polytope, Ψ:X→R+n\Psi:X\to\mathbb R^n_+Ψ:X→R+n​ Lipschitz continuous, r>0r>0r>0 the speed bound of the running cost (3.1), and X0⊆XX_0\subseteq XX0​⊆X compact. Let VVV be the value function of the source problem (SP) and C(y,x)C(y,x)C(y,x) the minimum cost of travelling from yyy to xxx, both with values in [0,+∞][0,+\infty][0,+∞]. For x∈Xx\in Xx∈X and ρ>0\rho>0ρ>0 let Bρ(x)={y: ∣y−x∣≤ρ}B_\rho(x)=\{y:\ |y-x|\le\rho\}Bρ​(x)={y: ∣y−x∣≤ρ} be the closed ℓ1\ell^1ℓ1 ball of radius ρ\rhoρ around xxx. Then for every x∈Xx\in Xx∈X and every ρ>0\rho>0ρ>0,

V(x)=min⁡y∈Bρ(x)∩X(V(y)+C(y,x)),V(x)=\min_{y\in B_\rho(x)\cap X}\big(V(y)+C(y,x)\big),V(x)=y∈Bρ​(x)∩Xmin​(V(y)+C(y,x)),

that is, V(x)≤V(y)+C(y,x)V(x)\le V(y)+C(y,x)V(x)≤V(y)+C(y,x) for every y∈Bρ(x)∩Xy\in B_\rho(x)\cap Xy∈Bρ​(x)∩X, with equality for some such yyy.

This dynamic programming principle is the tool used to prove that VVV is a viscosity subsolution (Proposition 4.3).

Formalization Note The radius is called ρ\rhoρ to keep it apart from the speed bound rrr; the statement holds for every ρ>0\rho>0ρ>0, so it covers the paper's reuse of the letter rrr.

Differences from the source:

  • reading: "Br(x)B_r(x)Br​(x), the closed unit ball in XXX with center xxx", for r>0r>0r>0 → {y∈X: ∣y−x∣1≤ρ}\{y\in X:\ |y-x|_1\le\rho\}{y∈X: ∣y−x∣1​≤ρ} for every ρ>0\rho>0ρ>0; reason: the paper's norm ∣⋅∣|\cdot|∣⋅∣ is ℓ1\ell^1ℓ1 (p. 5) and the radius is the quantified r>0r>0r>0; the letter is renamed to avoid a clash with the speed bound rrr, and every radius is covered.
  • encoding: min⁡\minmin → existence of a minimizer together with the lower bound for every yyy; reason: that is what a minimum means.
  • encoding: VVV, CCC real or +∞+\infty+∞ → values in ℝ≥0∞; reason: ccc is +∞+\infty+∞ for paths faster than rrr under (3.1), and inf⁡∅=+∞\inf\emptyset=+\inftyinf∅=+∞.
  • encoding: Ψ:X→R+n\Psi:X\to\mathbb R^n_+Ψ:X→R+n​ → Ψ:Rn→Rn\Psi:\mathbb R^n\to\mathbb R^nΨ:Rn→Rn, nonnegative and Lipschitz on XXX; reason: values off XXX 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
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me