Finite-budget bracketing and zoom for a strong Wolfe step

Let $D\subseteq {\mathbb{R}}^n$ be open, let $f:D\to \mathbb{R}$ be $C^1$, let $x\in D$, and let $p\in {\mathbb{R}}^n$ be arbitrary. Fix $0<c_1<c_2<1\mathrm{/}2$ and finite budgets $E,Z\in \mathbb{N}$ for expansion and zoom trials. After the direction check passes, use the functions $\varphi (t)=f(x+tp)$ and ${\varphi }^{\mathrm{\prime }}(t)=⟨\mathrm{\nabla }f(x+tp),p⟩$ from Wolfe and strong Wolfe line-search conditions. Output: either a positive strong Wolfe step, or one of invalid-direction, domain-exit, and evaluation-budget-exhausted.

1. Evaluate and retain $f(x)$ and $\mathrm{\nabla }f(x)$, and set $\varphi (0):=f(x)$ and ${\varphi }^{\mathrm{\prime }}(0):=⟨\mathrm{\nabla }f(x),p⟩$. If ${\varphi }^{\mathrm{\prime }}(0)\ge 0$, return invalid-direction. Set $a:=0$ and $t:=1$. For at most $E$ expansion trials, in order:
   • If $x+tp\mathrm{\notin }D$, return domain-exit without evaluating the trial.
   • Evaluate $\varphi (t)$ and ${\varphi }^{\mathrm{\prime }}(t)$. If $\varphi (t)>\varphi (0)+c_{1}t{\varphi }^{\mathrm{\prime }}(0)$ or $\varphi (t)\ge \varphi (a)$, call the zoom procedure below with the ordered endpoint pair $(a,t)$ and return its output.
   • If $\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(t)\mathrm{\mid }\le c_2\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(0)\mathrm{\mid }$, return $t$ as a strong Wolfe step.
   • If ${\varphi }^{\mathrm{\prime }}(t)\ge 0$, call zoom with the reversed endpoint pair $(t,a)$ and return its output.
   • Otherwise set $a:=t$ and $t:=2t$.
2. If the expansion budget is exhausted, return evaluation-budget-exhausted.

For zoom(a,b), preserve the endpoint order even when $b<a$. For at most $Z$ zoom trials, in order:

1. Set $m:=(a+b)\mathrm{/}2$. If $x+mp\mathrm{\notin }D$, return domain-exit without evaluating the trial.
2. Evaluate $\varphi (m)$ and ${\varphi }^{\mathrm{\prime }}(m)$. If $\varphi (m)>\varphi (0)+c_{1}m{\varphi }^{\mathrm{\prime }}(0)$ or $\varphi (m)\ge \varphi (a)$, set $b:=m$. Otherwise, if $\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(m)\mathrm{\mid }\le c_2\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(0)\mathrm{\mid }$, return $m$ as a strong Wolfe step. In the remaining branch, if ${\varphi }^{\mathrm{\prime }}(m)(b-a)\ge 0$, first set $b:=a$; then set $a:=m$.
3. If the zoom budget is exhausted, return evaluation-budget-exhausted.

The procedure returns a step only after both strong Wolfe inequalities have been checked. Finite budgets and domain exits may return failure even when a strong Wolfe step exists; no convergence claim follows from the procedure alone.