Theorem 3.1, p. 234 — at a semismooth, strongly BD-regular zero, the ∂_B Newton method (3.2) is well defined and converges superlinearly, and ‖F‖ decreases superlinearly
ProvedQiNonsmoothEq.Local.theorem_3_1Let be locally Lipschitz, let be a solution of , and let be semismooth and strongly BD-regular at (every is nonsingular). Consider the Newton method
Then there is such that:
- (well defined) for every with , every is nonsingular, and the Newton point again satisfies ;
- (superlinear convergence) every sequence generated by (3.2) from , for any choice of , has all nonsingular, converges to , and
- (superlinear decrease of ) if moreover for all , then
Restricting the Newton matrices to the B-subdifferential instead of Clarke's generalized Jacobian replaces the nonsingularity of all of by the weaker strong BD-regularity; the theorem shows that local superlinear convergence survives, and (1.9) makes the method a descent method for near the zero.
Formalization Note A run of (3.2) is a pair of sequences with and ; nonsingularity of each is part of the conclusion. The radius is fixed before the run and serves every starting point and every choice of . The little- is Mathlib's IsLittleO along atTop. Local Lipschitz continuity is the paper's standing assumption (§1). The second paragraph of the theorem (quadratic convergence) is the separate item theorem_3_1_quadratic.
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
namespace QiNonsmoothEq.Local
/-- Qi (1993), Theorem 3.1 (Local Convergence), first paragraph, p. 234. Let `x*` be a zero of
`F`, and let `F` be semismooth and strongly BD-regular at `x*`. Then there is `δ > 0` such that:
(1) for every `y` with `‖y - x*‖ < δ`, every `V ∈ ∂_B F(y)` is nonsingular and the Newton point
`y - V⁻¹F(y)` is again within `δ` of `x*` (the method (3.2) is well defined);
(2) every run of (3.2), `x^{k+1} = x^k - V_k⁻¹F(x^k)` with `V_k ∈ ∂_B F(x^k)` arbitrary, started
with `‖x^0 - x*‖ < δ`, has every `V_k` nonsingular, converges to `x*`, and superlinearly:
`‖x^{k+1} - x*‖ = o(‖x^k - x*‖)`;
(3) if moreover `F(x^k) ≠ 0` for all `k`, then `‖F(x^{k+1})‖ / ‖F(x^k)‖ → 0` (1.9). -/
theorem theorem_3_1 {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,
(∀ 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‖ < δ) ∧
(∀ (x : ℕ → EuclideanSpace ℝ (Fin n))
(V : ℕ → EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n)),
IsBDNewtonRun F x V → ‖x 0 - xstar‖ < δ →
(∀ k, ∃ W : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n),
IsInverse (V k) W) ∧
Tendsto x atTop (𝓝 xstar) ∧
(fun k => x (k + 1) - xstar) =o[atTop] (fun k => x k - xstar) ∧
((∀ k, F (x k) ≠ 0) →
Tendsto (fun k => ‖F (x (k + 1))‖ / ‖F (x k)‖) atTop (𝓝 0))) := by sorry
end QiNonsmoothEq.Local
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.