.

# Line Search Algorithm Assignment Help

## Line search algorithms

- Uniform search
- Dichotomous search
- Golden section search
- Quadratic fit search

### 1. Uniform Search

Pick the search points α_{1},α_{2},.....,α_{n} so that they are uniformly spaced over some preset range α

- α
^{*}= argminα∈α_{1},α_{2},.....,α_{n}ƒ(α) - + No assumptions about convexity or shape of ƒ(α)
- + Finds (nearly) a global minimum
- - Relatively inefficient

### 2. Dichotomous search

Suppose you know that α is in the range of α_{min} to α_{max}

- calculate the following evaluation points

- Otherwise, set α
_{min}= b - Repeat until convergence
- If the derivative dƒ(α)⁄dα can be calculated, the computation can be reduced to one evaluation of the derivative per an iteration.
- If the derivative is used, this is called bisection method.

### 3. Golden section line search

Suppose you know that α is in range of α_{min} to α_{max}

Loop to 2 until convergence

### 4. Quadratic fit line search

- Find α
_{1}, α_{2}and α_{3}such that ƒ(α_{1}) ≥ ƒ(α_{2}) and ƒ(α_{2}) ≤ ƒ(α_{3}) - Find α
^{*}as the minimum to the quadratic fit of ƒ(α_{1}), ƒ(α_{2}), and ƒ(α_{3}) - If α α
_{2},

if ƒ(α^{*}) ƒ (α_{2}), then α_{new}= α_{1}, α_{2}, α^{*}

if ƒ(α^{*}) ≤ ƒ (α_{2}), then α_{new}= α_{2}, α^{*}, α_{3}

Else

if ƒ(α^{*}) ƒ (α_{2}), then α_{new}= α^{*}, α_{2}, α_{3}

if ƒ(α^{*}) ≤ ƒ(α_{2}), then α_{new}= α_{1}, α^{*}, α_{2}

- Loop to 2 until convergence

.