TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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.

Full-memory Bfgs is locally superlinear when the Hessian is Lipschitz

Statement

Assume the hypotheses of Full-memory Bfgs converges globally and linearly on a uniformly strongly convex level set and consider an infinite, nonstationary exact-undamped BFGS run with successful strong Wolfe searches. Under these same hypotheses, Locally Lipschitz Hessians give the BFGS Dennis–Moré condition proves the Dennis–Moré condition used below. Suppose the Hessian is $L_{G}$ -Lipschitz on a neighborhood of its minimizer $x_{*}$ : $∥ \nabla^{2} f (u) - \nabla^{2} f (v) ∥_{2} \leq L_{G} ∥ u - v ∥_{2} .$ Then the BFGS matrices satisfy the Dennis–Moré condition $\frac{∥ (B_{k} - G_{*}) s_{k} ∥_{2}}{∥ s_{k} ∥_{2}} ⟶ 0, G_{*} : = \nabla^{2} f (x_{*}),$ and the line search eventually accepts its initial unit trial. Consequently, $\frac{∥ x_{k + 1} - x_{*} ∥_{2}}{∥ x_{k} - x_{*} ∥_{2}} ⟶ 0.$ Here a sequence is superlinear when this last error ratio tends to zero. The conclusion concerns the exact undamped branch; Powell-damped and rounded-direction variants are not covered by this theorem.

Facts & Assumptions

Given: The global BFGS hypotheses, the exact-undamped run, and the local Hessian-Lipschitz bound in the Statement.

[F1]

Full-memory Bfgs converges globally and linearly on a uniformly strongly convex level set: the iterates converge to $x_{*}$ , the Hessian bounds hold on $L_{0}$ , and the initial inverse matrix is SPD.

[F2]

Locally Lipschitz Hessians give the BFGS Dennis–Moré condition: $∥ (B_{k} - G_{*}) s_{k} ∥_{2} / ∥ s_{k} ∥_{2} \to 0$ ; since $s_{k} = α_{k} p_{k}$ with $α_{k} > 0$ , the same holds with $p_{k}$ .

[F3]

Full-memory Bfgs with Wolfe search, descent reset, and Powell damping: in exact mode $p_{k} = - H_{k} g_{k}$ , $B_{k} = H_{k}^{- 1}$ , and hence $B_{k} p_{k} = - g_{k}$ .

[F4]

Uniform Hessian bounds control gradient changes and Taylor remainders: on a convex local neighborhood with Hessian bounds and Lipschitz Hessian, $∥ g (x_{*} + z) - g_{*} - G_{*} z ∥_{2} \leq L_{G} ∥ z ∥_{2}^{2}$ and $∥ g (x_{*} + z) - g_{*} ∥_{2} \leq Λ ∥ z ∥_{2}$ .

[F5]

Second-order Taylor expansion $f (a + h) = f (a) + \nabla f (a) \cdot h + \frac{1}{2} h^{T} H_{f} (a) h + o (∥ h ∥^{2})$ : $f (x_{*} + z) = f (x_{*}) + g_{*}^{T} z + \frac{1}{2} z^{T} G_{*} z + o (∥ z ∥_{2}^{2})$ for a $C^{2}$ scalar field.

[F6]

Finite-budget bracketing and zoom for a strong Wolfe step: the first expansion trial is $α = 1$ and is returned if both strong Wolfe checks pass.

[F7]

Wolfe and strong Wolfe line-search conditions: strong Wolfe requires Armijo and $∣ g_{k + 1}^{T} p_{k} ∣ \leq c_{2} ∣ g_{k}^{T} p_{k} ∣$ .

[F8]

The Hessian matrix and critical points of a scalar field and The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $G (x)$ is the Hessian and $g (x) = \nabla f (x)$ .

[F9]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and 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}$ .

[F10]

Clairaut--Schwarz theorem for continuous second partial derivatives: under the $C^{2}$ hypothesis, the mixed second partials commute, so the Hessian quadratic form in [F5] uses the Hessian convention $G_{*} = \nabla^{2} f (x_{*})$ of [F8].

Proof

Given: The hypotheses and notation in the Statement. Put $e_{k} : = x_{k} - x_{*}$ , $G_{*} : = G (x_{*})$ , and $g_{k} : = \nabla f (x_{k})$ .

1.1givenF1F8algebra

The global minimizer $x_{*}$ is interior to $R^{n}$ , so each coordinate restriction has a minimum at $x_{*}$ and $g_{*} : = \nabla f (x_{*}) = 0$ . By [F1], $e_{k} \to 0$ and the eigenvalues of $G_{*}$ lie in $[μ, Λ]$ .

1.2givenF2F3algebra

The Dennis–Moré condition [F2] and $s_{k} = α_{k} p_{k}$ , $α_{k} > 0$ , give $∥ (B_{k} - G_{*}) p_{k} ∥_{2} = o (∥ p_{k} ∥_{2})$ .

2.1givenF1F2F3F4F8F9step 1.2algebra

For all sufficiently large $k$ , [F4] gives $g_{k} = G_{*} e_{k} + r_{k}$ with $∥ r_{k} ∥_{2} \leq L_{G} ∥ e_{k} ∥_{2}^{2}$ . By [F3], $B_{k} p_{k} = - g_{k}$ , so $G_{*} p_{k} = - g_{k} + (G_{*} - B_{k}) p_{k} .$ The smallest eigenvalue of $G_{*}$ is at least $μ$ , hence $μ ∥ p_{k} ∥_{2} \leq ∥ G_{*} p_{k} ∥_{2} \leq Λ ∥ e_{k} ∥_{2} + o (∥ p_{k} ∥_{2})$ , using [F9]. For sufficiently large $k$ , the $o (∥ p_{k} ∥_{2})$ term is at most $μ ∥ p_{k} ∥_{2} / 2$ , so $μ ∥ p_{k} ∥_{2} / 2 \leq Λ ∥ e_{k} ∥_{2}$ and $∥ p_{k} ∥_{2} \leq 2 Λ ∥ e_{k} ∥_{2} / μ$ . Substitution into $G_{*} (e_{k} + p_{k}) = (G_{*} - B_{k}) p_{k} - r_{k}$ gives $G_{*} (e_{k} + p_{k}) = o (∥ e_{k} ∥_{2})$ ; the same eigenvalue lower bound yields $e_{k} + p_{k} = o (∥ e_{k} ∥_{2})$ .

3.1givenF1F4F5F6F7F9F10step 2.1algebra

For sufficiently large $k$ , $e_{k}$ and $e_{k} + p_{k}$ lie in the local neighborhood. Apply [F4] and [F5] to $z = e_{k}$ and $z = e_{k} + p_{k}$ , using [F10] to identify the Hessian convention. Since $e_{k} + p_{k} = o (∥ e_{k} ∥_{2})$ , these expansions give $g_{k}^{T} p_{k} = - e_{k}^{T} G_{*} e_{k} + o (∥ e_{k} ∥_{2}^{2}), f (x_{k} + p_{k}) - f (x_{k}) = - \frac{1}{2} e_{k}^{T} G_{*} e_{k} + o (∥ e_{k} ∥_{2}^{2}), g (x_{k} + p_{k}) = o (∥ e_{k} ∥_{2}) .$ Because $G_{*} ⪰ μ I$ and $c_{1} < 1 / 2$ , $f (x_{k} + p_{k}) - f (x_{k}) - c_{1} g_{k}^{T} p_{k} = - (1 / 2 - c_{1}) e_{k}^{T} G_{*} e_{k} + o (∥ e_{k} ∥_{2}^{2}) < 0$ for all sufficiently large $k$ , so Armijo holds. Also $p_{k} = O (∥ e_{k} ∥_{2})$ by step 2.1; [F9] gives $∣ g (x_{k} + p_{k})^{T} p_{k} ∣ = o (∥ e_{k} ∥_{2}^{2})$ , while $∣ g_{k}^{T} p_{k} ∣ \geq (μ / 2) ∥ e_{k} ∥_{2}^{2}$ eventually. Thus the strong curvature condition holds. The search first tries $α = 1$ by [F6], and the two checks are exactly [F7], so the unit step is accepted.

4.1step 2.1step 3.1∎

Eventually $x_{k + 1} = x_{k} + p_{k}$ , so $e_{k + 1} = e_{k} + p_{k} = o (∥ e_{k} ∥_{2})$ by step 2.1. This is the claimed superlinear error ratio.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

51 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, 2nd ed. (standard reference, not scraped)
Manuel Carreira-Perpiñán, Lecture Notes on Numerical Optimization (standard reference, not scraped)