Golden Section Search algorithm, golden number why is 0.381

Hi guys, i don't understand why in tha code bellow (which works just fine) i don't understand why tau (the golden number) is 0.381.. ? I mean everywhere i look the golden number is 1.618 and if i change the constant value from 0.381 in 1.618 the code doesn't find the minimum of the function anymore. Any help is welcome. Kind regards

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% MATLAB code golden.m

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

% a -> lower bound of the design variable

% b -> upper bound of the design variable

% alpha -> midpoint of a and b

% falpha1 -> function value at x = alpha1

% falpha2 -> function value at x = alpha2

% epsilon -> constant used to terminate the algorithm

% abs -> absolute of a number, MATLAB function

% tau -> 2-golden number

%

clear all

clc

a = 40;

b = 90;

epsilon = 0.00001;

tau = 0.381967;

alpha1 = a*(1-tau) + b*tau;

alpha2 = a*tau + b*(1-tau);

falpha1 = func(alpha1);

falpha2 = func(alpha2);

fprintf(' a b \n')

fprintf('-------------------------\n')

for i = 1:100

fprintf(' %7.3f %8.3f \n',a,b)

if falpha1 > falpha2

a = alpha1;

alpha1 = alpha2;

falpha1 = falpha2;

alpha2 = tau*a + (1-tau)*b;

falpha2 = func(alpha2);

else

b = alpha2;

alpha2 = alpha1;

falpha2 = falpha1;

alpha1 = tau*b + (1-tau)*a;

falpha1 = func(alpha1);

end

if abs(func(alpha1)-func(alpha2)) < epsilon

break;

end

end

fprintf('-------------------------\n')

fprintf('x* = %7.3f Minimum = %8.3f\n',alpha1,func(alpha1))

fprintf('Number of function calls = %3d\n',2+i)

%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% MATLAB code func.m

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% objective function to be coded here

% different test functions

%

function fx = func(x)

fx = 204165.5/(330-2*x) + 10400/(x-20);

% fx = 3*x^4+(x-1)^2;

% fx = -4*x*sin(x);

% fx = 2*(x-3)^2+exp(0.5*x*x);

%fx = 3*(x)^2+12/(x^3)-5;

% fx = 2*x*x+16/x;

%

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Answer 1

[John D'Errico]

I think you need to spend some time in class listening, lol. Or, maybe your instructor did not explain this. It is very possible your instructor just glossed over these points. I do accept that as possible too. A teacher has only so much time to spend in class, and some things just seem obvious to a teacher, so they assume it will be just as obvious to the student. So let me do my best to motivate where 0.381966011250105... came from, and how the golden ratio gets into this algorithm.

We have tau to 6 digits as:

tau = 0.381967; % really 0.381966011250105...

How is tau used? In places always like this

alpha2 = a*tau + b*(1-tau);

That is, tau is always used to form a convex linear combination between two end points. You can find more about that term at this link:

https://en.wikipedia.org/wiki/Convex_combination

But consider what it would mean if tau were 0. What would we see? In that case, alpha2 would always result as b. This would always select the point b, because the coefficient of a is zero.

Likewise, were tau the number 1, we always get the other end point at a, because then the coefficient of b would be zero.

How about tau = 1/2? Then the combination gives us EXACTLY the midpoint between the two, since we then have

alpha2 = a*tau + b*(1-tau) = (a + b)/2

when tau is 1/2. One feature of the search, if we had used tau=1/2, is the search would now reduce to the bisection method.

What you need to recognize is that for various values of tau, we would get SOME point between a and b ONLY when tau is a number between zero and 1. For numbers larger than 1, or smaller than 0, alpha is no longer inside the interval [a,b]. I know, you don't believe me. So TRY IT!

a = 0;
b = 1;
tau = 1.61803398874989;

a*tau + b*(1-tau)
ans =
        -0.618033988749895

So if I use tau as 1.618, I do indeed get some value that is no longer even inside the original interval. In fact, this is a basic property of that convex combination we mentioned above. We need to use a number strictly between 0 and 1 in that formula.

So how does the name of the phrase golden section search arise?

I'll write phi as the golden number you know and love:

phi = (sqrt(5) + 1)/2
phi =
          1.61803398874989

phi has some neat properties as a number. If you form the inverse, you will see what results is the fractional part of the original number.

1/phi
ans =
         0.618033988749895

So if we form

1 + 1/phi
ans =
          1.61803398874989

we get phi back all over again!

Anyway, it is this golden ratio that is so nice, and seems to turn up all over the place, in art, in spirals from nature, etc. phi even arises as the limit of the ratio of two consecutive Fibonacci numbers. It falls out of all sorts of things. Have you heard enough about phi as the golden ratio now? Getting just a bit sick of it?

What value of tau were you given to use? We were given tau as:

tau = 0.381966011250105

In the convex combination thing, effectively this splits the interval [0,1] into two segments, of relative length tau and 1-tau. What is the ratio of the lengths of those segments? TRY IT! Aw, come on, guess. I bet it will take onliy one guess at this point.

(1-tau)/tau
ans =
          1.61803398874989

Indeed, the value of tau you were given to use is the exact number that causes the two pieces formed by the convex combination of the endpoints of the interval [a,b] to have a relative ratio that just happens to be the golden ratio. We just cannot escape that number, can we? Do anything, and it pops up again. In the back of my head, I can just hear Ahnuld saying the phrase "I'll be back..."

In fact, we can compute the exact value of tau as

tau = 1-1/phi
tau =
         0.381966011250105

To recoup all of this, the idea is the golden section search splits the interval [a,b] into two pieces based on a convex linear combination. Those two pieces of the interval, thus of relative lengths tau and 1-tau, themselves have the property that the ratio of their lengths is the golden ratio that you know and love.

In fact, either way we take that ratio, we still seem to get phi back. And it matters not which way we form that ratio.

(1 - tau)/tau
ans =
          1.61803398874989
          
tau/(1 - tau)
ans =
         0.618033988749895

I could get into more depth about how this choice of tau is in some way a good one, but I've spent now much time in an attempt to motivate the concept of a convex linear combination, and where the name golden section search comes from. If you want a derivation, it might be just as useful to read what is already written about the search:

https://en.wikipedia.org/wiki/Golden-section_search

[Emil Bucur]

wow, thanks a lot, now these things make more sense to me. You are the best

Answer 2

[Are Mjaavatten]

Let a and b be the end points of the current range. In golden ratio search we choose a new point c such that the ratio of the two lengths and is given by the golden ratio . Denote by r. Then and . It follows that , which is your tau.