Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 4 — superlinear convergence of the projected Newton method

Proved
ProjNewton.Superlinear.proposition4

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

bound-constraintsnonlinear-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1projected-newton

Let f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R be convex and twice continuously differentiable. Suppose problem (1) has a unique optimal solution x∗x^*x∗ in the nonnegative orthant satisfying Assumption (C). Suppose also that some 0<m1,m20<m_1,m_20<m1​,m2​ bound the Hessian quadratic form at every point yyy in the unrestricted initial level set {y:f(y)≤f(x0)}\{y:f(y)\le f(x_0)\}{y:f(y)≤f(x0​)} and in every direction zzz:

m1∥z∥2≤z⊤∇2f(y)z≤m2∥z∥2.m_1\|z\|^2\le z^\top\nabla^2f(y)z\le m_2\|z\|^2.m1​∥z∥2≤z⊤∇2f(y)z≤m2​∥z∥2.

Run (32)–(37) with Dk=Hk−1D_k=H_k^{-1}Dk​=Hk−1​, where HkH_kHk​ zeros only off-diagonal Hessian entries touching Ik+I_k^+Ik+​. Then xk→x∗x_k\to x^*xk​→x∗ and the error converges superlinearly: for every c>0c>0c>0, eventually ∥xk+1−x∗∥≤c∥xk−x∗∥\|x_{k+1}-x^*\|\le c\|x_k-x^*\|∥xk+1​−x∗∥≤c∥xk​−x∗∥. If the Hessian is Lipschitz on a neighborhood of x∗x^*x∗, the error is at least quadratic: for some C>0C>0C>0, eventually ∥xk+1−x∗∥≤C∥xk−x∗∥2\|x_{k+1}-x^*\|\le C\|x_k-x^*\|^2∥xk+1​−x∗∥≤C∥xk​−x∗∥2.

This is the paper's main rate claim for its partly diagonal projected Newton method.

Formalization Note The printed bound misbinds zzz in the level set while leaving its Hessian point free; it is read as the stated y,zy,zy,z quantification. The level set has no feasibility restriction, as printed. The C2C^2C2 hypothesis includes the standing C1C^1C1 convention; x∗x^*x∗ is feasible and uniquely optimal among feasible points. The run starts feasible and chooses the first acceptable exponent. No convergence, matrix invertibility, active-set identification or admissibility is assumed. Superlinearity uses a uniform eventual inequality, so finite termination is covered.

Preamble
import Mathlib
import Definitions.Def_ProjNewton_Superlinear_Algorithm
Formal statement
namespace ProjNewton.Superlinear

open Matrix Filter Topology

/-- Bertsekas (1982), Proposition 4, p. 236. -/
theorem proposition4 {n : ℕ} (hn : 0 < n) (f : Vec n → ℝ)
    (hf2 : ContDiff ℝ 2 f) (hconv : ConvexOn ℝ Set.univ f)
    (xs : Vec n) (hopt : xs ∈ orthant n ∧ ∀ y ∈ orthant n, f xs ≤ f y)
    (huniq : ∀ y ∈ orthant n, (∀ z ∈ orthant n, f y ≤ f z) → y = xs)
    (hC : AssumptionC f xs) (μ : Fin n → ℝ) (ε β σ : ℝ)
    (hpar : Params μ ε β σ) (x : ℕ → Vec n)
    (hm : ∃ m₁ m₂ : ℝ, 0 < m₁ ∧ 0 < m₂ ∧
      ∀ y : Vec n, f y ≤ f (x 0) → ∀ z : Fin n → ℝ,
        m₁ * (z ⬝ᵥ z) ≤ hessForm f y z ∧ hessForm f y z ≤ m₂ * (z ⬝ᵥ z))
    (hrun : IsRun f μ ε β σ (fun k => (Hmat f μ ε (x k))⁻¹) x) :
    Tendsto x atTop (𝓝 xs) ∧
    (∀ c : ℝ, 0 < c → ∀ᶠ k in atTop,
      ‖x (k + 1) - xs‖ ≤ c * ‖x k - xs‖) ∧
    ((∃ δ : ℝ, 0 < δ ∧ ∃ L : NNReal,
      LipschitzOnWith L (fderiv ℝ (gradient f)) (Metric.ball xs δ)) →
      ∃ C : ℝ, 0 < C ∧ ∀ᶠ k in atTop,
        ‖x (k + 1) - xs‖ ≤ C * ‖x k - xs‖ ^ 2) := by sorry

end ProjNewton.Superlinear
Source
Bertsekas, Projected Newton Methods for Optimization Problems with Simple Constraints, SIAM J. Control Optim. 20(2) (1982), p. 236, Proposition 4; Assumption (C), p. 233
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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