Line search methods

From optimization
Revision as of 21:28, 24 May 2015 by Epc257 (Talk | contribs)

Jump to: navigation, search

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

Contents

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


CodeCogsEqn.gif,


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:

CodeCogsEqn (2).gif,

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.

Figure 1: Complexity of finding ideal step length (Nocedal & Wright)

A common and practical method for finding a suitable step length that is not too near to the global minimum of the \phi function is to require that the step length of \alpha_k reduces the value of the target function, or that

CodeCogsEqn (3).gif

This method does not ensure a convergence to the function's minimum, and so two conditions are employed to require a significant decrease condition during every iteration.

Wolfe Conditions

Step Direction

Steepest Descent Method

Newton Method

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.