Line search

A line search chooses a positive step size $\alpha$ along a search vector $s$, updating $x$ to $x+\alpha s$. For a differentiable function $f$, a descent direction makes sufficiently short steps decrease the objective function; an Armijo condition quantifies the decrease, while the Wolfe conditions also prevent accepting an unnecessarily short step.

Suppose $f$ is bounded below on its initial level set, continuously differentiable with a Lipschitz gradient nearby, and each descent direction $p_k$ uses a step satisfying fixed Wolfe conditions. If $\cos {\theta }_k=-\nabla f(x_k{)}^T{p}_k/(\Vert \nabla f(x_k)\Vert \Vert p_k\Vert )$, the displayed series converges. In particular a uniform positive lower bound on these cosines gives $\nabla f(x_k)\to 0$.

For a gradient Lipschitz constant $L$, the curvature condition gives ${\alpha }_k\ge (1-\eta )(-\nabla f^T{p}_k)/(L\Vert p_k{\Vert }^2)$. Sufficient decrease then gives $f(x_k)-f(x_{k+1})\ge \sigma (1-\eta ){\cos }^2{\theta }_k\Vert \nabla f(x_k){\Vert }^2/L$. Summing and using the lower bound on $f$ proves the assertion.

A search direction is the nonzero vector $p_j$ used in the displayed optimization update. In a line search with positive step size, its orientation matters: a descent direction has negative directional derivative of the objective function. Minimization over a full line instead permits either sign of ${\alpha }_j$.

A line search that finds a global minimizer along the chosen ray, provided one exists. For a negative gradient direction, its decrease in the objective function is at least that of any admissible fixed step size. The cost of solving this one-dimensional minimization problem must be included when comparing computation time.

Target: vector-space.bigb, under Vector subspace.

A vector $s$ is a descent direction for a differentiable function $f$ at $x$ if its directional derivative $\nabla f(x{)}^{T}s$ is negative. The first-order expansion $f(x+\alpha s)=f(x)+\alpha \nabla f(x{)}^{T}s+o(\alpha )$ then gives $f(x+\alpha s)<f(x)$ for sufficiently small positive $\alpha$. The negative gradient is a descent direction whenever the gradient is nonzero.

For a nonzero gradient, this unit direction minimizes the directional derivative among Euclidean unit directions. The Cauchy-Schwarz inequality gives $\nabla f(x{)}^{T}p\ge -\Vert \nabla f(x){\Vert }_2$, with equality for the displayed direction. The steepest descent method usually uses the equivalent unnormalized direction $-\nabla f(x)$ and chooses a separate step length. A different choice of norm can change the steepest direction.

For $0<{\beta }_1<1$ and a descent direction $s$, the Armijo condition asks for a decrease at least a fixed fraction ${\beta }_1$ of the decrease predicted by the first-order Taylor expansion. Put $d=\nabla f(x{)}^{T}s<0$. Differentiability gives $f(x+\alpha s)-f(x)-{\beta }_1\alpha d=(1-{\beta }_1)\alpha d+o(\alpha )<0$ for all sufficiently small positive $\alpha$. Thus the condition is satisfiable without a second derivative.

Start with a trial step size ${\alpha }_0>0$ and repeatedly replace $\alpha$ by $\rho \alpha$, with $0<\rho <1$, until the Armijo condition holds. For a differentiable function and a descent direction, the short-step argument in the Armijo condition proves finite termination. This alone does not enforce the curvature part of the Wolfe conditions.

For a continuously differentiable function, a descent direction $s$ and $0<{\beta }_1<{\beta }_2<1$, the Wolfe conditions require both the Armijo condition andThis second inequality is the weak curvature condition: the slope must have become less negative. The strong variant instead requires $|\nabla f(x+\alpha s{)}^{T}s|\le {\beta }_2|\nabla f(x{)}^{T}s|$. The weak version already guarantees a positive curvature pair for the Quasi-Newton secant equation.

Suppose $f$ is continuously differentiable, $s$ is a descent direction, and $f(x+\alpha s)$ is bounded below for $\alpha \ge 0$. A positive step size satisfying the weak Wolfe conditions exists. To prove this, put $\varphi (\alpha )=f(x+\alpha s)$, $d={\varphi }^{\prime }(0)<0$, and $h(\alpha )=\varphi (\alpha )-\varphi (0)-{\beta }_1\alpha d$. The Armijo condition proof shows $h<0$ just to the right of zero. Boundedness below gives $h(\alpha )\to +\infty$. Consequently there is a first positive zero $A$, with $h\le 0$ on $[0,A]$. By the mean value theorem, some $t\in (0,A)$ satisfiesAt $t$, $h(t)\le 0$ gives the Armijo condition, and the displayed derivative gives the weak Wolfe conditions.