Full-memory Bfgs with Wolfe search, descent reset, and Powell damping

Inputs are a $C^1$ objective $f:D\to \mathbb{R}$ on an open $D\subseteq {\mathbb{R}}^n$ with $n\ge 1$, $x_0\in D$, consistent SPD matrices $B_0,H_0$ with $B_0{H}_0=H_0{B}_0=I$, a reset scale $\gamma >0$, constants $0<c_1<c_2<1\mathrm{/}2$, finite line-search and iteration budgets $E,Z,K\in \mathbb{N}$ (zero is allowed), a direction mode exact or rounded-Cholesky, and an update mode undamped or Powell. For rounded-Cholesky mode, also input a finite binary arithmetic format for the called direction procedure.

Initialize $k:=0$, $x_k:=x_0$, $B_k:=B_0$, $H_k:=H_0$, and $g_0:=\mathrm{\nabla }f(x_0)$. If $g_0=0$, return stationary at $x_0$. While $k<K$, if $g_k=0$, return stationary at $x_k$. Use the Euclidean inner product of The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$ in descent and curvature tests. In exact direction mode set $p_k:=-H_k{g}_k$. In rounded-Cholesky mode, first check that every entry of $B_k$ and $g_k$ is finite and representable in the selected format. If any entry is not, return direction-input-failure with $x_k$. Otherwise call Bfgs Hessian direction by failure-aware Cholesky solve with $(B_k,g_k)$ in that format; if the factorization or triangular solve fails, return its failure status with $x_k$. Otherwise set $p_k$ to its returned direction. If the computed direction is not descending, reset $B_k:={\gamma }^{-1}I$, $H_k:=\gamma I$, and set $p_k:=-\gamma g_k$.

Call Finite-budget bracketing and zoom for a strong Wolfe step with $(f,x_k,p_k,c_1,c_2,E,Z)$. If it returns a failure status, return that status and $x_k$. Otherwise take its positive strong Wolfe step ${\alpha }_k$, set $x_{k+1}:=x_k+{\alpha }_k{p}_k$, and compute $g_{k+1}:=\mathrm{\nabla }f(x_{k+1})$. Define $s_k:={\alpha }_k{p}_k,y_k:=g_{k+1}-g_k\mathrm{.}$ In undamped mode set ${\bar{y}}_k:=y_k$. In Powell mode put $c_k:=s_k^T{B}_k{s}_k$ and use the damping rule of Bfgs curvature pairs and Hessian/inverse updates to form ${\bar{y}}_k$. If $s_k^T{\bar{y}}_k\le 0$, skip the matrix update and return curvature-rejected with $x_{k+1}$. Otherwise update both matrices by $B_{k+1}=B_k-\frac{B_k{s}_k{s}_k^T{B}_k}{s_k^T{B}_k{s}_k}+\frac{{\bar{y}}_k{\bar{y}}_k^T}{s_k^T{\bar{y}}_k},H_{k+1}=(I-{\rho }_k{s}_k{\bar{y}}_k^T)H_k(I-{\rho }_k{\bar{y}}_k{s}_k^T)+{\rho }_k{s}_k{s}_k^T,{\rho }_k=(s_k^T{\bar{y}}_k{)}^{-1}\mathrm{.}$ If any required scalar or matrix operation is undefined, discard partial update results and return update-failure with $x_{k+1}$. After a successful update, commit $(x_{k+1},g_{k+1},B_{k+1},H_{k+1})$ as the state for the next iteration. If $g_{k+1}=0$, return stationary at $x_{k+1}$; if $k+1=K$, return iteration-budget-exhausted at $x_{k+1}$. Otherwise set $k:=k+1$ and continue from that committed state. A line-search failure returns its status with $x_k$. If the loop exits because $k=K$ without another return, return iteration-budget-exhausted with $x_k$; this covers $K=0$. The output is the last point and one of stationary, a line-search status, direction-input-failure, factorization/solve failure, curvature-rejected, update-failure, or iteration-budget-exhausted.

All objective and gradient evaluations, line-search arithmetic, descent and curvature tests, resets, and BFGS matrix updates are exact over $\mathbb{R}$. Only the called rounded-Cholesky factorization and triangular solves use the selected finite arithmetic. The representability check is repeated before every call, since exact updates need not preserve representable entries. The rounded-Cholesky direction mode specifies a computed factor-and-solve direction only; this item supplies no backward-error or convergence theorem for that mode. Its returned direction is checked for descent before the strong Wolfe search. The line-search procedure can fail within its finite budgets even when an acceptable step exists.