# Difference between revisions of "Line search methods"

Line 12: | Line 12: | ||

=Step Length= | =Step Length= | ||

− | Choosing an appropriate step length has a large impact on the robustness of a line search method. | + | 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: |

− | <math>\phi(\alpha) = f(x_k+\alpha p_k), \alpha >0 </math> | + | <math>\phi(\alpha) = f(x_k+\alpha p_k), \alpha >0 </math>, |

+ | |||

+ | 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 <math>\phi</math> has multiple local minima or stationary points, as shown in Figure 1. | ||

+ | |||

+ | [[File:Step length image.png|frame|Complexity of finding ideal step length (Nocedal & Wright)]] | ||

=Step Direction = | =Step Direction = |

## Revision as of 11:15, 24 May 2015

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 , an initial is chosen. To find a lower value of , the value of is increased by the following iteration scheme

in which is a positive scalar known as the step length and 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:

,

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 has multiple local minima or stationary points, as shown in Figure 1.

# Step Direction

## Steepest Descent Method

## Newton Method

## Quasi-Newton Method

# Conclusion

# 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.