Chapter 07 — Solving Nonlinear Least-Squares Problems

Proofs omitted. Hover over highlighted terms to see their Lean types.

Exercise 7.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Exercise 7.1 (1): starting from x^(0) = (0, 0)ᵀ, two Gauss-Newton steps reach the minimizer (1, 1)ᵀ.

open Matrix
local notation "Point" => EuclideanSpace ℝ (Fin 2)
local notation "ResidualVector" => EuclideanSpace ℝ (Fin 2)
local notation "JacobianMatrix" => Matrix (Fin 2) (Fin 2) ℝ
theorem exercise71GaussNewtonSecondIterate_eq :
    exercise71GaussNewtonSecondIterate = (WithLp.toLp 2 <| ![(1 : ℝ), 1])

Exercise 7.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Exercise 7.2 (4): repair note for the source typo. The residuals depend on three variables, so the book's x = (0, 0)ᵀ is interpreted on the dimensionally consistent ambient point exercise72ZeroPoint : ℝ³; at that point, J(x)ᵀ J(x) = ∇² f(x) does not hold.

open Matrix
local notation "Point" => EuclideanSpace ℝ (Fin 3)
local notation "ResidualVector" => EuclideanSpace ℝ (Fin 5)
theorem exercise72_jacobianGram_ne_hessianAtZero :
    Matrix.toEuclideanLin
        ((exercise72JacobianMatrix exercise72ZeroPoint).transpose *
          exercise72JacobianMatrix exercise72ZeroPoint) ≠
      fderiv ℝ (gradient exercise72Objective) exercise72ZeroPoint

Exercise 7.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Exercise 7.3 (3): estimate (7.2.9) for the inverse Gram field x ↦ (gaussNewtonNormalMatrix r x)⁻¹ at xStar, assuming (7.2.7) plus neighborhood positive definiteness of gaussNewtonNormalMatrix r x.

open scoped Matrix.Norms.Elementwise

-- Owner reuse: `Theorem_7_2_2` already owns the Chapter 7 least-squares objective, Jacobian,
-- correction matrix, and Gauss-Newton normal matrix. This exercise keeps only the local estimate
-- predicates and the source-facing statements that use those canonical owners.
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Residual" => EuclideanSpace ℝ (Fin m)
theorem exercise73_inverseJacobianGram_localEstimate
    (r : Point → Residual) (xStar : Point)
    (hRegular : LocalDifferenceEstimateAt (gaussNewtonNormalMatrix r) xStar)
    (hPosDef :
      ∃ δ : {δ : ℝ // 0 < δ},
        ∀ x : Point,
          x ∈ Metric.ball xStar δ.1 →
            (gaussNewtonNormalMatrix r x).PosDef) :
    LocalDifferenceEstimateAt (fun x : Point ↦ (gaussNewtonNormalMatrix r x)⁻¹) xStar

Exercise 7.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Exercise 7.4: let run be the exact-stopping/stuttering infinite-run reading of a trust-region type Levenberg-Marquardt Algorithm 7.3.9 run for f(x) = (1 / 2) * ∑ i, (r_i(x))^2. Assume r is twice continuously differentiable, so residualJacobianMatrix r is the source Jacobian field and the source least-squares correction and Hessian owners S[r](xStar) and G[r](xStar) retain their intended meaning, and the nonlinear least-squares objective f is also twice continuously differentiable. If the level set L(x₀) = {x | f x ≤ f x₀} is bounded, the iterate sequence run converges to xStar, the least-squares Hessian G(xStar) is positive definite, and S(xStar) = ∑ i, r_i(xStar) • ∇² r_i(xStar) = 0, then run converges to xStar with quadratic rate, encoded by the canonical owner HasQuadraticConvergenceTo run xStar.

open Filter
open scoped LeastSquares
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ResidualVector" => EuclideanSpace ℝ (Fin m)

-- Domain sampling for this refine pass:
-- * primary domain: trust-region Levenberg-Marquardt local quadratic convergence for nonlinear
--   least squares on Euclidean spaces;
-- * sampled owner declarations in the minimal Chapter 7 closure:
--   `TrustRegionLevenbergMarquardtAlgorithm`,
--   `TrustRegionLevenbergMarquardtAlgorithm.IsExactStoppingRun`,
--   `initialSublevelSet`,
--   `G[_](_)`,
--   `S[_](_)`,
--   `HasQuadraticConvergenceTo`;
-- * best owner abstraction: the canonical Chapter 7 trust-region algorithm object together with
--   the exact-stopping/stuttering Chapter 7 trust-region run owner together with the Chapter 3
--   quadratic-convergence owner;
-- * primitive data: the residual map `r` and the recorded algorithm run `run`;
-- * derived API removed here: the duplicate local trust-region objective/model/feasible-set
--   wrappers, the duplicate local algorithm record, the ad hoc Hessian alias, and the parallel
--   `qQuadraticConvergenceTo` rate predicate.
theorem trustRegionLevenbergMarquardt_qQuadraticConvergence_of_tendsto
    (r : Point → ResidualVector)
    (run : TrustRegionLevenbergMarquardtAlgorithm r (residualJacobianMatrix r))
    (hRun : run.IsExactStoppingRun)
    (xStar : Point)
    (hResidualC2 : ContDiff ℝ 2 r)
    (hLevelSetBounded :
      Bornology.IsBounded (initialSublevelSet (nonlinearLeastSquaresObjective r) run.x0))
    (hTendsto : Tendsto run atTop (nhds xStar))
    (hHessianPosDef : (G[r](xStar)).PosDef)
    (hCorrectionVanishes : S[r](xStar) = 0) :
    HasQuadraticConvergenceTo run xStar

Exercise 7.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Exercise 7.5: for r : ResidualVector, J : JacobianMatrix, and μ > 0, the explicit damped least-squares solution minimizes Moré's stacked damped least-squares objective in the identity-scaling specialization d = 1. In the source notation this is the minimizer of s ↦ ‖W s + y‖², where W = [J; √μ I] and y = [r; 0].

open Matrix
variable {m n : ℕ}
local notation "StepVector" => EuclideanSpace ℝ (Fin n)
local notation "ResidualVector" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ

-- Domain sampling:
-- * primary domain: damped least-squares / Levenberg-Marquardt stacked residual minimization
-- * sampled chapter owners:
--   `moreDampedLeastSquaresMatrix`
--   `moreDampedLeastSquaresOffset`
--   `moreDampedLeastSquaresObjective`
--   `IsMoreDampedLeastSquaresStep`
-- * core/canonical owner here: `IsMoreDampedLeastSquaresStep`
-- * bridge/view layer here: the Exercise 7.5 identity-scaling specialization `d = 1` together
--   with the explicit closed-form step on `EuclideanSpace ℝ (Fin n)` via `Matrix.toEuclideanLin`
-- * primitive data: the Jacobian `J`, residual vector `r`, and damping parameter `μ`
-- * derived API removed here: duplicate local identity-scaling matrix/offset/objective owners
theorem dampedLeastSquaresStep_isMoreDampedLeastSquaresStep
    (J : JacobianMatrix) (r : ResidualVector) (μ : ℝ) (hμ : 0 < μ) :
    IsMoreDampedLeastSquaresStep J r (1 : Fin n → ℝ) μ
      (-((Jᵀ * J + μ • (1 : MatrixN))⁻¹).toEuclideanLin
        (trustRegionLevenbergMarquardtGradient J r))

Exercise 7.6

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Exercise 7.6 (1): fixing a Jacobian J of full column rank and a residual vector r at one least-squares iterate, if s μ solves the regularized normal equation for every nonnegative damping parameter μ, then the Levenberg-Marquardt direction s μ tends to the Gauss-Newton direction s 0 as the damping parameter tends to 0 through positive values.

open Filter Matrix NormedSpace -- Domain sampling for this item: -- * primary domain: finite-dimensional least-squares Gauss-Newton and Levenberg-Marquardt -- directions at a fixed iterate; -- * sampled owner-family declarations: -- `solvesLevenbergMarquardtNormalEquation`, -- `levenbergMarquardtStep_norm_strictAntiOn`, -- `Algorithm_7_3_9.trustRegionLevenbergMarquardtGradient`, -- `Matrix.toEuclideanLin`, -- `NormedSpace.normalize` -- * source-facing layer here: the asymptotic statements for the fixed-iterate directions; -- * core/canonical owners reused here: `solvesLevenbergMarquardtNormalEquation` for the damped -- normal-equation semantics, `trustRegionLevenbergMarquardtGradient` for the least-squares -- gradient, and `NormedSpace.normalize` for normalized directions -- * primitive data reused from upstream: a step family solving the regularized normal equations -- for nonnegative damping parameters and the least-squares gradient -- * derived API: no local normalization wrapper is kept, since mathlib already owns it. variable {m n : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "Residual" => EuclideanSpace ℝ (Fin m) local notation "Jacobian" => Matrix (Fin m) (Fin n) ℝ local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ theorem levenbergMarquardtDirection_tendsto_gaussNewtonDirection (J : Jacobian) (r : Residual) (s : ℝ → Point) (hfullRank : Function.Injective (Matrix.toEuclideanLin J)) (h_step : ∀ ⦃μ : ℝ⦄, 0 ≤ μ → solvesLevenbergMarquardtNormalEquation J (trustRegionLevenbergMarquardtGradient J r) μ (s μ)) : Filter.Tendsto s (nhdsWithin 0 (Set.Ioi (0 : ℝ))) (nhds (s 0))

7.1 — Introduction

Definition 7.1.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Definition 7.1-extra-1 (1): for a residual map r : ℝ^n → ℝ^m, the nonlinear least-squares objective is x ↦ (1 / 2) * r(x)ᵀ r(x).

open scoped BigOperators -- Semantic recall: `lean_leansearch` surfaced the canonical `EuclideanSpace` owner and norm/sum -- identities, while nearby Chapter 3 and 5 files already formalize optimization problems on -- `EuclideanSpace ℝ (Fin n)` with `EuclideanSpace.equiv` for coordinate formulas. This file keeps -- that ambient representation for the book's `ℝ^n` and `ℝ^m` least-squares setup. variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "Residual" => EuclideanSpace ℝ (Fin m) local notation "residualCoords" => (EuclideanSpace.equiv (Fin m) ℝ) def nonlinearLeastSquaresObjective (r : Point → Residual) (x : Point) : ℝ := (1 / 2 : ℝ) * dotProduct (residualCoords (r x)) (residualCoords (r x))

Notation 7.1.extra.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Gradient formula for Chapter07 Notation 7.1-extra-2: if r is differentiable at x, then g(x) = J(x)ᵀ r(x).

open Filter Matrix
open scoped BigOperators LeastSquares
variable {m n : ℕ}

-- Local declaration justification (source-local notation): this numbered item uses the
-- source's fixed Euclidean domain notation throughout and keeps the aliases local.
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Residual" => EuclideanSpace ℝ (Fin m)
local notation "residualCoords" => (EuclideanSpace.equiv (Fin m) ℝ)
theorem leastSquaresObjective_gradient_eq
    (r : Point → Residual) (x : Point) (hr : DifferentiableAt ℝ r x) :
    gradient (nonlinearLeastSquaresObjective r) x = g[r](x)

Algorithm 7.1.extra.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Algorithm 7.1-extra-3: for the nonlinear least-squares problem (7.1.1) with residual map r, the Newton update at x is x - G(x)⁻¹ g(x), where g(x) = leastSquaresGradient r x = J(x)ᵀ r(x) and G(x) = leastSquaresHessianMatrix r x = J(x)ᵀ * J(x) + S(x) with S(x) = leastSquaresCorrectionMatrix r x.

open Matrix
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Residual" => EuclideanSpace ℝ (Fin m)

-- Semantic recall: the source-facing Newton update belongs on top of the Chapter 7 least-squares
-- owners from `Theorem_7_2_2`, rather than duplicating their calculus definitions locally.
def nonlinearLeastSquaresNewtonStep
    (r : Point → Residual) (x : Point)
    [Invertible (leastSquaresHessianMatrix r x)] : Point :=
  x - Matrix.toEuclideanLin (⅟ (leastSquaresHessianMatrix r x)) (leastSquaresGradient r x)

Definition 7.1.extra.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Definition 7.1-extra-4: the textbook terminology "small residual problem" and "large residual problem" is qualitative commentary on whether the canonical correction term S(x) = leastSquaresCorrectionMatrix r x is negligible at the point under discussion. This item introduces no new mathematical owner: the Chapter 7 source-facing object is already the correction term leastSquaresCorrectionMatrix, and later quantitative statements in the chapter reuse that owner directly.

variable {m n : ℕ}
#check leastSquaresCorrectionMatrix

7.2 — Gauss-Newton Method

Algorithm 7.2.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Algorithm 7.2.1: a Gauss-Newton iteration for residual map r and Jacobian map J starts from x₀, uses a tolerance ε, stops whenever ‖J(xₖ)ᵀ r(xₖ)‖ ≤ ε, and otherwise chooses a step sₖ solving J(xₖ)ᵀ J(xₖ) sₖ = -J(xₖ)ᵀ r(xₖ) and updates xₖ₊₁ = xₖ + sₖ; once the stopping test fires, the iterate sequence stays constant.

open Matrix
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Residual" => EuclideanSpace ℝ (Fin m)
local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ

-- Domain sampling for this item:
-- * primary domain: finite-dimensional nonlinear least-squares Gauss-Newton iteration data with
--   a source-faithful stopping rule;
-- * sampled declarations in the owner family:
--   `Matrix.toEuclideanLin`,
--   `SunYuanOptimizationTheoryMethods.Chap07.Theorem_7_2_2.leastSquaresGradient`,
--   `SunYuanOptimizationTheoryMethods.Chap03.Algorithm_3_2_3.
--      NewtonMethodWithLineSearch.IsTerminalIndex`,
--   `SunYuanOptimizationTheoryMethods.Chap05.Algorithm_5_7_2.LBFGSMethod.terminatedAt`;
-- * source-facing owner here: the stopping-aware Gauss-Newton iteration object;
-- * core/canonical owner reused here: the Chapter 7 least-squares gradient owner
--   `leastSquaresGradient` together with the Euclidean-space matrix action
--   `Matrix.toEuclideanLin`;
-- * primitive data here: iterate and step sequences together with the active-step normal equation
--   and update law, plus the constant-tail rule after the stopping test fires;
-- * derived API here: the stopping/active predicates, their complementarity, the terminal-index
--   view, and bundled active-step consequences.
structure GaussNewtonIteration
    (J : Point → JacobianMatrix) (r : Point → Residual) (x0 : Point) (ε : ℝ) where
  x : ℕ → Point
  step : ℕ → Point
  x_zero : x 0 = x0
  step_solves_normalEquation (k : ℕ) (hActive : ε < ‖gaussNewtonGradient J r (x k)‖) :
    (((J (x k))ᵀ * J (x k)) : MatrixN).toEuclideanLin (step k) =
      -gaussNewtonGradient J r (x k)
  next_eq_of_active (k : ℕ) (hActive : ε < ‖gaussNewtonGradient J r (x k)‖) :
    x (k + 1) = x k + step k
  next_eq_of_terminated (k : ℕ) (hTerm : ‖gaussNewtonGradient J r (x k)‖ ≤ ε) :
    x (k + 1) = x k

Theorem 7.2.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.2.2: let f(x) = nonlinearLeastSquaresObjective r x = (1 / 2) * ‖r x‖^2, assume r ∈ C², xStar is a local minimizer of the nonlinear least-squares problem, the Gauss-Newton iterates x k converge to xStar, J(xStar)ᵀ * J(xStar) is positive definite, the normal matrix remains positive definite in a neighborhood of xStar, and both G(x) = leastSquaresHessianMatrix r x and (J(x)ᵀ * J(x))⁻¹ = (gaussNewtonNormalMatrix r x)⁻¹ are Lipschitz in a neighborhood of xStar. Then the one-step error satisfies the source bound, with the matrix norms in the linear coefficient interpreted as Euclidean (ℓ₂) operator norms, `‖x_(k+1) - xStar‖ ≤ ‖(J(xStar)ᵀ * J(xStar))⁻¹‖ * ‖S(xStar)‖ * ‖x_k - xStar‖ + O(‖x_k - xStar‖^2)` in the standard eventual-inequality form.

open Filter Matrix
open scoped LeastSquares
open scoped Matrix.Norms.L2Operator
variable {m n : ℕ}

-- Local declaration justification (source-local notation): this source-facing theorem keeps the
-- chapter's point-space formulas readable while confining the alias to the current item file.
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Local declaration justification (source-local notation): the residual codomain alias mirrors
-- the source statement and is intentionally kept local to avoid exporting a generic notation.
local notation "Residual" => EuclideanSpace ℝ (Fin m)
theorem gaussNewton_errorNorm_eventually_le_linear_plus_quadratic
    (r : Point → Residual) (x : ℕ → Point) (xStar : Point)
    (hResidualC2 : ContDiff ℝ 2 r)
    (hLocalMin : IsLocalMin (nonlinearLeastSquaresObjective r) xStar)
    (hStep : ∀ k : ℕ, solvesGaussNewtonNormalEquation r (x k) (x (k + 1)))
    (hGramPosDef : (gaussNewtonNormalMatrix r xStar).PosDef)
    (hTendsto : Tendsto x atTop (nhds xStar))
    (hNormalMatrixPosDef :
      ∃ δ > 0, ∀ y : Point,
        y ∈ Metric.ball xStar δ →
          (gaussNewtonNormalMatrix r y).PosDef)
    (hHessianLipschitz :
      ∃ δ > 0, ∃ L > 0, ∀ x y : Point,
        x ∈ Metric.ball xStar δ →
        y ∈ Metric.ball xStar δ →
          ‖G[r](x) - G[r](y)‖ ≤ L * ‖x - y‖)
    (hInverseLipschitz :
      ∃ δ > 0, ∃ L > 0, ∀ x y : Point,
        x ∈ Metric.ball xStar δ →
        y ∈ Metric.ball xStar δ →
          ‖(gaussNewtonNormalMatrix r x)⁻¹ - (gaussNewtonNormalMatrix r y)⁻¹‖ ≤
            L * ‖x - y‖) :
    ∃ C > 0, ∀ᶠ k : ℕ in atTop,
      ‖x (k + 1) - xStar‖ ≤
        gaussNewtonLinearErrorCoefficient r xStar * ‖x k - xStar‖ +
          C * ‖x k - xStar‖ ^ (2 : ℕ)

Theorem 7.2.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.2.3: under the source assumptions on the open convex set D, the residual map r is C² on D, the Jacobian J(x) satisfies (7.2.16) and (7.2.17), the stationarity condition is g(xStar) = 0, the smallest-eigenvalue hypothesis is imposed on gaussNewtonNormalMatrix r xStar, and the gap hypotheses 0 ≤ σ, 1 < c, and c * σ < lam hold. Then there exists a radius ε > 0 such that every x0 ∈ Metric.ball xStar ε admits a Gauss-Newton iterate family x_k staying in D, solving the canonical normal equation at each step, converging linearly to xStar in the canonical sense HasLinearConvergenceTo x xStar, satisfying the source estimates (7.2.18) and (7.2.19), and strictly decreasing the error norm whenever the current iterate is not already the fixed point xStar.

open Filter Matrix
open scoped LeastSquares Matrix.Norms.L2Operator
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Residual" => EuclideanSpace ℝ (Fin m)
variable (r : Point → Residual)

-- Domain sampling for this file:
-- * primary domain: local existence and convergence statements for Gauss-Newton iterate
--   sequences;
-- * sampled owners reused here:
--   `nonlinearLeastSquaresObjective`,
--   `residualJacobianMatrix`,
--   `gaussNewtonNormalMatrix`,
--   `leastSquaresGradient`,
--   `solvesGaussNewtonNormalEquation`,
--   `Matrix.spectrum`;
-- * source/core/bridge triage:
--   - source-facing layer here: the existence theorem for an iterate family `x_k`;
--   - core/canonical owners reused here: the Chapter 7 objective and residual Jacobian owners;
--   - bridge/view layer here: the local one-step error estimates deduced from those core owners;
-- * primitive data here: the domain `D`, residual map `r`, initial point `x0`, and iterate
--   family `x`;
-- * derived API here: the canonical linear-convergence owner `HasLinearConvergenceTo x xStar`
--   together with the source pointwise error bounds `(7.2.18)` and `(7.2.19)`. The one-step
--   semantics themselves are reused from the Chapter 7 owner
--   `solvesGaussNewtonNormalEquation` rather than repackaged in a second owner structure.
theorem gaussNewtonLocalConvergence_of_smallestEigenvalueGap
    (D : Set Point) (r : Point → Residual) (xStar : Point) (lam σ α γ c : ℝ)
    (hOpen : IsOpen D)
    (hConvex : Convex ℝ D)
    (hxStar : xStar ∈ D)
    (hResidualC2 : ContDiffOn ℝ 2 r D)
    (hJLipschitz :
      ∀ x ∈ D, ∀ y ∈ D,
        ‖(Matrix.toEuclideanLin
            (J[r](x) - J[r](y))).toContinuousLinearMap‖ ≤
          γ * ‖x - y‖)
    (hJBound :
      ∀ x : Point, x ∈ D →
        ‖(Matrix.toEuclideanLin (J[r](x))).toContinuousLinearMap‖ ≤ α)
    (hσ_nonneg : 0 ≤ σ)
    (hStationary : g[r](xStar) = 0)
    (hSmallest :
      IsLeast (spectrum ℝ (gaussNewtonNormalMatrix r xStar)) lam)
    (hResidualLinearization :
      ∀ x : Point, x ∈ D →
        ‖Matrix.toEuclideanLin
            ((J[r](x) - J[r](xStar))ᵀ) (r xStar)‖ ≤
          σ * ‖x - xStar‖)
    (hc_lower : 1 < c)
    (hc_upper : c * σ < lam) :
    ∃ ε : ℝ, 0 < ε ∧
      ∀ x0 : Point, x0 ∈ Metric.ball xStar ε →
        ∃ x : ℕ → Point,
          x 0 = x0 ∧
            (∀ k : ℕ, x k ∈ D) ∧
            (∀ k : ℕ, solvesGaussNewtonNormalEquation r (x k) (x (k + 1))) ∧
            HasLinearConvergenceTo x xStar ∧
            (∀ k : ℕ,
              ‖x (k + 1) - xStar‖ ≤
                (c * σ / lam) * ‖x k - xStar‖ +
                  (c * α * γ / (2 * lam)) * ‖x k - xStar‖ ^ (2 : ℕ)) ∧
            (∀ k : ℕ,
              ‖x (k + 1) - xStar‖ ≤
                ((c * σ + lam) / (2 * lam)) * ‖x k - xStar‖) ∧
            ∀ k : ℕ, x k ≠ xStar → ‖x (k + 1) - xStar‖ < ‖x k - xStar‖

Theorem 7.2.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.2.4: keep the geometric and regularity hypotheses from Theorem 7.2.3. If r xStar = 0, then the residual-linearization condition is automatic with coefficient 0, so the only remaining spectral hypothesis is positive definiteness of the canonical Gauss-Newton normal matrix at xStar. Under these assumptions there exists ε > 0 such that every x0 ∈ Metric.ball xStar ε admits a Gauss-Newton iterate family x_k which stays in D, solves the canonical normal equation at each step, converges to xStar, and does so with Q-quadratic convergence rate in the canonical sense HasQuadraticConvergenceTo x xStar.

open Filter Matrix
open scoped LeastSquares
open scoped Matrix.Norms.Elementwise
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Residual" => EuclideanSpace ℝ (Fin m)
variable (r : Point → Residual)

-- Semantic recall: the canonical project owner for `Q`-quadratic convergence is
-- `HasQuadraticConvergenceTo` from Chapter 3. The Chapter 7 least-squares objective, Jacobian,
-- correction, Hessian, normal matrix, and step-equation owners already live in `Theorem_7_2_2`,
-- so this file reuses both the Chapter 3 convergence owner and the Chapter 7 Gauss-Newton owners
-- rather than keeping a parallel local rate predicate.
theorem gaussNewton_exists_qQuadraticConvergence_of_zeroResidual
    (D : Set Point) (xStar : Point) (α γ : ℝ)
    (hOpen : IsOpen D)
    (hConvex : Convex ℝ D)
    (hxStar : xStar ∈ D)
    (hResidualC2 : ContDiffOn ℝ 2 r D)
    (hJLipschitz :
      ∀ x ∈ D, ∀ y ∈ D,
        ‖(Matrix.toEuclideanLin
            (J[r](x) - J[r](y))).toContinuousLinearMap‖ ≤
          γ * ‖x - y‖)
    (hJBound :
      ∀ x : Point, x ∈ D →
        ‖(Matrix.toEuclideanLin (J[r](x))).toContinuousLinearMap‖ ≤ α)
    (hGramPosDef : (gaussNewtonNormalMatrix r xStar).PosDef)
    (hResidualZero : r xStar = 0) :
    ∃ ε : ℝ, 0 < ε ∧
      ∀ x0 : Point, x0 ∈ Metric.ball xStar ε →
        ∃ x : ℕ → Point,
          x 0 = x0 ∧
            (∀ k : ℕ, x k ∈ D) ∧
            (∀ k : ℕ, solvesGaussNewtonNormalEquation r (x k) (x (k + 1))) ∧
            HasQuadraticConvergenceTo x xStar

Example 7.2.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Example 7.2.5 (5): when |λ| > 1, the Gauss-Newton method can fail to converge to the minimizer x* = 0 from a nonzero starting value.

open Asymptotics
open scoped Topology

-- Domain sampling:
-- * primary domain: one-dimensional nonlinear least-squares Gauss-Newton updates;
-- * sampled owner declarations reused here:
--   `nonlinearLeastSquaresObjective`,
--   `solvesGaussNewtonNormalEquation`,
--   `Function.iterate`,
--   `Function.IsFixedPt`;
-- * core/canonical owner for the update semantics:
--   `solvesGaussNewtonNormalEquation (example725ResidualMap lam)`;
-- * primitive data kept here: the example residual map and its explicit point-level
--   Gauss-Newton update;
-- * derived API here: scalar-coordinate views, the objective formula, and orbit views.
theorem example725GaussNewtonOrbit_notTendsto_zero_of_one_lt_abs
    {lam : ℝ} (hlam : 1 < |lam|) :
    ∃ x0 : ℝ, x0 ≠ 0 ∧
        ¬ Filter.Tendsto (example725GaussNewtonOrbit lam x0) Filter.atTop (𝓝 (0 : ℝ))

Remark 7.2.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Under invertibility of the Gauss-Newton normal matrix, the zero-damping Levenberg-Marquardt direction is the textbook damped Gauss-Newton inverse formula.

open Filter Matrix
open scoped LeastSquares
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Residual" => EuclideanSpace ℝ (Fin m)

-- Domain sampling:
-- * primary domain: damped Gauss-Newton line-search iterations for nonlinear least squares;
-- * sampled owner declarations reused here:
--   `ArmijoParameters`,
--   `IsArmijoIndex`,
--   `IsNonmonotoneArmijoLineSearch`,
--   `levenbergMarquardtDirection`,
--   `nonlinearLeastSquaresObjective`,
--   `gaussNewtonNormalMatrix`,
--   `leastSquaresGradient`,
--   `solvesGaussNewtonNormalEquation`,
--   `initialSublevelSet`,
--   `nonmonotoneArmijoLineSearch_accumulationPoint_stationary`,
--   `IsStationaryPoint`,
--   `IsDescentDirectionAt`;
-- * best owner abstraction: the Chapter 7 residual-based least-squares owners
--   `solvesGaussNewtonNormalEquation` and the zero-damping
--   Levenberg-Marquardt direction `levenbergMarquardtDirection r 0`, together with the
--   Chapter 2 line-search owner `IsNonmonotoneArmijoLineSearch` specialized to memory `M = 0`;
-- * source/core/bridge triage:
--   - source-facing declarations kept here: the remark's Armijo/update/stationarity statements;
--   - core/canonical owners reused here: the Chapter 7 least-squares owners, the
--     zero-damping Levenberg-Marquardt direction, and the Chapter 2 line-search owner;
--   - bridge/view layer here: the explicit inverse formula for
--     `levenbergMarquardtDirection r 0 x` under invertibility, the corresponding full-step
--     Gauss-Newton normal-equation lemma, and the theorem turning the source Armijo/update data
--     into the canonical memory-zero nonmonotone Armijo owner;
-- * primitive data here: the iterate update, the accepted step sizes, and the accepted Armijo
--   exponents;
-- * derived API here: the memory-zero nonmonotone Armijo bridge and the
--   objective/stationarity consequences.
theorem levenbergMarquardtDirection_zero_eq_dampedGaussNewtonFormula
    (r : Point → Residual) (x : Point)
    (hInv : Invertible (gaussNewtonNormalMatrix r x)) :
    levenbergMarquardtDirection r 0 x =
      -((⅟ (gaussNewtonNormalMatrix r x)).toEuclideanLin (g[r](x)))

7.3 — Levenberg-Marquardt Method

Theorem 7.3.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.3.1: if the Gauss-Newton gradient Jᵀ.mulVec r is nonzero and, for each positive damping parameter μ, the step s μ satisfies the regularized normal equation (Jᵀ * J + μ • 1).mulVec (s μ) = -(Jᵀ.mulVec r), then the Euclidean norm ‖s μ‖ decreases strictly as μ increases on Set.Ioi 0.

open Matrix -- Domain sampling: -- * source-facing owner: `solvesLevenbergMarquardtNormalEquation` -- * sampled project declarations in this domain: -- `solvesLevenbergMarquardtNormalEquation` -- `levenbergMarquardtAngle_antitoneOn` -- `levenbergMarquardtRegularizedNormalMatrix` -- * core/canonical owner in this chapter: the regularized normal-equation relation, with the -- matrix family `Jᵀ * J + μ • 1` only as supporting data -- * primitive data: the Jacobian `J`, residual vector `r`, and a family of steps solving the -- regularized normal equations on the genuine positive damping domain -- * derived API removed here: the redundant total inverse-based step definition on all `μ : ℝ` -- whose values outside the positive regime were not source-faithful variable {m n : ℕ} local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ local notation "ResidualVector" => EuclideanSpace ℝ (Fin m) local notation "Step" => EuclideanSpace ℝ (Fin n) local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ theorem levenbergMarquardtStep_norm_strictAntiOn (J : JacobianMatrix) (r : ResidualVector) (s : ℝ → Step) (hgrad : Jᵀ.mulVec r ≠ 0) (h_step : ∀ ⦃μ : ℝ⦄, 0 < μ → solvesLevenbergMarquardtNormalEquation J (Jᵀ.mulVec r) μ (s μ)) : StrictAntiOn (fun μ : ℝ ↦ ‖s μ‖) (Set.Ioi 0)

Theorem 7.3.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.3.2: fix a Jacobian matrix J and a vector g, and for each damping parameter μ > 0 let s μ solve the regularized normal equation (Jᵀ * J + μ • 1).mulVec (s μ) = -g. Then the angle between s μ and -g is antitone on Set.Ioi 0, so it does not increase as μ increases.

open Matrix variable {m n : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ -- Semantic recall: `lean_leansearch` surfaced `InnerProductGeometry.angle` and `AntitoneOn`, -- while Chapter 7 already owns the source regularized-normal-equation predicate -- `solvesLevenbergMarquardtNormalEquation`. This item keeps the direct-gradient theorem surface -- and reuses that owner. theorem levenbergMarquardtAngle_antitoneOn (J : JacobianMatrix) (g : Point) (s : ℝ → Point) (h_step : ∀ ⦃μ : ℝ⦄, 0 < μ → solvesLevenbergMarquardtNormalEquation J g μ (s μ)) : AntitoneOn (fun μ : ℝ ↦ InnerProductGeometry.angle (s μ) (-g)) (Set.Ioi 0)

Theorem 7.3.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.3.3: if μ > 0 and s_k satisfies the regularized normal equation (Jᵀ * J + μ • 1).mulVec s_k = -(Jᵀ.mulVec r), then s_k is a global solution of the subproblem min q^(k) (s) = (1 / 2) * ‖J s + r‖₂² subject to ‖s‖ ≤ ‖s_k‖, formalized with the Euclidean residual Matrix.toEuclideanLin J s + r.

open Matrix variable {m n : ℕ} -- Semantic recall: Chapter 7 already owns the regularized-normal-equation predicate -- `solvesLevenbergMarquardtNormalEquation` and the source-faithful trust-region least-squares -- surface from `Theorem_7_3_4`, namely the Euclidean residual objective -- `s ↦ (1 / 2) * ‖Matrix.toEuclideanLin J s + r‖²` on the canonical closed ball -- `Metric.closedBall 0 ‖s_k‖`. This item is the source-facing special case with radius `‖s_k‖`. theorem levenbergMarquardtStep_isMinOn_ball_of_regularizedNormalEquation (J : Matrix (Fin m) (Fin n) ℝ) (r : EuclideanSpace ℝ (Fin m)) (μ : ℝ) (sk : EuclideanSpace ℝ (Fin n)) (hμ : 0 < μ) (hsk : (Jᵀ * J + μ • (1 : Matrix (Fin n) (Fin n) ℝ)).mulVec sk = -(Jᵀ.mulVec r)) : IsMinOn (fun s : EuclideanSpace ℝ (Fin n) ↦ ((1 : ℝ) / 2) * ‖Matrix.toEuclideanLin J s + r‖ ^ (2 : ℕ)) (Metric.closedBall 0 ‖sk‖) sk

Theorem 7.3.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.3.4: the vector sk solves the constrained least-squares problem min (1 / 2) * ‖J s + r‖₂² subject to ‖s‖ ≤ Δ, formalized with the Euclidean residual Matrix.toEuclideanLin J s + r. Then sk is feasible and minimizes that model on Metric.closedBall 0 Δ if and only if there exists μ ≥ 0 such that (Jᵀ * J + μ • 1).mulVec sk = -(Jᵀ.mulVec r), μ * (Δ - ‖sk‖) = 0, and ‖sk‖ ≤ Δ.

open Matrix variable {m n : ℕ} -- Local declaration justification (source-local notation): this item fixes the Chapter 7 -- least-squares trust-region ambient spaces `EuclideanSpace ℝ (Fin n)` and -- `EuclideanSpace ℝ (Fin m)`, and these short textbook names are only used to keep the local -- KKT formulas readable without exporting item-specific aliases. local notation "StepVector" => EuclideanSpace ℝ (Fin n) -- Local declaration justification (source-local notation): this file uses the residual-space -- alias only for the source-local LM formulas, so keeping it local avoids adding item-specific -- ambient-space vocabulary to the public API. local notation "ResidualVector" => EuclideanSpace ℝ (Fin m) -- Local declaration justification (source-local notation): this abbreviation names the fixed -- Hessian matrix ambient space used only by the source-local trust-region calculations. local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ -- Local declaration justification (source-local notation): this alias is only the Jacobian -- matrix ambient type for this theorem's local Chapter 7 formulas, not a reusable owner. local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ theorem levenbergMarquardtTrustRegionSolution_iff_exists_multiplier (J : JacobianMatrix) (r : ResidualVector) (Δ : ℝ) (hΔ : 0 < Δ) (sk : StepVector) : (sk ∈ Metric.closedBall 0 Δ ∧ IsMinOn (fun s : StepVector ↦ ((1 : ℝ) / 2) * ‖Matrix.toEuclideanLin J s + r‖ ^ (2 : ℕ)) (Metric.closedBall 0 Δ) sk) ↔ ∃ μ : ℝ, IsLevenbergMarquardtTrustRegionMultiplier J r Δ sk μ

Theorem 7.3.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.3.5: for (7.3.27) with the source damping matrix D(x) = diag (diag (J(x)ᵀ * J(x))), the spectral condition number of J(x)ᵀ * J(x) + μ • D(x) is a non-increasing function of μ for positive damping parameters μ; in the singular case, this source-facing condition-number owner takes value ⊤, so no separate positive-definiteness witness is exposed in the theorem statement.

open Matrix
variable {m n : ℕ}
theorem levenbergMarquardtConditionNumber_antitone
    (J : JacobianMatrix m n)
    (hn : 0 < n) :
    Antitone
      (sourceLevenbergMarquardtExtendedConditionNumber J hn)

Theorem 7.3.6

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.3.6: let x_k be a sequence generated by the scaled Levenberg-Marquardt method with Armijo rule for the nonlinear least-squares objective attached to r, using the canonical Chapter 7 Jacobian owner. If a subsequence x ∘ φ converges to xStar, and the corresponding subsequence of regularized normal matrices gaussNewtonNormalMatrix r (x_(φ i)) + μ_(φ i) • D(x_(φ i)) converges to a positive definite matrix P, the residual map is C¹ at xStar, and each iterate x_k carries an actual Jacobian in the source sense used by the Levenberg-Marquardt update, then the canonical least-squares gradient at the accumulation point vanishes: g[r](xStar) = 0.

open Filter Matrix
open scoped LeastSquares
variable {m n : ℕ}

-- Local declaration justification (source-local notation): the theorem uses the chapter's fixed
-- Euclidean parameter space notation while the reusable least-squares owners now come from
-- `Theorem_7_2_2`.
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Local declaration justification (source-local notation): the residual codomain shorthand is
-- kept local to preserve the source-facing theorem text.
local notation "Residual" => EuclideanSpace ℝ (Fin m)
theorem scaledLevenbergMarquardtArmijo_accumulationPoint_g_eq_zero
    (r : Point → Residual) (D : Point → MatrixN n)
    (x : ℕ → Point) (μ α : ℕ → ℝ) (mIndex : ℕ → ℕ)
    (run :
      IsScaledLevenbergMarquardtArmijoSequence
        (nonlinearLeastSquaresObjective r)
        (leastSquaresGradient r)
        (residualJacobianMatrix r) r D x μ α mIndex)
    {xStar : Point} {φ : ℕ → ℕ} {P : MatrixN n}
    (hφ : StrictMono φ)
    (hxStar : Tendsto (x ∘ φ) atTop (nhds xStar))
    (hr : ContDiffAt ℝ 1 r xStar)
    (hJacobian_run : ∀ k : ℕ, DifferentiableAt ℝ r (x k))
    (hP : P.PosDef)
    (hP_lim :
      Tendsto
        (fun i : ℕ ↦
          gaussNewtonNormalMatrix r (x (φ i)) + μ (φ i) • D (x (φ i)))
        atTop (nhds P)) :
    g[r](xStar) = 0

Theorem 7.3.7

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.3.7: let x_k be generated by the Levenberg-Marquardt method for the nonlinear least-squares objective attached to r. Assume every level set L(x̄) = {x | f x ≤ f x̄} of f is closed and bounded, for every objective value c the stationary set {x | IsStationaryPoint f x ∧ f x = c} is finite, every Gram matrix J(x)ᵀ * J(x) built from the Jacobian of r is positive definite, and the damping sequence μ_k is bounded above. Then the whole iterate sequence converges to a stationary point of f.

open Filter Matrix
open scoped Topology
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Residual" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ

-- Semantic recall: `lean_leansearch` surfaced `IsCompact.tendsto_subseq` and
-- `tendsto_nhds_of_unique_mapClusterPt` as the canonical sequence-convergence API. This file
-- reuses the Chapter 7 scaled Levenberg-Marquardt owners from `Theorem_7_3_6` and keeps only
-- the remaining source-facing global-convergence assumptions local.
theorem levenbergMarquardt_tendsto_stationaryPoint_of_finite_sameValueStationaryPoints
    (r : Point → Residual) (x : ℕ → Point) (μ : ℕ → ℝ)
    (run : IsLevenbergMarquardtSequence r x μ)
    (hLevelClosed :
      ∀ xBar : Point,
        IsClosed (initialSublevelSet (nonlinearLeastSquaresObjective r) xBar))
    (hLevelBounded :
      ∀ xBar : Point,
        Bornology.IsBounded (initialSublevelSet (nonlinearLeastSquaresObjective r) xBar))
    (hSameValueFinite :
      ∀ c : ℝ,
        Set.Finite
          (levenbergMarquardtSameValueStationaryPoints (nonlinearLeastSquaresObjective r) c))
    (hGramPosDef :
      ∀ xStar : Point, (gaussNewtonNormalMatrix r xStar).PosDef)
    (hMuBoundedAbove : ∃ M : ℝ, ∀ k : ℕ, μ k ≤ M) :
    ∃ xStar : Point,
      Tendsto x atTop (nhds xStar) ∧
        IsStationaryPoint (nonlinearLeastSquaresObjective r) xStar

Theorem 7.3.8

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.3.8 (1): let x_k be a Levenberg-Marquardt Armijo sequence for the canonical nonlinear least-squares objective attached to r, recorded by the source-facing owner IsLevenbergMarquardtArmijoSequence. Assume the iterate sequence converges to xStar, the Gauss-Newton normal matrix at xStar has positive smallest Hermitian eigenvalue, the correction matrix induces the local rate ratio levenbergMarquardtLocalRateRatio r xStar hn hCorrectionSymm < 1, run.β < (1 - levenbergMarquardtLocalRateRatio r xStar hn hCorrectionSymm) / 2, and μ k → 0. Then the accepted step size is eventually full, i.e. α_k = 1 for all sufficiently large k.

open Filter Matrix
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Residual" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ

-- Domain sampling for this file:
-- * primary domain: finite-dimensional nonlinear least-squares Levenberg-Marquardt local rate;
-- * sampled owner declarations:
--   `Chapter07.Theorem_7_3_5.smallestHermitianEigenvalue`,
--   `IsArmijoIndex`,
--   `leastSquaresGradient`,
--   `leastSquaresCorrectionMatrix`,
--   `IsLevenbergMarquardtSequence`,
--   `levenbergMarquardtDirection`;
-- * source/core/bridge triage:
--   - source-facing owner introduced here: the identity-scaled Levenberg-Marquardt Armijo run
--     data specific to Theorem 7.3.8;
--   - core/canonical owners reused here: the Chapter 2 Armijo-index owner, the Chapter 7
--     least-squares objective/gradient owners, and the Chapter 7 base Levenberg-Marquardt
--     sequence owner from Theorem 7.3.7;
--   - bridge/view kept here: the named local-rate ratio `levenbergMarquardtLocalRateRatio`
--     expressing the source quantity `τ = M / l` directly through the canonical Hermitian
--     eigenvalue API;
-- * primitive data kept in this file: the iterate/update sequences, accepted exponents, accepted
--   Armijo parameters, limit point, and the local spectral data at `xStar`;
-- * derived API kept in this file: inherited Armijo parameter bounds, accepted-exponent
--   companions, the source-semantic run expansion, and the eventual full-step, local-rate, and
--   strict-local-minimum conclusions of Theorem 7.3.8.
variable {r : Point → Residual} {x : ℕ → Point} {μ α : ℕ → ℝ} {mIndex : ℕ → ℕ}
variable {xStar : Point}
theorem levenbergMarquardt_stepsize_eventually_eq_one
    (run : IsLevenbergMarquardtArmijoSequence r x μ α mIndex)
    (hTendsto : Tendsto x atTop (nhds xStar))
    (hn : 0 < n)
    (hCorrectionSymm : (leastSquaresCorrectionMatrix r xStar).IsSymm)
    (hGram_smallest_pos :
      0 <
        smallestHermitianEigenvalue
          (isHermitian_conjTranspose_mul_self (residualJacobianMatrix r xStar))
          hn)
    (hRate_lt_one : levenbergMarquardtLocalRateRatio r xStar hn hCorrectionSymm < 1)
    (hBeta_lt :
      run.β < (1 - levenbergMarquardtLocalRateRatio r xStar hn hCorrectionSymm) / 2)
    (hMuTendsto : Tendsto μ atTop (nhds 0)) :
    ∃ N : ℕ, ∀ k ≥ N, α k = 1

Algorithm 7.3.9

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Algorithm 7.3.9: a trust-region type Levenberg-Marquardt algorithm for the nonlinear least-squares objective attached to r and matrix field J consists of an initial point x₀, an outer radius bound ΔBar, an initial trust-region radius Δ₀ ∈ (0, ΔBar), parameters ε ≥ 0, 0 < η₁ ≤ η₂ < 1, 0 < γ₁ < 1 < γ₂, and an approximate-solution fraction β₂ ∈ (0, 1], together with a sequence of accepted iterates x k, outer trust-region radii Δ k, inner retry radii trialRadius k j, trial steps step k j, and acceptance indices acceptIndex k. At every active outer iteration with ε < ‖J(x_k)ᵀ r(x_k)‖, the inner attempt j = 0 starts with radius Δ_k, and Step 3 is recorded directly on the canonical Chapter 6 trust-region subproblem built from J (x k), r (x k), and trialRadius k j. The source gradient J(x_k)ᵀ r(x_k) and the trial radius belong to that owner by construction, so feasibility and strict positivity of the predicted reduction become owner-level derived consequences instead of primitive packaged data. Rejected trials satisfy ρ_(k,j) < η₁ and update the next retry radius by γ₁ * trialRadius k j, the accepted trial j = acceptIndex k satisfies η₁ ≤ ρ_(k,j), the next iterate is x_(k + 1) = x_k + s_(k,j), and the next outer radius is min (γ₂ * trialRadius k j) ΔBar exactly in the source branch η₂ ≤ ρ_(k,j) with ‖s_(k,j)‖ = trialRadius k j, otherwise trialRadius k j.

open Matrix variable {m n : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ResidualVector" => EuclideanSpace ℝ (Fin m) local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ -- Domain-style sampling for this refine pass: -- * primary domain: trust-region Levenberg-Marquardt subproblems for nonlinear least squares on -- Euclidean spaces; -- * sampled owner declarations in the minimal closure: -- `nonlinearLeastSquaresObjective`, -- `TrustRegionSubproblem`, -- `TrustRegionSubproblem.feasibleSet`, -- `TrustRegionSubproblem.reductionRatio`; -- * best owner abstraction: Chapter 6 already owns the canonical trust-region quadratic-model -- package `TrustRegionSubproblem`, while Chapter 7 already owns the nonlinear least-squares -- objective `nonlinearLeastSquaresObjective`; -- * source/core/bridge triage: -- - source-facing: the explicit least-squares gradient and model `s ↦ (1 / 2) * ‖J s + r‖²`; -- - core/canonical: `TrustRegionSubproblem`; -- - bridge/view: the Step-3 least-squares data determine a canonical `TrustRegionSubproblem`, -- and the algorithm records that owner rather than a parallel local wrapper. structure TrustRegionLevenbergMarquardtAlgorithm (r : Point → ResidualVector) (J : Point → JacobianMatrix) where ε : ℝ η1 : ℝ η2 : ℝ γ1 : ℝ γ2 : ℝ β₂ : ℝ x0 : Point ΔBar : ℝ Δ0 : ℝ x : ℕ → Point Δ : ℕ → ℝ acceptIndex : ℕ → ℕ trialRadius : ℕ → ℕ → ℝ step : ℕ → ℕ → Point epsilon_nonneg : 0 ≤ ε eta1_pos : 0 < η1 eta1_le_eta2 : η1 ≤ η2 eta2_lt_one : η2 < 1 gamma1_mem : γ1 ∈ Set.Ioo (0 : ℝ) 1 gamma2_gt_one : 1 < γ2 beta2_mem : β₂ ∈ Set.Ioc (0 : ℝ) 1 deltaBar_pos : 0 < ΔBar delta0_mem : Δ0 ∈ Set.Ioo (0 : ℝ) ΔBar x_zero : x 0 = x0 delta_zero : Δ 0 = Δ0 delta_mem (k : ℕ) : Δ k ∈ Set.Ioc (0 : ℝ) ΔBar trialRadius_initial (k : ℕ) (_ : ε < trustRegionLevenbergMarquardtGradientNorm r J (x k)) : trialRadius k 0 = Δ k attempt_radius_mem (k j : ℕ) (_ : ε < trustRegionLevenbergMarquardtGradientNorm r J (x k)) (_ : j ≤ acceptIndex k) : trialRadius k j ∈ Set.Ioc (0 : ℝ) ΔBar attempt_isApproximateSolution (k j : ℕ) (hk : ε < trustRegionLevenbergMarquardtGradientNorm r J (x k)) (hj : j ≤ acceptIndex k) : (leastSquaresTrustRegionSubproblem (J (x k)) (r (x k)) (trialRadius k j) (attempt_radius_mem k j hk hj).1).isApproximateSolution β₂ (step k j) rejected_ratio_lt_eta1 (k j : ℕ) (hk : ε < trustRegionLevenbergMarquardtGradientNorm r J (x k)) (hj : j < acceptIndex k) : (leastSquaresTrustRegionSubproblem (J (x k)) (r (x k)) (trialRadius k j) (attempt_radius_mem k j hk (Nat.le_of_lt hj)).1).reductionRatio (x k) (nonlinearLeastSquaresObjective r) (step k j) < η1 rejected_radius_update (k j : ℕ) (_ : ε < trustRegionLevenbergMarquardtGradientNorm r J (x k)) (_ : j < acceptIndex k) : trialRadius k (j + 1) = γ1 * trialRadius k j accepted_ratio_ge_eta1 (k : ℕ) (hk : ε < trustRegionLevenbergMarquardtGradientNorm r J (x k)) : η1 ≤ (leastSquaresTrustRegionSubproblem (J (x k)) (r (x k)) (trialRadius k (acceptIndex k)) (attempt_radius_mem k (acceptIndex k) hk (le_rfl)).1).reductionRatio (x k) (nonlinearLeastSquaresObjective r) (step k (acceptIndex k)) iterate_update (k : ℕ) (_ : ε < trustRegionLevenbergMarquardtGradientNorm r J (x k)) : x (k + 1) = x k + step k (acceptIndex k) radius_update (k : ℕ) (hk : ε < trustRegionLevenbergMarquardtGradientNorm r J (x k)) : Δ (k + 1) = if η2 ≤ (leastSquaresTrustRegionSubproblem (J (x k)) (r (x k)) (trialRadius k (acceptIndex k)) (attempt_radius_mem k (acceptIndex k) hk (le_rfl)).1).reductionRatio (x k) (nonlinearLeastSquaresObjective r) (step k (acceptIndex k)) ∧ ‖step k (acceptIndex k)‖ = trialRadius k (acceptIndex k) then min (γ2 * trialRadius k (acceptIndex k)) ΔBar else trialRadius k (acceptIndex k)

Theorem 7.3.10

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.3.10 (1): let run be an exact-stopping trust-region type Levenberg-Marquardt Algorithm 7.3.9 run for f(x) = (1 / 2) * ‖r(x)‖² on the canonical Jacobian field residualJacobianMatrix r. Assume r is continuously differentiable, f is twice continuously differentiable, the initial sublevel set initialSublevelSet (nonlinearLeastSquaresObjective r) x₀ is bounded, and there exist constants M₁ and M₂ such that ‖∇² f(x)‖ ≤ M₁ and ‖gaussNewtonNormalMatrix r x‖ ≤ M₂ for every point in that initial sublevel set. Then the canonical least-squares gradient sequence g[r](run k) tends to 0.

open Filter Matrix
open scoped Matrix.Norms.Frobenius Matrix.Norms.L2Operator
open scoped LeastSquares
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ResidualVector" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ

-- Domain sampling for this theorem file:
-- * primary domain: exact-stopping trust-region Levenberg-Marquardt asymptotics for nonlinear
--   least-squares on Euclidean spaces;
-- * sampled owner declarations in the minimal Chapter 7 closure:
--   `TrustRegionLevenbergMarquardtAlgorithm`,
--   `leastSquaresGradient`,
--   `gaussNewtonNormalMatrix`,
--   `nonlinearLeastSquaresObjective`,
--   `initialSublevelSet`,
--   `hessianMatrixAt`;
-- * source/core/bridge triage:
--   - source-facing owner here: the exact-stopping/stuttering infinite-run reading used by the
--     source convergence statement;
--   - core/canonical owners reused here: the Chapter 7 trust-region algorithm owner from
--     `Algorithm_7_3_9`, the Chapter 7 least-squares gradient owner `leastSquaresGradient`,
--     the canonical Gauss-Newton normal-matrix owner `gaussNewtonNormalMatrix`, and the
--     canonical least-squares initial sublevel-set owner `initialSublevelSet`.
theorem trustRegionLevenbergMarquardt_gaussNewtonGradient_tendsto_zero
    (r : Point → ResidualVector)
    (run : TrustRegionLevenbergMarquardtAlgorithm r (residualJacobianMatrix r))
    (hRun : run.IsExactStoppingRun)
    (hCr : ContDiff ℝ 1 r)
    (hC2 : ContDiff ℝ 2 (nonlinearLeastSquaresObjective r))
    (M1 M2 : ℝ)
    (hLevelSetBounded :
      Bornology.IsBounded (initialSublevelSet (nonlinearLeastSquaresObjective r) run.x0))
    (hHessianBound :
      ∀ x ∈ initialSublevelSet (nonlinearLeastSquaresObjective r) run.x0,
        ‖hessianMatrixAt (nonlinearLeastSquaresObjective r) x‖ ≤ M1)
    (hGramBound :
      ∀ x ∈ initialSublevelSet (nonlinearLeastSquaresObjective r) run.x0,
        ‖gaussNewtonNormalMatrix r x‖ ≤ M2) :
    Tendsto (fun k : ℕ ↦ g[r](run k)) atTop (nhds 0)

Definition 7.3.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Definition 7.3-extra-1: for a Jacobian matrix J, right-hand side vector g, damping parameter μ, and step s, the Levenberg-Marquardt direction is characterized by the regularized normal equation (Jᵀ * J + μ • 1).mulVec s = -g. In nonlinear least squares this is specialized by g = Jᵀ.mulVec r.

open Matrix -- Chapter 7 already uses `solvesGaussNewtonNormalEquation` as the owner for normal-equation -- satisfaction. For the damped system, the primitive data is the Jacobian and the right-hand side -- vector `g`, while the residual-form equation is the least-squares specialization -- `g = Jᵀ.mulVec r`. variable {m n : ℕ} local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ local notation "GradientVector" => Fin n → ℝ local notation "ResidualVector" => Fin m → ℝ local notation "StepVector" => Fin n → ℝ def solvesLevenbergMarquardtNormalEquation (J : JacobianMatrix) (g : GradientVector) (μ : ℝ) (s : StepVector) : Prop := (Jᵀ * J + μ • (1 : MatrixN)).mulVec s = -g

7.4 — Implementation of L-M Method

Algorithm 7.4.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Algorithm 7.4.1: a Levenberg-Marquardt iteration at x_k with trust-region radius Δ_k > 0 and positive definite diagonal scaling matrix D_k consists of a parameter μ_k ≥ 0, a step s_k, the accepted or rejected next iterate x_{k+1}, a positive next trust-region radius Δ_{k+1} > 0, and a next positive definite diagonal scaling matrix D_{k+1} such that ((J x_k)ᵀ * J x_k + μ_k • D_k).mulVec s_k = -((J x_k)ᵀ.mulVec (r x_k)), either μ_k = 0 with ‖D_k.mulVec s_k‖ ≤ Δ_k or 0 < μ_k with ‖D_k.mulVec s_k‖ = Δ_k, and x_{k+1} is updated according to the acceptance test ‖r (x_k + s_k)‖ ≤ ‖r x_k‖.

open Matrix
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ResidualVector" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ

-- Semantic recall: `lean_leansearch` surfaced only generic nonlinear-operator results, so this
-- item keeps the source-facing Levenberg-Marquardt iteration directly on the local matrix and
-- Euclidean-space API already used elsewhere in Chapter 7.
structure LevenbergMarquardtIteration
    (r : Point → ResidualVector) (J : Point → JacobianMatrix)
    (xk : Point) (Δk : ℝ) (Dk : MatrixN) where
  mu : ℝ
  step : Point
  xNext : Point
  deltaNext : ℝ
  scalingMatrixNext : MatrixN
  delta_pos : 0 < Δk
  scalingMatrix_posDef : IsPositiveDefiniteDiagonalMatrix Dk
  mu_nonneg : 0 ≤ mu
  regularizedNormalEquation :
    (((J xk)ᵀ * J xk) + mu • Dk).mulVec step = -((J xk)ᵀ.mulVec (r xk))
  trustRegionCase :
    if mu = 0 then ‖Dk.mulVec step‖ ≤ Δk else ‖Dk.mulVec step‖ = Δk
  deltaNext_pos : 0 < deltaNext
  scalingMatrixNext_posDef : IsPositiveDefiniteDiagonalMatrix scalingMatrixNext
  acceptedUpdate :
    levenbergMarquardtStepAccepted r xk step → xNext = xk + step
  rejectedUpdate :
    ¬ levenbergMarquardtStepAccepted r xk step → xNext = xk

Algorithm 7.4.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Algorithm 7.4.2: a Moré Levenberg-Marquardt iteration at x_k with trust-region radius Δ_k, strictly positive diagonal scaling data d_k, parameter σ ∈ (0, 1), damping value μ_k, step s_k, ratio ρ_k, next iterate x_(k + 1), next Jacobian J_(k + 1), next trust-region radius Δ_(k + 1), next diagonal scaling data d_(k + 1). If the scaled Gauss-Newton pseudoinverse step satisfies moreScaledStepNorm d_k (morePseudoinverseStep (J x_k) (r x_k)) ≤ (1 + σ) * Δ_k, then μ_k = 0 with s_k equal to that pseudoinverse step; otherwise μ_k > 0, s_k minimizes the stacked least-squares problem [J_k; √μ_k D_k] s ≈ -[r_k; 0], with (1 - σ) * Δ_k ≤ moreScaledStepNorm d_k s_k plus moreScaledStepNorm d_k s_k ≤ (1 + σ) * Δ_k. The predicted reduction in the ratio ρ_k is assumed positive so that ρ_k is the genuine actual-to-predicted reduction quotient for the nonlinear least-squares objective. The iterate/Jacobian update follows the threshold ρ_k ≤ 1 / 10000. The radius update uses the source 1 / 4, 1 / 3, 3 / 4 branches. The current scaling matrix diag d_k is positive definite diagonal, and the next scaling data satisfy d_(k + 1) = max(d_k, columnNorms J_(k + 1)), matching (7.4.24).

open Matrix
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ResidualVector" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ

-- Semantic recall: `lean_leansearch` did not surface a dedicated Moré-type
-- Levenberg-Marquardt owner. Nearby Chapter 7 files package these methods as explicit
-- matrix/Euclidean-space iteration structures, so this item follows that local API.
structure MoreLevenbergMarquardtIteration
    (r : Point → ResidualVector) (J : Point → JacobianMatrix)
    (xk : Point) (Δk : ℝ) (dk : Fin n → ℝ) where
  sigma : ℝ
  mu : ℝ
  step : Point
  rho : ℝ
  xNext : Point
  jacobianNext : JacobianMatrix
  deltaNext : ℝ
  scalingNext : Fin n → ℝ
  sigma_mem_Ioo : sigma ∈ Set.Ioo 0 1
  delta_pos : 0 < Δk
  scalingMatrix_posDef :
    IsPositiveDefiniteDiagonalMatrix (moreScalingMatrix dk)
  step_case :
    if moreScaledStepNorm dk (morePseudoinverseStep (J xk) (r xk)) ≤ (1 + sigma) * Δk then
      mu = 0 ∧ step = morePseudoinverseStep (J xk) (r xk)
    else
      MoreLevenbergMarquardtDampedStep (J xk) (r xk) dk sigma Δk mu step
  predictedReduction_pos :
    0 < morePredictedReduction (J xk) (r xk) step
  rho_eq :
    rho =
      TrustRegionSubproblem.actualReduction xk (nonlinearLeastSquaresObjective r) step /
        morePredictedReduction (J xk) (r xk) step
  xNext_eq_of_small_ratio :
    rho ≤ (1 / 10000 : ℝ) → xNext = xk
  jacobianNext_eq_of_small_ratio :
    rho ≤ (1 / 10000 : ℝ) → jacobianNext = J xk
  xNext_eq_of_large_ratio :
    (1 / 10000 : ℝ) < rho → xNext = xk + step
  jacobianNext_eq_of_large_ratio :
    (1 / 10000 : ℝ) < rho → jacobianNext = J (xk + step)
  deltaNext_mem_of_ratio_le_quarter :
    rho ≤ (1 / 4 : ℝ) →
      deltaNext ∈ Set.Icc (((1 : ℝ) / 10) * Δk) (((1 : ℝ) / 2) * Δk)
  deltaNext_eq_of_expansion :
    MoreLevenbergMarquardtExpansionTrigger rho mu →
      deltaNext = 2 * moreScaledStepNorm dk step
  scalingNext_eq :
    scalingNext = moreScalingUpdate dk jacobianNext

Theorem 7.4.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.4.3 (1): let r : ℝ^n → ℝ^m be continuously differentiable, and let run : MoreLevenbergMarquardtSequence r be generated by Chapter07 Algorithm 7.4.2, including the source step-selection, reduction-ratio, accepted/rejected Jacobian update, and scaling-update semantics. If the Chapter 7 least-squares level set initialSublevelSet (nonlinearLeastSquaresObjective r) (run.x 0) is bounded, then the scaled gradient satisfies liminf_(k → ∞) ‖((J_k * D_k⁻¹)ᵀ).mulVec r_k‖ = 0, encoded as liminf (fun k ↦ ‖run.scaledGradient k‖) atTop = 0.

open Filter Matrix
open scoped LeastSquares
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ResidualVector" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ
theorem moreLevenbergMarquardt_liminf_scaledGradient_eq_zero
    (r : Point → ResidualVector)
    (hC1 : ContDiff ℝ 1 r)
    (run : MoreLevenbergMarquardtSequence r)
    (hLevelSetBounded :
      Bornology.IsBounded (initialSublevelSet (nonlinearLeastSquaresObjective r) (run.x 0))) :
    liminf (fun k : ℕ ↦ ‖run.scaledGradient k‖) atTop = 0

7.5 — Quasi-Newton Method

Theorem 7.5.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Theorem 7.5.1: for the Chapter 7 secant vector v, if 0 < dotProduct s v, T is positive definite, and (T * Tᵀ).mulVec s = v, then the update in (7.5.11), namely the Chapter 5 owner symmetrizedBroydenLimit B s y v, is the unique minimizer of the weighted Frobenius change weightedFrobeniusNorm T⁻¹ (Bnext - B) among matrices Bnext whose change from B is symmetric and that satisfy the secant equation Bnext.mulVec s = y.

open Matrix
open scoped Matrix.Norms.Frobenius
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem weightedLeastChangeHessianUpdate_isUniqueMinimizer
    (B T : MatrixN) (s v y : Point)
    (hsv : 0 < dotProduct s v)
    (hTpos : T.PosDef)
    (hTv : (T * Tᵀ).mulVec s = v) :
    let Bbar := symmetrizedBroydenLimit B s y v
    let δ : MatrixN → ℝ := weightedFrobeniusNorm T⁻¹
    let feasibleSet : Set MatrixN := {Bnext | (Bnext - B).IsSymm ∧ Bnext.mulVec s = y}
    Bbar ∈ feasibleSet ∧
      IsMinOn (fun Bnext ↦ δ (Bnext - B)) feasibleSet Bbar ∧
      ∀ Bnext ∈ feasibleSet, δ (Bnext - B) = δ (Bbar - B) → Bnext = Bbar

Remark 7.5.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter07 Remark 7.5-extra-1 (1): if Bₖ₊₁ = ∑ i, r_i(xₖ₊₁) • (H_i)ₖ₊₁, the residual map is differentiable at xₖ and xₖ₊₁, and each component secant approximation satisfies (H_i)ₖ₊₁ (xₖ₊₁ - xₖ) = ∇r_i(xₖ₊₁) - ∇r_i(xₖ), then Bₖ₊₁ satisfies the Hessian-form quasi-Newton equation with secant vector (J(xₖ₊₁) - J(xₖ))ᵀ r(xₖ₊₁).

open Matrix
open scoped BigOperators
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Residual" => EuclideanSpace ℝ (Fin m)
local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "residualCoords" => (EuclideanSpace.equiv (Fin m) ℝ)

-- Domain sampling for this remark:
-- * primary domain: least-squares quasi-Newton secant equations
-- * sampled canonical declarations in the same domain:
--   `satisfiesQuasiNewtonEquationHessianForm` from Chapter 5,
--   and `residualJacobianMatrix`, `leastSquaresGradient`,
--   `leastSquaresCorrectionMatrix`, `gaussNewtonNormalMatrix` from Chapter 7
-- * best owner abstraction: the Chapter 7 least-squares owners on
--   `EuclideanSpace ℝ (Fin n)` together with the Chapter 5 Hessian-form secant owner
-- * layer choice here:
--   (1) a bridge/view theorem from the source weighted Hessian approximation to the canonical
--       secant owner;
--   (2) a source-facing algebraic consequence stated directly on the Chapter 7 owners
-- * primitive data here: the residual map `r`, the points `xk`, `xk1`, the iterate
--   displacement `xk1 - xk`, the step `s` in (2), the aggregated approximation `Bnext`,
--   and the component Hessian approximants
-- * derived API here: the secant right-hand sides built from the residual Jacobian, the
--   least-squares gradient, and the Gauss-Newton normal matrix
theorem leastSquaresSecondOrderApproximation_secant
    (r : Point → Residual) (xk xk1 : Point)
    (Bnext : MatrixN) (componentHessians : Fin m → MatrixN)
    (hxk : DifferentiableAt ℝ r xk) (hxk1 : DifferentiableAt ℝ r xk1)
    (hB :
      Bnext = ∑ i : Fin m, residualCoords (r xk1) i • componentHessians i)
    (hHi :
      ∀ i : Fin m,
        (componentHessians i).toEuclideanLin (xk1 - xk) =
          gradient (fun y : Point ↦ residualCoords (r y) i) xk1 -
            gradient (fun y : Point ↦ residualCoords (r y) i) xk) :
    satisfiesQuasiNewtonEquationHessianForm
      Bnext.toEuclideanLin
      (xk1 - xk)
      (((residualJacobianMatrix r xk1 - residualJacobianMatrix r xk)ᵀ).toEuclideanLin
        (r xk1))

Supporting modules

These source modules support the indexed items and are listed separately so the chapter inventory remains complete.

  • Theorem_7_2_2/DifferentialData.lean (Documentation unavailable) (Lean source)

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

  • Theorem_7_2_2/NormalEquation.lean (Documentation unavailable) (Lean source)

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

  • Theorem_7_3_5/ConditionNumber.lean (Documentation unavailable) (Lean source)

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

  • Theorem_7_3_5/MatrixFamily.lean (Documentation unavailable) (Lean source)

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

  • Theorem_7_3_6/ArmijoSequence.lean (Documentation unavailable) (Lean source)

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source