Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1, pp. 1720–1721 — local contractivity of the real-time iterations: (4.2), (4.3), (4.4)

Proved
RealTimeIter.Contract.theorem_4_1

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

contractionmodel-predictive-controlnewton-type-methodp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1real-time-iteration

Consider the shrinking-horizon problems Pk(xk)P_k(x_k)Pk​(xk​), their Lagrangians Lk\mathcal L^kLk and Newton-type matrices JkJ^kJk, a family of compatible norms ∥⋅∥k\|\cdot\|_k∥⋅∥k​, a neighbourhood D0⊂Rn0D_0\subset\mathbb R^{n_0}D0​⊂Rn0​ with projections Dk+1:=Πk+1DkD_{k+1}:=\Pi^{k+1}D_kDk+1​:=Πk+1Dk​, an initial state x0x_0x0​ and an initial guess y0∈D0y^0\in D_0y0∈D0​. Assume, for k=0,…,Nk=0,\dots,Nk=0,…,N: Lk\mathcal L^kLk is twice continuously differentiable on DkD_kDk​; JkJ^kJk is continuous on DkD_kDk​ and has a bounded inverse there; and there are κ<1\kappa<1κ<1 and ω∈R\omega\in\mathbb Rω∈R such that (4.1a), (4.1b) hold for all y′,y∈Dky',y\in D_ky′,y∈Dk​, Δy=y′−y\Delta y=y'-yΔy=y′−y, t∈[0,1]t\in[0,1]t∈[0,1], and (4.1c) holds for k≤N−1k\le N-1k≤N−1:

∥Jk(y′)−1(Jk(y+tΔy)−∇y2Lk(y+tΔy))Δy∥k≤κ∥Δy∥k,\big\|J^k(y')^{-1}\big(J^k(y+t\Delta y)-\nabla^2_y\mathcal L^k(y+t\Delta y)\big)\Delta y\big\|_k\le\kappa\|\Delta y\|_k,​Jk(y′)−1(Jk(y+tΔy)−∇y2​Lk(y+tΔy))Δy​k​≤κ∥Δy∥k​, ∥Jk(y′)−1(Jk(y+tΔy)−Jk(y))Δy∥k≤ωt∥Δy∥k2,\big\|J^k(y')^{-1}\big(J^k(y+t\Delta y)-J^k(y)\big)\Delta y\big\|_k\le\omega t\|\Delta y\|_k^2,​Jk(y′)−1(Jk(y+tΔy)−Jk(y))Δy​k​≤ωt∥Δy∥k2​, ∥Jk+1(Πk+1y′)−1Πk+1(Jk(y+tΔy)−Jk(y))Δy∥k+1≤ωt∥Δy∥k2.\big\|J^{k+1}(\Pi^{k+1}y')^{-1}\Pi^{k+1}\big(J^k(y+t\Delta y)-J^k(y)\big)\Delta y\big\|_{k+1}\le\omega t\|\Delta y\|_k^2.​Jk+1(Πk+1y′)−1Πk+1(Jk(y+tΔy)−Jk(y))Δy​k+1​≤ωt∥Δy∥k2​.

Suppose the first step is small, δ0:=κ+ω2∥Δy0∥0<1\delta_0:=\kappa+\frac{\omega}{2}\|\Delta y^0\|_0<1δ0​:=κ+2ω​∥Δy0∥0​<1, and B0={y:∥y−y0∥0≤∥Δy0∥0/(1−δ0)}⊆D0B_0=\{y:\|y-y^0\|_0\le\|\Delta y^0\|_0/(1-\delta_0)\}\subseteq D_0B0​={y:∥y−y0∥0​≤∥Δy0∥0​/(1−δ0​)}⊆D0​. Let y0,…,yNy^0,\dots,y^Ny0,…,yN be the real-time iterates, Δyk:=−Jk(yk)−1∇yLk(yk)\Delta y^k:=-J^k(y^k)^{-1}\nabla_y\mathcal L^k(y^k)Δyk:=−Jk(yk)−1∇y​Lk(yk), yk+1:=Πk+1(yk+Δyk)y^{k+1}:=\Pi^{k+1}(y^k+\Delta y^k)yk+1:=Πk+1(yk+Δyk), where Lk\mathcal L^kLk belongs to Pk(xk)P_k(x_k)Pk​(xk​) and xk+1=fk(xk,uk)x_{k+1}=f_k(x_k,u_k)xk+1​=fk​(xk​,uk​), uk:=qkk+Δqkku_k:=q^k_k+\Delta q^k_kuk​:=qkk​+Δqkk​, and let δk:=κ+ω2∥Δyk∥k\delta_k:=\kappa+\frac{\omega}{2}\|\Delta y^k\|_kδk​:=κ+2ω​∥Δyk∥k​. Then:

  1. (4.2) for k=0,…,Nk=0,\dots,Nk=0,…,N: yk∈Πk⋯Π1B0⊆Dky^k\in\Pi^k\cdots\Pi^1B_0\subseteq D_kyk∈Πk⋯Π1B0​⊆Dk​;
  2. (4.3) for k=0,…,N−1k=0,\dots,N-1k=0,…,N−1:
∥Δyk+1∥k+1≤(κ+ω2∥Δyk∥k)∥Δyk∥k=δk∥Δyk∥k≤δ0∥Δyk∥k,\|\Delta y^{k+1}\|_{k+1}\le\Big(\kappa+\frac{\omega}{2}\|\Delta y^k\|_k\Big)\|\Delta y^k\|_k=\delta_k\|\Delta y^k\|_k\le\delta_0\|\Delta y^k\|_k,∥Δyk+1∥k+1​≤(κ+2ω​∥Δyk∥k​)∥Δyk∥k​=δk​∥Δyk∥k​≤δ0​∥Δyk∥k​,

and δk≤δ0\delta_k\le\delta_0δk​≤δ0​; 3. (4.4) for k=0,…,Nk=0,\dots,Nk=0,…,N: the Newton-type iterates (2.4) of Pk(xk)P_k(x_k)Pk​(xk​) started at yky^kyk converge to a stationary point y∗ky^k_*y∗k​ (∇yLk(y∗k)=0\nabla_y\mathcal L^k(y^k_*)=0∇y​Lk(y∗k​)=0), and

∥yk−y∗k∥k≤∥Δyk∥k1−δk≤(δ0)k∥Δy0∥01−δ0.\|y^k-y^k_*\|_k\le\frac{\|\Delta y^k\|_k}{1-\delta_k}\le\frac{(\delta_0)^k\|\Delta y^0\|_0}{1-\delta_0}.∥yk−y∗k​∥k​≤1−δk​∥Δyk∥k​​≤1−δ0​(δ0​)k∥Δy0∥0​​.

The real-time iteration performs a single Newton-type step per problem and then moves to the next, shorter problem. The theorem shows that, after one initial disturbance, its iterates contract like a Newton-type method and approach the exact stationary points of the problems they track, at a geometric rate.

Formalization Note. The hypotheses are bundled in Thm41Hyp (see the definitions file): differentiability, continuity and invertibility are required at the points of DkD_kDk​, not globally; (4.1a)–(4.1c) are required for those ttt with y+tΔy∈Dky+t\Delta y\in D_ky+tΔy∈Dk​, since the paper's Jk,LkJ^k,\mathcal L^kJk,Lk live on DkD_kDk​ (which need not be convex). y∗ky^k_*y∗k​ is identified as the limit of the Newton-type scheme (2.4) from yky^kyk, as in the paper's proof (p. 1723), so it cannot be chosen after the fact. Since xkx_kxk​ enters Lk\mathcal L^kLk linearly, its Hessian and JkJ^kJk do not depend on xkx_kxk​ (Remark 1).

Preamble
import Mathlib
import Definitions.Def_RealTimeIter_Contract_Problem
import Definitions.Def_RealTimeIter_Contract_Iteration
Formal statement
namespace RealTimeIter.Contract

theorem theorem_4_1 (P : OCP) (ν : CompatNorms P) (x0 : Vec P.nx) (y0 : PD P 0)
    (D0 : Set (PD P 0)) (κ ω : ℝ) (h : Thm41Hyp P ν x0 y0 D0 κ ω) :
    -- (4.2)
    (∀ k ≤ P.N, (rti P x0 y0 k).2 ∈ projTo P k '' ball0 P ν x0 y0 κ ω ∧
        projTo P k '' ball0 P ν x0 y0 κ ω ⊆ Dset P D0 k) ∧
    -- (4.3)
    (∀ k < P.N,
        ν.nrm (k + 1) (rtiStep P x0 y0 (k + 1))
          ≤ (κ + ω / 2 * ν.nrm k (rtiStep P x0 y0 k)) * ν.nrm k (rtiStep P x0 y0 k) ∧
        delta P ν x0 y0 κ ω k * ν.nrm k (rtiStep P x0 y0 k)
          ≤ delta P ν x0 y0 κ ω 0 * ν.nrm k (rtiStep P x0 y0 k) ∧
        delta P ν x0 y0 κ ω k ≤ delta P ν x0 y0 κ ω 0) ∧
    -- (4.4)
    (∀ k ≤ P.N, ∃ ystar : PD P k,
        Filter.Tendsto (newtonIter P k (rti P x0 y0 k).1 (rti P x0 y0 k).2) Filter.atTop
          (nhds ystar) ∧
        grad P k (rti P x0 y0 k).1 ystar = 0 ∧
        ν.nrm k ((rti P x0 y0 k).2 - ystar)
          ≤ ν.nrm k (rtiStep P x0 y0 k) / (1 - delta P ν x0 y0 κ ω k) ∧
        ν.nrm k (rtiStep P x0 y0 k) / (1 - delta P ν x0 y0 κ ω k)
          ≤ delta P ν x0 y0 κ ω 0 ^ k * ν.nrm 0 (rtiStep P x0 y0 0)
              / (1 - delta P ν x0 y0 κ ω 0)) := by sorry

end RealTimeIter.Contract
Source
Diehl, Bock, Schlöder, A real-time iteration scheme for nonlinear optimization in optimal feedback control, SIAM J. Control Optim. 43 (2005), pp. 1720–1721, Theorem 4.1, (4.1a)–(4.4)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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