Linkage

• Continuous search
  • plan space - looking for a good point in space, not a good path
• Relate to reinforcement learning
  • Search over the space of policies for one that optimises sum of reward

Function minimization/maximization/optimization

• [http://www.library.cornell.edu/nr/bookcpdf.html Numerical Recipies in C] - chapter 10
• [http://www.ece.northwestern.edu/~nocedal/book/num-opt.html Wright and Nocedal - Numerical Optimization]

Optimization without gradients

• evaluate a function at a given point
  • minimize (or maximise) function
  • avoid estimating derivative for this lecture
• Simulated Annealing
  • Bounce around (usually using using Boltzmann exploration)
  • proof of convergence given infinite time
• Downhill Simplex Method in Multi-dimensions
  • How do you bracket a minimum in multiple dimensions?
  • Triangulation - simplex
  • Very robust algorithm - often not fast, but generally does surprisingly well
  • Simplex 'rolls' down hill
    • Options
    • Reflection - highest point is refected through opposite plane
    • Reflection and expansion - like reflection, but dist through opposing plane is doubled
    • Contraction - half dist from highest point to opposing plane
    • Multiple contraction - move all points in plane opposing min point half dist to min point
    • Routine
    • First try to lower highest point
      • Reflect it
      • If the reflection is better than min point then
      • try expanding in that dir
      • If the reflection is still the worst point then
      • try a simple contraction
      • If the simple contraction is STILL the worst point then
        • try a multiple contraction
• Line minimization (1D)
  • 1D search for roots - binary search
    • Bracket min with 2 pts
  • 1D search for a minimum - Golden ratio search
    • Bracket min with 3 pts
    • Choosing new point given (a, b, c)
      • let b be a fraction w between a and c (p 399)
      • (normalise dists so (c-a) is unit length
      • our next point, x, will be an additional fraction z beyond b
      • similar formula
      • again, (c-a) is the normalisation factor
      • length of next segment is either
      • (w + z), or (1 - w)
      • make these equal - binary search
      • w + z = 1 - w => z = 1 - 2w => z > 0 iff w > 0.5 => x falls in larger of gap
      • Now use recursive similarity argument
      • z/(1-w) = w
      • w solves to be (3 - sqrt(5)) / 2 - related to the golden ratio
    • Parabolic search (p402)
    • A parabola could have a min or max...
    • Need to mix parabolic fit with Golden ratio search
    • Brent's method
      • Parabolic fit must fall within current range
      • Movement from the current best value must be less than half the step before last
      • One bad step allowed, not two
• Multidimensional line minimisation methods
  • Do line minimisation in one direction (1D minimization)
  • Pick a new direction and do another minimization
  • Talk about how to "pick a direction" next lecture
    • generally NOT able to pick the direction to the minimum - have to do repeated line minimizations.