Golden rectangle search

solve for one variable

• golden rectangle search
• fastest search algorithm to find the minimum of unimodal function
• assume the function is:  y = f(x)
• tau = (1. + sqrt(5.))/2 ; golden rectangle constant of 1.61803
• lower bound = x1
• higher bound = x4
• minimum lies between x1 and x4
• one interation
• set x3 = (x4 - x1) * tau 
• set x2 = x1 + (x4 - x3)
• evaluate y1 = f(x1), y2 = f(x2), y3 = f(x3), y4 = f(x4)
• eliminate x1 if
• y3 gt y2
• eliminate x4 if
• y2 gt y3
• each iteration reduces the interval to 61.8 % of its original interval
• reduction factor after n intervals
• 1 = 61.8 %
• 5 = 9.0 %
• 10 = .81 %
• 15 = .073 %
• 20 = .006 %
• 25 = .00059 %
• 30 = .000053 %
• 15 intervals is OK for most solutions
• 10 intervals is sufficient for rough solutions
• 20 intervals is plausible for precise solutions
• number of function calls = (number of intervals + 3)
• nested golden rectangle search
• nesting of the search is needed to solve multiple things at once
• for example: solve for
• weight between 450 pounds and 600 pounds
• mast side slop between 5 degrees and 20 degrees
• lap time for the optimum VMG courses (upwind and downwind)
• boat angle between 10 degrees and 80 degrees upwind
• boat angle between 100 degrees and 170 degrees downwind
• boat speed between (.5 * TrueWindSpeed) and (5 * TrueWindSpeed)
• total function calls = (10 + 3){weight} * (10 * 3){slop} * 2{Upwind-Downwind} * (12 + 3){VMG} * (15 *3){SPEED}
• total function calls = 76,050 for above solution  

.