Limited-memory Bfgs two-loop recursion with curvature filtering

Inputs are a $C^1$ objective $f:D\to \mathbb{R}$ on an open set $D\subseteq {\mathbb{R}}^n$ with $n\ge 1$, an initial point $x_0\in D$, a positive integer memory length $m$, a fallback scale ${\gamma }_0>0$, line-search constants $0<c_1<c_2<1\mathrm{/}2$, and finite expansion, zoom, and iteration budgets $E,Z,K\in \mathbb{N}$ (zero is allowed). All evaluations of $f$ and $\mathrm{\nabla }f$, and all scalar and vector arithmetic, are exact over $\mathbb{R}$. Initialize $k:=0$, the current point $x:=x_0$, the current gradient $g:=\mathrm{\nabla }f(x_0)$, and an empty history list. If $g=0$, return stationary. Otherwise, while $k<K$, store at most $m$ pairs $(s_i,y_i)$ in chronological order, retaining only pairs with $s_i^T{y}_i>0$. Let ${\rho }_i=(s_i^T{y}_i{)}^{-1}$ for each stored pair.

At each nonstationary iterate $x$ with current gradient $g$, all inner products are the Euclidean ones of The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$. Choose $\gamma ={\gamma }_0$ if the list is empty; otherwise choose $\gamma =\frac{s_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}^T{y}_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}}{y_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}^T{y}_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}}\mathrm{.}$ The denominator is positive because the retained pair has positive curvature, so $y_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\mathrm{\ne }0$. Compute $r=H_{k}g$ by the following two loops, then set $p=-r$:

1. Set $q:=g$. Traverse the stored pairs from newest to oldest, setting ${\alpha }_i:={\rho }_i{s}_i^{T}q$ and then $q:=q-{\alpha }_i{y}_i$.
2. Set $r:=\gamma q$. Traverse the pairs from oldest to newest, setting ${\beta }_i:={\rho }_i{y}_i^{T}r$ and then $r:=r+s_i({\alpha }_i-{\beta }_i)$.

If $g=0$, return stationary. If $g^{T}p\ge 0$, clear the list, set $p:=-{\gamma }_{0}g$, and return direction-failure only if this fallback is not a strict descent direction.

Call Finite-budget bracketing and zoom for a strong Wolfe step with $(f,x,p,c_1,c_2,E,Z)$. If it returns a failure status, return that status with the current point. If it returns $\alpha >0$, set $x^{+}:=x+\alpha p$, compute $g^{+}:=\mathrm{\nabla }f(x^{+})$, and set $s:=x^{+}-x$, $y:=g^{+}-g$. If $s^{T}y>0$, append $(s,y)$ and $\rho =(s^{T}y{)}^{-1}$, dropping the oldest pair if the list would exceed $m$. If $s^{T}y\le 0$, skip that pair and preserve the existing valid list.

After either storing or skipping the new pair, commit the accepted step by setting $x:=x^{+}$ and $g:=g^{+}$, then increment $k:=k+1$. If the updated gradient is zero, return stationary at $x$; otherwise continue while $k<K$. When the iteration budget is exhausted, return the current point and iteration-budget-exhausted. A line-search failure returns its status with the current point, and the fallback branch returns direction-failure only if the fallback direction is not a strict descent direction. Finite line-search budgets may fail even when a strong Wolfe step exists.

Output the last point and one of stationary, the line-search status, direction-failure, or iteration-budget-exhausted.

The initial inverse-Hessian scale is $\gamma I$, an SPD matrix. Positive curvature is checked before storing a pair. The pair filter protects the recursion from a zero or negative denominator; it does not turn a failed finite search into an accepted step.