Golden Section

Overview


The golden section search method is a simple optimization method for optimizing a function of a single variable.

The golden section optimization works similar to the root finding technique, bisection.

First, an interval is identified which is known to contain a single maximum (or minimum), call it {% [x_l, x_u] %}. Two addition points are chosen within the interval, ({% x_1,x_2 %}), chosen such that {% x_1 < x_2 %} and {% x_1 - x_l = x_u - x_2 %}. The the algorithm tests for whether the maximum occurs within the first three points, or the second three points.

Define
  • {% l_0 = x_u-x_l %}
  • {% l_2 = x_1-x_l %}
  • {% l_1 = x_2-x_l %}
Then we have
{% l_0 = l_1 + l_2 %}
Choose ({% x_1,x_2 %}) such that
{% \frac{l_1}{l_0} = \frac{l_2}{l_1} %}
Then the algorithm proceeds recursively to narrow the interval by identifying which three points the maximum appears in. chapra - pg. 356

Algorithm


The golden secion library can be found at the following. 


'/lib/optimization/v1.0.0/golden-section.mjs'


The following is a simple example of running a golde section search. 


let op = await import('/lib/numeric/optimization/v1.0.0/golden-section.mjs');

let f = function(x){
  return -1*(x-5)*(x-5);
}

let test = op.optimize(f,-10, 10, 0.001);
Try it!

Contents