Line Search Algorithm Assignment Help

Line search algorithms

1. Uniform search
2. Dichotomous search
3. Golden section search
4. Quadratic fit search

1. Uniform Search

Pick the search points α₁,α₂,.....,α_n so that they are uniformly spaced over some preset range α

• α^* = argminα∈α₁,α₂,.....,α_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 α₁, α₂ and α₃ such that ƒ(α₁) ≥ ƒ(α₂) and ƒ(α₂) ≤ ƒ(α₃)
• Find α^* as the minimum to the quadratic fit of ƒ(α₁), ƒ(α₂), and ƒ(α₃)
• If α α₂,
  if ƒ(α^*) ƒ (α₂), then α_new = α₁, α₂, α^*
  if ƒ(α^*) ≤ ƒ (α₂), then α_new = α₂, α^*, α₃
  
  Else
  
  if ƒ(α^*) ƒ (α₂), then α_new = α^*, α₂, α₃
  if ƒ(α^*) ≤ ƒ(α₂), then α_new = α₁, α^*, α₂
  
• Loop to 2 until convergence