Line search

Definition

Line search is one of two strategies (the other being trust region) used in iterative procedures intended to solve optimization problems. For simplicity, we restrict attention here to minimization problems, though everything said here can be adapted to maximization problems as well.

The key idea behind the iterative step of line search is:

Identify a descent direction.
Determine the step size to move in that descent direction to loosely minimize the value of the objective function when restricted to the line of that descent direction. The goal is not always to find a local or absolute minimum along the line, but rather to make a move that guarantees at least a certain quantity of reduction.

Mathematical formalism

In symbols, suppose $f$ is the function we are trying to minimize, ${\vec{x}}_{k}$ is the preceding guess, and ${\vec{p}}_{k}$ is the descent direction. The next guess ${\vec{x}}_{k + 1}$ is obtained as ${\vec{x}}_{k} + α {\vec{p}}_{k}$ , where the real number $α$ is to be determined.

We are trying to minimize $h (α) = f ({\vec{x}}_{k} + α {\vec{p}}_{k})$ over choices of $α$ . If it is computationally feasible to minimize $h$ directly, that is great. Otherwise, we use other methods to find a value of $α$ that is guaranteed to result in at least a certain amount of decrease in $f$ . Approaches that exactly minimize $h$ are given the name exact line search, whereas other approaches are given the name inexact line search.