LemmaStatement: 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.

Locally Lipschitz Hessians give the BFGS Dennis–Moré condition

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. Suppose $G (x) = \nabla^{2} f (x)$ is $L_{G}$ -Lipschitz in operator norm on a neighborhood of $x_{*}$ . With $B_{k} : = H_{k}^{- 1}$ and $s_{k} : = x_{k + 1} - x_{k}$ , the iterates satisfy $\frac{∥ (B_{k} - G_{*}) s_{k} ∥_{2}}{∥ s_{k} ∥_{2}} ⟶ 0, G_{*} : = G (x_{*}) .$ Since $s_{k} = α_{k} p_{k}$ with $α_{k} > 0$ , the same limit holds with $p_{k}$ in place of $s_{k}$ . This is the Dennis–Moré condition used by the local full-memory superlinear convergence result.

Facts & Assumptions

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

[F1]

Full-memory Bfgs converges globally and linearly on a uniformly strongly convex level set: $f (x_{k}) - f (x_{*}) \leq r_{0} q^{k}$ for some $r_{0} \geq 0$ , $0 < q < 1$ , and $H_{0}$ is SPD.

[F2]

Full-memory Bfgs with Wolfe search, descent reset, and Powell damping: in exact-undamped mode $p_{k} = - H_{k} g_{k}$ , $B_{k} = H_{k}^{- 1}$ , $s_{k} = α_{k} p_{k}$ , $y_{k} = g_{k + 1} - g_{k}$ , and the undamped BFGS update is applied after a successful strong Wolfe step.

[F3]

Bfgs curvature pairs and Hessian/inverse updates: $B^{+} = B - B s s^{T} B / (s^{T} B s) + y y^{T} / (s^{T} y)$ for $s^{T} y > 0$ .

[F4]

Bfgs trace and determinant identities give a matrix potential inequality: the BFGS update satisfies the trace/determinant potential inequality, $ψ (B) \geq n$ , and $h (t) = 1 - t + \log t \leq 0$ with equality only at $t = 1$ ; its curvature angle lies in $(0, 1]$ .

[F5]

Bfgs updates preserve the secant equations, symmetry, and positive definiteness: a positive-curvature update preserves SPD and reciprocity.

[F6]

Wolfe and strong Wolfe line-search conditions: every strong Wolfe step is a Wolfe step.

[F7]

A Wolfe step gives positive Bfgs curvature on a descent direction: a Wolfe step along a strict descent direction gives $s_{k}^{T} y_{k} > 0$ .

[F8]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric matrix has an orthonormal eigenbasis.

[F9]

Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ : every positive real number has a unique positive square root.

[F10]

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) = \nabla^{2} f (x)$ and $g (x) = \nabla f (x)$ .

[F11]

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$ is the Euclidean inner product and $∣ u^{T} v ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ .

[F12]

Uniform Hessian bounds control gradient changes and Taylor remainders: on a convex set with the stated Hessian bounds, the gradient is Lipschitz; when the Hessian is Lipschitz near $x_{*}$ , $∥ g (u) - g (v) - G_{*} (u - v) ∥_{2} \leq L_{G} \max (∥ u - x_{*} ∥_{2}, ∥ v - x_{*} ∥_{2}) ∥ u - v ∥_{2}$ .

[F13]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: $\log^{'} (x) = 1 / x$ for $x > 0$ .

Proof

Given: The hypotheses and notation in the Statement. Write $e_{k} : = x_{k} - x_{*}$ , $g_{k} : = \nabla f (x_{k})$ , and $B_{k} : = H_{k}^{- 1}$ .

1.1givenF1F10algebra

The global theorem gives $r_{k} : = f (x_{k}) - f (x_{*}) \leq r_{0} q^{k}$ . Its strong-convexity lower bound gives $∥ e_{k} ∥_{2} \leq \sqrt{2 r_{0} / μ} q^{k / 2}$ , so $\sum_{k} ∥ e_{k} ∥_{2} < \infty$ . Also $g_{*} : = \nabla f (x_{*}) = 0$ because each coordinate restriction has a minimum at $x_{*}$ in the open domain.

1.2givenF1F2F5F6F7algebrainduction

The initial pair is SPD. At a nonstationary iterate, $p_{k} = - H_{k} g_{k}$ is a strict descent direction. The accepted strong Wolfe step is Wolfe by [F6], so [F7] gives $s_{k}^{T} y_{k} > 0$ ; [F5] preserves SPD and reciprocity. Induction proves every $B_{k}, H_{k}$ is SPD.

2.1givenF1F2F10F12step 1.1step 1.2algebra

Choose a closed ball $W$ about $x_{*}$ contained in the Hessian-Lipschitz neighborhood, and set $K : = L_{0} \cap W$ . Both sets are convex and $x_{*} \in K$ . By step 1.1, for all sufficiently large $k$ , the accepted segment lies in $K$ . Define $ε_{k} : = \max {∥ e_{k} ∥_{2}, ∥ e_{k + 1} ∥_{2}}$ , $s_{k} : = x_{k + 1} - x_{k}$ , and $y_{k} : = g_{k + 1} - g_{k}$ . Applying [F12] on the segment gives $∥ y_{k} - G_{*} s_{k} ∥_{2} \leq L_{G} ε_{k} ∥ s_{k} ∥_{2},$ and $\sum_{k} ε_{k} < \infty$ .

3.1givenF1F3F8F9step 1.2step 2.1algebra

By [F8], choose an orthonormal eigenbasis of $G_{*}$ with eigenvalues $λ_{i}$ . The lower Hessian bound and the operator-norm bound give $μ \leq λ_{i} \leq Λ$ . Define $G_{*}^{1 / 2}$ and $G_{*}^{- 1 / 2}$ in that basis using diagonal entries $\sqrt{λ_{i}}$ and $1 / \sqrt{λ_{i}}$ , respectively; [F9] supplies the positive roots. Then $(G_{*}^{1 / 2})^{2} = G_{*}$ and $G_{*}^{1 / 2} G_{*}^{- 1 / 2} = I$ . Set ${\tilde{s}}_{k} : = G_{*}^{1 / 2} s_{k}, {\tilde{y}}_{k} : = G_{*}^{- 1 / 2} y_{k}, {\tilde{B}}_{k} : = G_{*}^{- 1 / 2} B_{k} G_{*}^{- 1 / 2} .$ The update for ${\tilde{B}}_{k}$ has the same BFGS form with pair $({\tilde{s}}_{k}, {\tilde{y}}_{k})$ : ${\tilde{B}}_{k} {\tilde{s}}_{k} = G_{*}^{- 1 / 2} B_{k} s_{k}$ , ${\tilde{s}}_{k}^{T} {\tilde{B}}_{k} {\tilde{s}}_{k} = s_{k}^{T} B_{k} s_{k}$ , and ${\tilde{s}}_{k}^{T} {\tilde{y}}_{k} = s_{k}^{T} y_{k}$ . Substitution in [F3] gives ${\tilde{B}}_{k + 1} = G_{*}^{- 1 / 2} B_{k + 1} G_{*}^{- 1 / 2}$ . By step 2.1, ${\tilde{y}}_{k} - {\tilde{s}}_{k} = G_{*}^{- 1 / 2} (y_{k} - G_{*} s_{k})$ . Since $∥ G_{*}^{- 1 / 2} ∥_{2} \leq 1 / \sqrt{μ}$ and $s_{k} = G_{*}^{- 1 / 2} {\tilde{s}}_{k}$ , we have $∥ s_{k} ∥_{2} \leq ∥ G_{*}^{- 1 / 2} ∥_{2} ∥ {\tilde{s}}_{k} ∥_{2}$ , and hence $∥ {\tilde{y}}_{k} - {\tilde{s}}_{k} ∥_{2} \leq L_{G} ∥ G_{*}^{- 1 / 2} ∥_{2}^{2} ε_{k} ∥ {\tilde{s}}_{k} ∥_{2} .$ Put $δ_{k} : = L_{G} ∥ G_{*}^{- 1 / 2} ∥_{2}^{2} ε_{k}$ ; then $\sum_{k} δ_{k} < \infty$ , so eventually $δ_{k} \leq 1 / 2$ . Congruence preserves SPD, so ${\tilde{B}}_{k}$ is SPD.

4.1givenF11F13step 3.1algebra

For all sufficiently large $k$ , the triangle inequality and [F11] give $(1 - δ_{k}) ∥ {\tilde{s}}_{k} ∥_{2} \leq ∥ {\tilde{y}}_{k} ∥_{2} \leq (1 + δ_{k}) ∥ {\tilde{s}}_{k} ∥_{2}, {\tilde{m}}_{k} : = \frac{{\tilde{y}}_{k}^{T} {\tilde{s}}_{k}}{∥ {\tilde{s}}_{k} ∥_{2}^{2}} \geq 1 - δ_{k} .$ Put ${\tilde{M}}_{k} : = ∥ {\tilde{y}}_{k} ∥_{2}^{2} / ({\tilde{y}}_{k}^{T} {\tilde{s}}_{k})$ . Algebra gives $(1 + δ_{k})^{2} / (1 - δ_{k}) \leq 1 + 7 δ_{k}$ , since the difference after multiplication by $1 - δ_{k} > 0$ is $4 δ_{k} (1 - 2 δ_{k}) \geq 0$ . Also, for $0 \leq t \leq 1 / 2$ , $r (t) : = \log (1 - t) + 2 t$ has $r (0) = 0$ and $r^{'} (t) = (1 - 2 t) / (1 - t) \geq 0$ by [F13]. Thus ${\tilde{M}}_{k} \leq 1 + 7 δ_{k}$ and $\log {\tilde{m}}_{k} \geq - 2 δ_{k}$ .

5.1givenF4step 3.1step 4.1algebra

Since ${\tilde{B}}_{k}$ is SPD and ${\tilde{s}}_{k} \neq 0$ , [F4] gives $0 < {\tilde{η}}_{k} \leq 1$ and ${\tilde{q}}_{k} > 0$ , where ${\tilde{η}}_{k} : = \frac{{\tilde{s}}_{k}^{T} {\tilde{B}}_{k} {\tilde{s}}_{k}}{∥ {\tilde{s}}_{k} ∥_{2} ∥ {\tilde{B}}_{k} {\tilde{s}}_{k} ∥_{2}}, {\tilde{q}}_{k} : = \frac{{\tilde{s}}_{k}^{T} {\tilde{B}}_{k} {\tilde{s}}_{k}}{∥ {\tilde{s}}_{k} ∥_{2}^{2}}, v_{k} : = {\tilde{q}}_{k} / {\tilde{η}}_{k}^{2} .$ Applying the potential inequality [F4] to the transformed update and using step 4.1 gives $0 < ψ ({\tilde{B}}_{k + 1}) \leq ψ ({\tilde{B}}_{k}) + 9 δ_{k} + h (v_{k}) + \log {\tilde{η}}_{k}^{2},$ since ${\tilde{M}}_{k} - \log {\tilde{m}}_{k} - 1 \leq 9 δ_{k}$ .

6.1givenF4step 5.1algebra

Sum step 5.1 from a sufficiently large index $K$ to $N - 1$ and rearrange: $\sum_{k = K}^{N - 1} [- h (v_{k}) - \log {\tilde{η}}_{k}^{2}] \leq ψ ({\tilde{B}}_{K}) - ψ ({\tilde{B}}_{N}) + 9 \sum_{k = K}^{N - 1} δ_{k} \leq ψ ({\tilde{B}}_{K}) + 9 \sum_{k = K}^{\infty} δ_{k} .$ The right side is finite, and the summands are nonnegative by [F4], so both $h (v_{k}) \to 0$ and ${\tilde{η}}_{k} \to 1$ . For any $0 < ϵ < 1$ , strict increase of $h$ on $(0, 1)$ and strict decrease on $(1, \infty)$ , with equality only at $1$ by [F4], imply $h (v) \leq h (1 - ϵ) < 0$ when $v \leq 1 - ϵ$ and $h (v) \leq h (1 + ϵ) < 0$ when $v \geq 1 + ϵ$ . Therefore $v_{k} \to 1$ .

7.1givenF8step 5.1step 6.1algebra∎

Let $w_{k} : = ({\tilde{B}}_{k} - I) {\tilde{s}}_{k}$ . Expanding gives $\frac{∥ w_{k} ∥_{2}^{2}}{∥ {\tilde{s}}_{k} ∥_{2}^{2}} = \frac{{\tilde{q}}_{k}^{2}}{{\tilde{η}}_{k}^{2}} - 2 {\tilde{q}}_{k} + 1 = v_{k} {\tilde{q}}_{k} - 2 {\tilde{q}}_{k} + 1.$ By the definitions in step 5.1, ${\tilde{q}}_{k} = v_{k} {\tilde{η}}_{k}^{2}$ ; step 6.1 therefore makes the right side tend to zero. The definitions give $w_{k} = G_{*}^{- 1 / 2} (B_{k} - G_{*}) s_{k}$ , so $∥ (B_{k} - G_{*}) s_{k} ∥_{2} \leq \sqrt{Λ} ∥ w_{k} ∥_{2}$ and $∥ {\tilde{s}}_{k} ∥_{2} \leq \sqrt{Λ} ∥ s_{k} ∥_{2}$ . Hence $\frac{∥ (B_{k} - G_{*}) s_{k} ∥_{2}}{∥ s_{k} ∥_{2}} \leq Λ \frac{∥ w_{k} ∥_{2}}{∥ {\tilde{s}}_{k} ∥_{2}} ⟶ 0.$ Because $s_{k} = α_{k} p_{k}$ with $α_{k} > 0$ , the same limit holds with $p_{k}$ in place of $s_{k}$ .

Depends on

Used by

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

Dependency tree · two levels

65 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)