LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

The L-Bfgs two-loop recursion equals the stored inverse updates and costs linear memory work

Statement

Let $0 \leq r \leq m$ stored pairs $(s_{i}, y_{i})$ , $i = 1, \dots, r$ , be ordered oldest to newest, with $s_{i}^{T} y_{i} > 0$ , and let $ρ_{i} = (s_{i}^{T} y_{i})^{- 1}$ . Start from $H_{0} = γ I$ with $γ > 0$ and apply the inverse updates of Bfgs curvature pairs and Hessian/inverse updates in that order, obtaining $H_{r}$ . For every $g \in R^{n}$ , the two-loop recursion in Limited-memory Bfgs two-loop recursion with curvature filtering returns $H_{r} g$ before changing its sign to form the search direction. The recursion uses $O (r n + n)$ scalar operations and stores $O (r n + n)$ real entries; when $m \geq 1$ and $r \leq m$ , these are $O (m n)$ .

Facts & Assumptions

Given: The memory length, valid stored pairs, scale $γ$ , and vector $g$ in the Statement.

[F1]

Limited-memory Bfgs two-loop recursion with curvature filtering: the reverse loop updates $q \leftarrow q - α_{i} y_{i}$ with $α_{i} = ρ_{i} s_{i}^{T} q$ , then the forward loop updates $r \leftarrow r + s_{i} (α_{i} - β_{i})$ with $β_{i} = ρ_{i} y_{i}^{T} r$ .

[F2]

Bfgs curvature pairs and Hessian/inverse updates: an inverse update is $H_{i} = V_{i}^{T} H_{i - 1} V_{i} + ρ_{i} s_{i} s_{i}^{T}$ , where $V_{i} = I - ρ_{i} y_{i} s_{i}^{T}$ .

Proof

Given: The memory length, valid stored pairs, scale $γ$ , and vector $g$ in the Statement.

[F1] Limited-memory Bfgs two-loop recursion with curvature filtering: the reverse loop updates $q \leftarrow q - α_{i} y_{i}$ with $α_{i} = ρ_{i} s_{i}^{T} q$ , then the forward loop updates $r \leftarrow r + s_{i} (α_{i} - β_{i})$ with $β_{i} = ρ_{i} y_{i}^{T} r$ .

[F2] Bfgs curvature pairs and Hessian/inverse updates: an inverse update is $H_{i} = V_{i}^{T} H_{i - 1} V_{i} + ρ_{i} s_{i} s_{i}^{T}$ , where $V_{i} = I - ρ_{i} y_{i} s_{i}^{T}$ .

1.1givenF1F2algebra

Set $q_{r} : = g$ . In the reverse loop, when pair $i$ is processed, the current vector is $q_{i}$ and $α_{i} = ρ_{i} s_{i}^{T} q_{i}$ . Its update is therefore $q_{i - 1} = q_{i} - ρ_{i} y_{i} (s_{i}^{T} q_{i}) = V_{i} q_{i}$ .

2.1step 1.1F1F2algebra

Set $r_{0} : = H_{0} q_{0}$ . In the forward loop, if $r_{i - 1}$ is the current vector, then $r_{i} = r_{i - 1} + s_{i} (α_{i} - ρ_{i} y_{i}^{T} r_{i - 1}) = V_{i}^{T} r_{i - 1} + ρ_{i} s_{i} (s_{i}^{T} q_{i}),$ because $V_{i}^{T} = I - ρ_{i} s_{i} y_{i}^{T}$ and $α_{i} = ρ_{i} s_{i}^{T} q_{i}$ .

3.1F2step 1.1step 2.1induction

By induction on $i$ , $r_{i} = H_{i} q_{i}$ . It holds at $i = 0$ by definition. If it holds at $i - 1$ , then $q_{i - 1} = V_{i} q_{i}$ from step 1.1, so $H_{i} q_{i} = V_{i}^{T} H_{i - 1} V_{i} q_{i} + ρ_{i} s_{i} (s_{i}^{T} q_{i}) = V_{i}^{T} r_{i - 1} + ρ_{i} s_{i} (s_{i}^{T} q_{i}) = r_{i}$ by [F2] and step 2.1. At $i = r$ , $q_{r} = g$ , hence the output is $r_{r} = H_{r} g$ .

4.1givenF1algebra∎

Each stored pair is read once in each loop. Each read uses a fixed number of length- $n$ dot products, scalar-vector products, and vector additions, so the operation count is at most a constant times $r n + n$ . The stored pairs use $2 r n$ coordinates; loop scalars use $O (r)$ entries and the working vectors use $O (n)$ entries. Therefore the counts are $O (r n + n)$ , and are $O (m n)$ when $m \geq 1$ and $r \leq m$ .

Depends on

Used by

Dependency tree · two levels

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