LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Uniformly large damping forces an acceptable LM trial in finitely many attempts

Statement

Let $r : U \to R^{m}$ be $C^{1}$ on an open $U \subseteq R^{n}$ , let $J = D r$ , and let $ϕ = ∥ r ∥_{2}^{2} / 2$ . Fix $x_{0} \in U$ and suppose its sublevel set $S = {x \in U : ϕ (x) \leq ϕ (x_{0})}$ is compact. Put $S_{1} = {y \in R^{n} : dist (y, S) \leq 1}$ and assume $S_{1} \subseteq U$ . On $S_{1}$ , suppose $∥ r (x) ∥_{2} \leq R_{0}$ , $∥ J (x) ∥_{2} \leq M$ , and $J$ is $L$ -Lipschitz in the Euclidean induced matrix norm. Fix nonsingular $D$ , numbers $d, d_{+} > 0$ with $∥ D v ∥_{2} \geq d ∥ v ∥_{2}$ and $\max {∥ D ∥_{2}, ∥ D^{T} ∥_{2}} \leq d_{+}$ , and parameters $λ_{\min} > 0$ , $γ > 1$ , $0 < η_{1} < η_{2} < 1$ , and $Δ > 0$ . Define $C_{D} : = d_{+}^{2} + M^{2} / λ_{\min}, C_{E} : = \frac{L}{2} (R_{0} + M) + \frac{L^{2}}{8}, P : = \min {1, Δ / (2 d_{+})},$ $Λ : = \max {λ_{\min}, \frac{M R_{0}}{d^{2} P}, \frac{C_{E} C_{D}^{2}}{(1 - η_{2}) d^{6}}}, N : = 1 + ⌈ \frac{\log (Λ / λ_{\min})}{\log γ} ⌉ .$ At any $x \in S$ with $g : = J (x)^{T} r (x) \neq 0$ , an exact LM trial with damping $λ \geq Λ$ , using a supplied exact reduced QR factorization of its augmented matrix, has $0 < pred$ , $∥ D p_{λ} ∥_{2} \leq Δ / 2$ , and $ρ \geq η_{2}$ . Therefore, if the algorithm starts an iteration with $λ \geq λ_{\min}$ and has at least $N$ trials, it either accepts an earlier trial with $ρ \geq η_{1}$ or accepts by the $N$ th trial. This conclusion assumes exact subproblem solves and exact objective evaluations.

Facts & Assumptions

Given: The residual map, compact sublevel and unit neighborhood, bounds, nonsingular scaling, damping floor and update factor, ratio thresholds, radius, and exact trial model of the Statement.

[F1]

Finite-budget Levenberg-Marquardt with a trust-ratio safeguard: the exact step solves $(J^{T} J + λ D^{T} D) p = - J^{T} r$ , rejection multiplies $λ$ by $γ$ , and an actual ratio is tested only on a feasible trial with positive predicted reduction. With the stated exact solves and evaluations, such a trial is accepted when $ρ \geq η_{1}$ , after the prescribed next damping is set.

[F2]

A damped least-squares step solves a scaled trust-region model: for nonzero $g$ , $pred = ∥ J p ∥_{2}^{2} / 2 + λ ∥ D p ∥_{2}^{2} > 0$ .

[F3]

Rectangular residual linearization error under a Lipschitz Jacobian: on a convex segment, $∥ r (x + p) - r (x) - J (x) p ∥_{2} \leq (L / 2) ∥ p ∥_{2}^{2}$ .

[F4]

Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1: induced matrix norms bound products and matrix-vector products.

[F5]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: $∣ u^{T} v ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ .

[F6]

Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition and Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison: a matrix and its transpose have the same singular values, hence the same Euclidean induced matrix norm.

[F7]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the Euclidean norm is induced by the standard real inner product.

[F8]

The matrix norm induced by a published vector p-norm: for $p = 2$ , $∥ A ∥_{2}$ is the operator norm induced by the Euclidean vector norm.

[A1]

$S$ is compact, $S_{1} \subseteq U$ , and the stated bounds hold on $S_{1}$ .

[A2]

The LM system is solved exactly and each $ϕ (x + p)$ used by the ratio is evaluated exactly.

Proof

1.1givenA1A2F1F2F4F5F6F7F8construct

Fix $x \in S$ with $g = J (x)^{T} r (x) \neq 0$ , and let $λ \geq λ_{\min}$ . By [F1] the exact trial solves $Q_{λ} p = - g$ for $Q_{λ} = J^{T} J + λ D^{T} D$ . For $v \neq 0$ , $v^{T} Q_{λ} v = ∥ J v ∥_{2}^{2} + λ ∥ D v ∥_{2}^{2} > 0$ , so the solution is nonzero. By [F2], $pred = \frac{1}{2} ∥ J p ∥_{2}^{2} + λ ∥ D p ∥_{2}^{2}$ . The transpose norm equality [F6] and submultiplicativity [F4] give $∥ g ∥_{2} = ∥ Q_{λ} p ∥_{2} \leq (M^{2} + λ d_{+}^{2}) ∥ p ∥_{2} \leq λ C_{D} ∥ p ∥_{2}$ . Also $λ d^{2} ∥ p ∥_{2}^{2} \leq p^{T} Q_{λ} p = - p^{T} g \leq ∥ p ∥_{2} ∥ g ∥_{2}$ by [F5], so $∥ p ∥_{2} \leq ∥ g ∥_{2} / (λ d^{2}) \leq M R_{0} / (λ d^{2})$ using [F4], [F6], and [A1].

2.1givenA1F3F5F7F8step 1.1algebra

If $λ \geq Λ$ , step 1.1 gives $∥ p ∥_{2} \leq P \leq 1$ and therefore $∥ D p ∥_{2} \leq d_{+} P \leq Δ / 2$ . The segment from $x$ to $x + p$ lies in $S_{1}$ , since every point on it is within $∥ p ∥_{2} \leq 1$ of $x \in S$ . Apply [F3] on that segment and write $E = r (x + p) - r (x) - J p$ ; then $∥ E ∥_{2} \leq (L / 2) ∥ p ∥_{2}^{2}$ . Expanding the two squared norms and using [F5] yields $∣ ϕ (x + p) - m_{0} (p) ∣ = ∣ (r (x) + J p)^{T} E + \frac{1}{2} ∥ E ∥_{2}^{2} ∣ \leq C_{E} ∥ p ∥_{2}^{2}$ .

3.1F2F4step 1.1step 2.1algebra

By step 1.1, step 2.1, and [F2], $pred \geq λ ∥ D p ∥_{2}^{2} \geq λ d^{2} ∥ p ∥_{2}^{2}$ . From $g = - Q_{λ} p$ and [F4], $∥ p ∥_{2} \geq ∥ g ∥_{2} / (λ C_{D})$ , so $pred \geq d^{2} ∥ g ∥_{2}^{2} / (λ C_{D}^{2})$ . The preceding bounds therefore give $∣ ρ - 1 ∣ = \frac{∣ ϕ (x + p) - m_{0} (p) ∣}{pred} \leq \frac{C_{E} C_{D}^{2}}{λ d^{6}} \leq 1 - η_{2},$ and hence $ρ \geq η_{2}$ .

4.1F1givenstep 2.1step 3.1algebra∎

Since $Λ \geq λ_{\min}$ , after at most $⌈ \log (Λ / λ_{\min}) / \log γ ⌉$ consecutive rejections the damping reaches at least $Λ$ . At that trial step 2.1 makes it radius-feasible and step 3.1 gives $ρ \geq η_{2} > η_{1}$ , so it is accepted. An earlier feasible trial with $ρ \geq η_{1}$ is already accepted by [F1]. The extra one in $N$ counts the final trial at or above $Λ$ , proving the finite attempt bound.

Depends on

Used by

Exact safeguarded Levenberg-Marquardt iterates approach stationarity on compact sublevels Theorem

Dependency tree · two levels

58 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Jorge Nocedal and Stephen J. Wright, Numerical Optimization, second edition (standard reference, not scraped)
David Bindel, CS 4220: Numerical Analysis, Gauss-Newton and nonlinear least squares (standard reference, not scraped)