Wolfe and strong Wolfe line-search conditions

Let $D\subseteq {\mathbb{R}}^n$ be open, let $f:D\to \mathbb{R}$ be $C^1$ (Continuously differentiable maps, local inverses, and local diffeomorphisms), let $x\in D$, and let $p\in {\mathbb{R}}^n\setminus \{0\}$. Define the open parameter set $S_{x,p}:=\{t\in \mathbb{R}:x+tp\in D\}$, which contains $0$, the feasible ray $T_{x,p}:=S_{x,p}\cap [0,\mathrm{\infty })$, and $\varphi (t):=f(x+tp)$ for $t\in S_{x,p}$. At every $t\in S_{x,p}$, including $0$, the chain rule gives ${\varphi }^{\mathrm{\prime }}(t)=Df(x+tp)p$. By A total derivative computes every directional derivative, and its matrix is the Jacobian, the matrix of $Df$ is the Jacobian, whose scalar-field row is the transpose of the gradient. Hence ${\varphi }^{\mathrm{\prime }}(t)=⟨\mathrm{\nabla }f(x+tp),p⟩$, using the gradient convention of The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case and the Euclidean inner product of The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$. A direction is a descent direction at $x$ when ${\varphi }^{\mathrm{\prime }}(0)=⟨\mathrm{\nabla }f(x),p⟩<0$.

Assume for the line-search conditions below that $p$ is a descent direction at $x$. Fix constants $0<c_1<c_2<1\mathrm{/}2$. A feasible step $t>0$ is a Wolfe step when

$$\varphi (t)\le \varphi (0)+c_{1}t{\varphi }^{\mathrm{\prime }}(0),{\varphi }^{\mathrm{\prime }}(t)\ge c_2{\varphi }^{\mathrm{\prime }}(0)\mathrm{.}$$

It is a strong Wolfe step when it satisfies the first inequality and

$$\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(t)\mathrm{\mid }\le c_2\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(0)\mathrm{\mid }\mathrm{.}$$

The first inequality is the Armijo sufficient-decrease condition. The second Wolfe inequality is the curvature condition. Every strong Wolfe step is a Wolfe step, because ${\varphi }^{\mathrm{\prime }}(0)<0$ and the strong curvature bound implies ${\varphi }^{\mathrm{\prime }}(t)\ge -c_2\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(0)\mathrm{\mid }=c_2{\varphi }^{\mathrm{\prime }}(0)$.

For a descent direction define its descent angle $\theta \in [0,\pi \mathrm{/}2)$ by

$$\cos \theta :=-\frac{⟨\mathrm{\nabla }f(x),p⟩}{\mathrm{\parallel }\mathrm{\nabla }f(x){\mathrm{\parallel }}_2\mathrm{\parallel }p{\mathrm{\parallel }}_2}\mathrm{.}$$

The denominator is nonzero for a descent direction. The Cauchy–Schwarz inequality Cauchy-Schwarz $\mid ⟨x,y⟩\mid \le \parallel x{\parallel }_2\parallel y{\parallel }_2$ with its equality case, the triangle inequality for $\parallel \cdot {\parallel }_2$, the parallelogram law and polarisation ensures $0<\cos \theta \le 1$.