Golden Section Search - Recursive Algorithm

Recursive Algorithm

double phi = (1 + Math.sqrt(5)) / 2; double resphi = 2 - phi; // a and c are the current bounds; the minimum is between them. // b is a center point // f(x) is some mathematical function elsewhere defined // a corresponds to x1; b corresponds to x2; c corresponds to x3 // x corresponds to x4 public double goldenSectionSearch(double a, double b, double c, double tau) { double x; if (c - b > b - a) x = b + resphi * (c - b); else x = b - resphi * (b - a); if (Math.abs(c - a) < tau * (Math.abs(b) + Math.abs(x))) return (c + a) / 2; assert(f(x) != f(b)); if (f(x) < f(b)) { if (c - b > b - a) return goldenSectionSearch(b, x, c, tau); else return goldenSectionSearch(a, x, b, tau); } else { if (c - b > b - a) return goldenSectionSearch(a, b, x, tau); else return goldenSectionSearch(x, b, c, tau); } }

To realise the advantage of golden section search, the function would be implemented with caching, so that in all invocations of goldenSectionSearch(..) above, except the first, would have already been evaluated previously — the result of the calculation will be re-used, bypassing the (perhaps expensive) explicit evaluation of the function. Together with a slightly smaller number of recursions, this 50% saving in the number of calls to is the main algorithmic advantage over Ternary search.