Line search methods

Authors: Lihe Cao, Zhengyi Sui, Jiaqi Zhang, Yuqing Yan, and Yuhui Gu (6800 Fall 2021).

Introduction

When solving unconstrained optimization problems, the user need to supply a starting point for all algorithms. With the initial starting point, $x_{0}$, optimization algorithms generate a sequence of iterates $\{x_{k}\}_{k=0}^{\infty }$ which terminates when an approximated solution has been achieved or no more progress can be made. Line Search is one of the two fundamental strategies for locating the new $x_{k+1}$ given the current point.

Generic Line Search Method

Basic Algorithm

• Pick an initial iterate point $x_{0}$
• Repeat the following steps until $x_{k}$ converge:
  • Choose a descent direction $p_{k}$ starting at $x_{k}$, defined as if $\nabla f_{k}\not =0$, then $\nabla f_{k}^{\top }p_{k}<0$
  • Calculate a decent step length $\alpha >0$ so that $f(x_{k}+\alpha _{k}p_{k})<f_{k}$
  • Set $x_{k+1}=x_{k}+\alpha _{k}p_{k}$

Search Direction for Line Search

The direction of the line search should be chosen to make $f$ decrease moving from point $x_{k}$ to $x_{k+1}$. The most obvious direction is the $-\nabla f_{k}$ because it is the one to make $f$ decreases most rapidly. We can verify the claim by Taylor's theorem:

$f(x_{k}+\alpha )=f(x_{k})+\alpha p^{\top }\nabla f_{k}+{\frac {1}{2}}\alpha ^{2}p^{T}f(x_{k}+tp)p$ where $t\in (0,\alpha )$

The rate of change in $f$ along the direction $p$ at $x_{k}$ is the coefficient of $\alpha$. Therefore, the unit direction $p$ of most rapid decrease is the solution to

$\min \ p^{\top }\nabla f_{k}$

${\text{s.t.}}\ \ ||p||=1$.

$p={\frac {-\nabla f_{k}}{||\nabla f_{k}||}}$ is the solution and this direction is orthogonal to the contours of the function. In the following sections, we will use this as the default direction of the line search.

Step Length

The step length is a non-negative value such that $f(x_{k}+\alpha _{k}p_{k})<f_{k}$. When choosing the step length $\alpha _{k}$, we need to trade off between giving a substantial reduction of $f$ and not spending too much time finding the solution. If $\alpha _{k}$ is too large, then the step will overshoot, while if the step length is too small, it is time consuming to find the convergent point. We have exact line search and inexact line search to find the value of $\alpha$ and more detail about these approaches will be introduced in the next section.

Convergence

For a line search algorithm to be reliable, it should be globally convergent, that is the gradient norms, $||\nabla f(x_{k})||$, should converge to zero with each iteration, i.e., $\lim _{k\to \infty }||\nabla f(x_{k})||=0$.

It can be shown from Zoutendijk's theorem that if the line search algorithm satisfies (weak) Wolfe's conditions (similar results also hold for strong Wolfe and Goldstein conditions) and has a search direction that makes an angle with the steepest descent direction that is bounded away from 90°, the algorithm is globally convergent.

Zoutendijk's theorem states that, given an iteration where $p_{k}$ is the descent direction and $\alpha _{k}$ is the step length that satisfies (weak) Wolfe conditions, if the objective $f$ is bounded below on $\mathbb {R} ^{n}$ and is continuously differentiable in an open set ${\mathcal {N}}$ containing the level set ${\mathcal {L}}:=\{x\ |\ f(x)\leq f(x_{0})\}$, where $x_{0}$ is the starting point of the iteration, and the gradient $\nabla f$ is Lipschitz continuous on ${\mathcal {N}}$, then

$\sum _{k=0}^{\infty }\cos ^{2}\theta _{k}||\nabla f_{k}||^{2}<\infty$,

where $\theta _{k}$ is the angle between $p_{k}$ and the steepest descent direction $-\nabla f(x_{k})$.

The Zoutendijk condition above implies that

$\lim _{k\to \infty }\cos ^{2}\theta _{k}||\nabla f_{k}||^{2}=0$,

by the n-th term divergence test. Hence, if the algorithm chooses a search direction that is bounded away from $90^\circ$ relative to the gradient, i.e., given $\epsilon >0$,

$\cos \theta _{k}\geq \epsilon >0,\ \forall k$,

it follows that

$\lim _{k\to \infty }||\nabla f_{k}||=0$.

However, the Zoutendijk condition doesn't guarantee convergence to a local minimum but only stationary points. Hence, additional conditions on the search direction is necessary, such as finding a direction of negative curvature, to prevent the iteration from converging to a nonminimizing stationary point.

Exact Search

Steepest Descent Method

Given the intuition that the negative gradient $-\nabla f_{k}$ can be an effective search direction, steepest descent follows the idea and establishes a systematic method for minimizing the objective function. Setting $-\nabla f_{k}$ as the direction, steepest descent computes the step-length $\alpha _{k}$ by minimizing a single-variable objective function. More specifically, the steps of Steepest Descent Method are as follows.

Steepest Descent Algorithm

Set a starting point $x_{0}$

Set a convergence criterium $\epsilon >0$

Set $k=0$

Set the maximum iteration $N$

While $k\leq N$:

$\nabla f(x_{k})=\left.{\frac {\partial f(x)}{\partial x}}\right\vert _{x=x_{k}}$

If $\nabla f(x_{k})\leq \epsilon$:

Break

End

$\alpha _{k}={\underset {\alpha }{\arg \min }}f(x_{k}-\alpha \nabla f(x_{k}))$

$x_{k+1}=x_{k}-\alpha _{k}\nabla f(x_{k})$

$k=k+1$

End

Return $x_{k}$, $f(x_{k})$

One advantage of the steepest descent method is that it has a nice convergence theory. For a steepest descent method, it converges to a local minimal from any starting point.

Theorem: Global Convergence of Steepest Descent

Let the gradient of $f\in C^{1}$ be uniformly Lipschitz continuous on $\mathbb {R} ^{n}$. Then, for the iterates with steepest-descent search directions, one of the following situations occurs:

• $\nabla f(x_{k})=0$ for some finite $k$
• $\lim _{k\to \infty }f(x_{k})=-\infty$
• $\lim _{k\to \infty }\nabla f(x_{k})=0$

Steepest descent method is a special case of gradient descent in that the step-length is rigorously defined. Generalization can be made regarding the choice of $\alpha$.

Inexact Search

When we minimize the objective function using numeric methods, in each iteration, the updated objective is $\phi (\alpha )=f(x_{k}+\alpha p_{k})$, a function of $\alpha$ when we fix the direction. Our goal is to minimize the objective with respect to $\alpha$. However, sometimes if we want to solve for the exact minimum in each iteration, it might be computationally expensive and the algorithm will be time consuming. Therefore, in practice we just solve the subproblem

${\underset {\alpha }{min}}\quad f(x_{k}+\alpha p_{k})$

approximately and find a suitable step length $\alpha$ instead, which will decrease the objective function. That is, $\alpha$ satisfies $f(x_{k}+\alpha p_{k})\leq f(x_{k})$.A problem is, we can not guarantee the convergence to the function's minimum, so we often apply the following conditions to find an acceptable step length.

Wolfe Conditions

This condition is proposed by Phillip Wolfe in 1969. It provide an efficient way of choosing a step length that decreases the objective function sufficiently. It consists of two conditions, Armijo condition and curvature condition.

$(1)\quad {\textbf {Armijocondition}}$

$f(x_{k}+\alpha p_{k})\leq f(x_{k})+c_{1}\alpha _{k}p_{k}^{\top }\nabla {f(x_{k})}$ where $c_{1}$ is between 0 and 1 and is often chosen to be of a small order of magnitude around 10E-4. This condition ensures the computed step length can reduces the objective function $f(x_{k})$ sufficiently. Only using this condition, we can't guarantee $x_{k}$ to converge, since Armijo condition is always satisfied with step length that is small enough. Therefore, we need to pair it with the second condition below, in order to keep $\alpha _{k}$ from being too short.

$(2)\quad {\textbf {Curvaturecondition}}$ $-p_{k}\nabla {f(x_{k}+\alpha p_{k})\leq c_{2}p_{k}^{\top }f(x_{k})}$ where $c_{2}$ is much greater than $c_{1}$ and is often chosen in the magnitude of 0.1. This condition ensures the slope to decrease sufficiently.

$(2)^{*}\quad {\textbf {StrongWolfeconditiononcurvature}}$

The Wolfe condition can result in a value that is not close to the minimizer of $\phi {\alpha }$. We can modify the Wolfe condition by using the following condition called Strong Wolfe condition to replace the curvature condition in $(2)$. $|p_{k}\nabla {f(x_{k}+\alpha p_{k})|\leq c_{2}|p_{k}^{\top }f(x_{k}))}|$

This left hand side of the strong curvature condition is simply the derivative of the $\phi (\alpha )$, thus can ensure $\alpha _{k}$ to lie close to a critical point of $\phi (\alpha )$.

Goldstein Conditions

Another condition to find an appropriate step length is called Goldstein conditions.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_k) + (1-c) \alpha_k \nabla{f^T_k} \bm{p}_k \leq f(x_k + \alpha \bm{p}_k) \leq f(x_k) + c \alpha_k \nabla{f^T_k} \bm{p}_k}

where $0\leq c\leq 1/2$. The Goldstein condition is quite similar with the Wolfe condition in that, its second inequality ensures that the step length $\alpha$ will decrease the objective function sufficiently and its first inequality keep $\alpha$ from being too short. In comparison with Wolfe condition, one disadvantage of Goldstein condition is that the first inequality of the condition might exclude all minimizers of $\phi$ function. However, usually it is not a fatal problem as long as the objective decrease in the direction of convergence. As a short conclusion, the Goldstein and Wolfe conditions have quite similar convergence theories. Compared to the Wolfe conditions, the Goldstein conditions are often used in Newton-type methods but are not well suited for quasi-Newton methods that maintain a positive definite Hessian approximation.

Backtracking

The backtracking method is often used to find the appropriate step length and terminate line search. The backtracking method starts with a relatively large initial step length (e.g., 1 for Newton method), then iteratively shrinking it by a contraction factor until the Armijo (sufficient decrease) condition is satisfied. The advantage of this approach is that the curvature condition needs not be considered, and the step length found at each line search iterate is ensured to be short enough to satisfy sufficient decrease but large enough to still allow the algorithm to make reasonable progress towards convergence.

The backtracking algorithm involves control parameters $\rho \in (0,1)$ and $c\in (0,1)$.