Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 3.2, p. 235 — near a semismooth, strongly BD-regular zero one ∂_B Newton step contracts ‖x − x*‖ and ‖F‖ by any factor ε

Proved
QiNonsmoothEq.Local.corollary_3_2

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

bd-regularitynonsmooth-equationsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semismooth-newton

Let F:Rn→RnF:\mathbb R^n\to\mathbb R^nF:Rn→Rn be locally Lipschitz, let x∗x^*x∗ be a zero of FFF, and let FFF be semismooth and strongly BD-regular at x∗x^*x∗. Then for every ε>0\varepsilon>0ε>0 there is δ>0\delta>0δ>0 such that for every xxx with ∥x−x∗∥≤δ\|x-x^*\|\le\delta∥x−x∗∥≤δ and every V∈∂BF(x)V\in\partial_B F(x)V∈∂B​F(x), the map VVV is nonsingular and

∥x−V−1F(x)−x∗∥≤ε∥x−x∗∥,∥F(x−V−1F(x))∥≤ε∥F(x)∥.\|x-V^{-1}F(x)-x^*\|\le\varepsilon\|x-x^*\|,\qquad \|F(x-V^{-1}F(x))\|\le\varepsilon\|F(x)\|.∥x−V−1F(x)−x∗∥≤ε∥x−x∗∥,∥F(x−V−1F(x))∥≤ε∥F(x)∥.

The corollary isolates the one-step estimates behind Theorem 3.1: a single ∂B\partial_B∂B​ Newton step from close to x∗x^*x∗ shrinks both the distance to the zero and the residual by an arbitrarily small factor. It is reused for the damped Newton method in §4.

Formalization Note The paper prints "for any ε≥0\varepsilon\ge 0ε≥0"; for ε=0\varepsilon=0ε=0 the claim would force exact convergence in one step, which fails in general, so the statement is made for ε>0\varepsilon>0ε>0. V−1V^{-1}V−1 is written as any two-sided inverse WWW of VVV (it is unique). Local Lipschitz continuity of FFF is the paper's standing assumption (§1).

Preamble
import Mathlib
import Definitions.Def_NonsmoothNewton_Shared_clarkeJac
import Definitions.Def_NonsmoothNewton_Local_dirDeriv
import Definitions.Def_NonsmoothNewton_Local_SemismoothAt
import Definitions.Def_QiNonsmoothEq_Local_Setting
open Filter Topology
Formal statement
namespace QiNonsmoothEq.Local

/-- Qi (1993), Corollary 3.2, p. 235. Let `x*` be a zero of `F`, and let `F` be semismooth and
strongly BD-regular at `x*`. For every `ε > 0` (the page prints `ε ≥ 0`) there is `δ > 0` such that
for every `x` with `‖x - x*‖ ≤ δ` and every `V ∈ ∂_B F(x)`, `V` is nonsingular and
`‖x - V⁻¹F(x) - x*‖ ≤ ε ‖x - x*‖`, `‖F(x - V⁻¹F(x))‖ ≤ ε ‖F(x)‖`. -/
theorem corollary_3_2 {n : ℕ} (F : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
    (hF : LocallyLipschitz F) (xstar : EuclideanSpace ℝ (Fin n)) (hzero : F xstar = 0)
    (hss : NonsmoothNewton.Local.SemismoothAt F xstar) (hreg : StronglyBDRegularAt F xstar) :
    ∀ ε > 0, ∃ δ > 0, ∀ y : EuclideanSpace ℝ (Fin n), ‖y - xstar‖ ≤ δ →
      ∀ V ∈ NonsmoothNewton.Shared.bJac F y,
        (∃ W : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n), IsInverse V W) ∧
        ∀ W : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n), IsInverse V W →
          ‖y - W (F y) - xstar‖ ≤ ε * ‖y - xstar‖ ∧
          ‖F (y - W (F y))‖ ≤ ε * ‖F y‖ := by sorry

end QiNonsmoothEq.Local
Source
Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res. 18 (1993), p. 235, Corollary 3.2
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