Line search methods

Author names: Elizabeth Conger
Steward: Dajun Yue and Fengqi You

Introduction

An algorithm is a line search method if it seeks the minimum of a defined nonlinear function by selecting a reasonable direction vector that, when computed iteratively with a reasonable step size, will provide a function value closer to the absolute minimum of the function. Varying these will change the "tightness" of the optimization. For example, given the function $f(x)$, an initial $x_k$ is chosen. To find a lower value of $f(x)$, the value of $x_{k+1}$ is increased by the following iteration scheme

,

in which $\alpha_k$ is a positive scalar known as the step length and $p_k$ defines the step direction.

Step Length

Choosing an appropriate step length has a large impact on the robustness of a line search method. To select the ideal step length, the following function could be minimized:

$\phi(\alpha) = f(x_k+\alpha p_k), \alpha >0$,

but this is not used in practical settings generally. This may give the most accurate minimum, but it would be very computationally expensive if the function $\phi$ has multiple local minima or stationary points, as shown in Figure 1.

Complexity of finding ideal step length (Nocedal & Wright)

Step Direction

Quasi-Newton Method

Solution to 48 States Traveling Salesman Problem

Conclusion

$\begin{bmatrix} G(x,y) & 0 & -A(x)^T \\ 0 & Y & W \\ A(x) & -I & 0 \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta s \\ \Delta y \end{bmatrix} = \begin{bmatrix} -\nabla f(x) + A(x)^T y \\ \mu e - W Y e \\ -g(x) + s \end{bmatrix}$

References

1. Sun, W. & Yuan, Y-X. (2006) Optimization Theory and Methods: Nonlinear Programming (Springer US) p 688.

2. Anonymous (2014) Line Search. (Wikipedia). http://en.wikipedia.org/wiki/Line_search.

3. Nocedal, J. & Wright, S. (2006) Numerical Optimization (Springer-Verlag New York, New York) 2 Ed p 664.