Theorem 5.1, p. 238 — a descent method with ‖F(x^{k+1})‖ ≤ ‖F(x^k)‖ and ‖d^k‖ ≤ p‖F(x^k)‖ near x* converges to any BD-regular zero x* among its limit points
ProvedQiNonsmoothEq.Attraction.theorem_5_1Attraction theorem. Let be locally Lipschitz and B-differentiable. Let be generated by a descent direction method
satisfying
Let be a limiting (cluster) point of which is a zero of , and assume is BD-regular at : for all . Assume there are scalars , , such that for all , if then and
Then the whole sequence converges: .
The theorem needs neither semismoothness nor nonsingularity of generalized Jacobians: a BD-regular zero attracts every descent method whose steps are controlled by the residual near . Corollary 5.2 applies it to the damped Newton method, and §5 to the two algorithms of Han, Pang and Rangaraj.
Formalization Note The norm is the 2-norm. "Limiting point" means a cluster point of the sequence (some subsequence converges to ). The hypothesis for all is added: the page's "descent direction method" carries nonnegative step sizes implicitly, and its proof bounds by , which needs .
import Mathlib import Definitions.Def_NonsmoothNewton_Local_dirDeriv import Definitions.Def_QiNonsmoothEq_Attraction_Setting open Filter Topology NonsmoothNewton.Local
namespace QiNonsmoothEq.Attraction
/-- Qi 1993, Theorem 5.1, p. 238 (attraction theorem): for a locally Lipschitz, B-differentiable
`F : ℝⁿ → ℝⁿ` and a descent direction method `x^{k+1} = x^k + α_k d^k` with
`‖F(x^{k+1})‖ ≤ ‖F(x^k)‖` (5.1), if a limiting point `x*` of `{x^k}` is a BD-regular zero of `F`
and, near `x*`, `α_k ≤ s` and `‖d^k‖ ≤ p ‖F(x^k)‖` (5.2), then `x^k → x*`. -/
theorem theorem_5_1 {n : ℕ}
(F : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)) (hF : LocallyLipschitz F)
(hB : ∀ y, QiNonsmoothEq.Local.BDiffAt F y)
(x d : ℕ → EuclideanSpace ℝ (Fin n)) (α : ℕ → ℝ)
(hstep : ∀ k, x (k + 1) = x k + α k • d k) (hα : ∀ k, 0 ≤ α k)
(hdesc : ∀ k, ‖F (x (k + 1))‖ ≤ ‖F (x k)‖)
(xstar : EuclideanSpace ℝ (Fin n)) (hclu : MapClusterPt xstar atTop x)
(hzero : F xstar = 0) (hreg : BDRegularAt F xstar)
(δ₁ s p : ℝ) (hδ₁ : 0 < δ₁) (hs : 0 < s) (hp : 0 < p)
(hloc : ∀ k, ‖x k - xstar‖ ≤ δ₁ → α k ≤ s ∧ ‖d k‖ ≤ p * ‖F (x k)‖) :
Tendsto x atTop (𝓝 xstar) := by sorry
end QiNonsmoothEq.Attraction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.